in reply to Passwords

my @chars = ('a' .. 'z', 'A' .. 'Z', 0 .. 9);
my $password = do {{
    local $_ = join "" => map {$chars [rand @chars]} 1 .. 8;
    redo unless /[a-z]/ && /[A-Z]/ && /\d/;
    $_;
}};

[download]
Abigail

Replies are listed 'Best First'.
Re: Passwords
by Abigail-II (Bishop) on Aug 02, 2002 at 13:14 UTC
    One might wonder, how often does the redo get excuted? Well, we're doing a redo if the generated password doesn't contain a lowercase letter, or it doesn't contain an uppercase letter, or it doesn't contain a digit.

    The chance of not containing a lowercase letter is the same as the chance the password only contains uppercase letters or digits, which is (36/62)^8. The chance of not containing an uppercase letter is of course the same. Similary, the chance of not containing a digit is (52/62)^8.

    Now, the chance of doing a redo is sligthly less than the sum of these three chances, because than you would count the chance of the password containing only lowercase letters, only uppercase letters, or only digits twice. The chance of containing only lowercase letters, or only uppercase letters is (26/62)^8. The chance of containing only digits is (10/62)^8.

    Hence the chance of doing a redo is 

    (36/62)^8+(36/62)^8+(52/62)^8-(26/62)^8-(26/62)^8-(10/62)^8

    [download]
    which, according to bc, is roughly 
         .2687742319

    [download]
    or just over one in four.

    So, what is the expected number of iterations you have to do to calculate a password? Let p be the chance of having to do a redo. Then the number of iterations is 

     
  (1 - p) + 2 (1 - p) p + 3 (1 - p) p^2 + 4 (1 - p) p^3 + ...  =

  (1 - p) (1 + 2 p + 3 p^2 + 4 p^3 + ...)                      =

   1 - p
   -----  (p + 2 p^2 + 3 p^3 + 4 p^4 + ...)                    =  
     p

   1 - p     p           1
   -----  ------ 2  =  -----
     p    (1 - p)      1 - p

    [download]
    which is roughly 
        1.3675666854

    [download]
    Tests suggests the calculated number might be correct.

    Abigail

[reply]
[d/l]
[select]
      Wow, wicked flashback to AP Stats....
[reply]
A reply falls below the community's threshold of quality. You may see it by logging in.

In Section Seekers of Perl Wisdom