1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Calculating number of character combinations in password

  1. Mar 23, 2013 #1
    First of all, I'm not strong in math, but always interested in learning more. This is an "intellectual satisfaction" type of question, meaning knowing the answer won't really impact anything, but will afford me a certain satisfaction by quenching my curiosity. Maybe someone out there would be willing to help me work through how to compute the possible combinations of a password?

    The company I work for has a system that historically utilized passwords of 8 (and exactly 8, no more, no less) alphanumeric characters. The only rule was that the first character could not be numeric; otherwise, repeated characters were okay. The password is not case sensitive. So there are 26 possibilities for the first character, and positions 2 - 8 can be any of 36 possibilities. In my mind, then, the number of password possibilities is expressed as 26x36x36x36x36x36x36x36. The result is 2+ trillion; 2,037,468,266,496 to be exact.

    The rules were recently changed so that the 8-character password must now contain at least one alphabetic character and one numeric character, as well as one of three special characters (#,!,~). The special character must be used in positions 2 - 7 only, not in the first or last position.

    My gut told me the total number of password possibilities had been reduced, because though the overall character base was increased from 36 to 39, two (the first and last) are still base 36, at least one of the characters is base 26, at least one is base 10, and at least one is only base 3. Maybe my gut was wrong though, because of the "at least" part of the scenario. Do the new rules have any mathematical limiting impact on the possibilities for the middle six characters? Is 36x39x39x39x39x39x39x36 = 4,560,291,914,256 the right answer? I have a feeling I'm overlooking something, and I'd appreciate someone giving me some clarity on this. Thanks!
  2. jcsd
  3. Mar 23, 2013 #2
    yeah, the calculation is more complicated than that. Because your calculation says that
    12345678 ,for example, is a possible password. But there must be at least a number, at least an alphabet and at least one of the 3 symbols you mentioned above.
  4. Mar 23, 2013 #3
    You can picture it this way: first the new rules increase the number of possible passwords to the amount you calculated. But they then decrease the amount of possible passwords by requiring at least one position to be filled by a symbol, at least one position to be a number, and at least one position to be a letter. It is tedious to count the condition "at least". What we can do instead is subtract the three types of passwords that are not allowed: passwords that do not contain any symbols, passwords that do not contain any numbers and passwords that do not contain any letters. We want to subtract the union of these three sets, so we must take care to account for their intersections (for example, when we subtract each set separately we subtract "passwords that contain neither numbers nor letters" twice: once when we subtract passwords with no numbers and again when we subtract passwords with no letters. We must add back this amount, since the second subtraction is erroneous: that amount was already subtracted). This method of counting is usually referred to as the Inclusion-Exclusion Principle.
    So we have "No Numbers" as (26^2)(29^6). What that means is we have only letters in the first and last positions and a choice of only letters or symbols for positions 2-7. Similarly, "No Letters" is (10^2)(13^6) and "No Symbols" is 36^8. The 3 double intersections that are over-counted are "No Numbers or letters": 0 because our full set only contains passwords that require letters or numerals in the first and last position, "No Numbers or symbols": 26^8, and "No letters or symbols": 10^8. The triple intersection: passwords that contain no letters, no symbols and no numbers is empty.
    So our final count would be the full set of "8-character passwords containing only alphanumeric characters in the 1st and last positions and including symbols as an option in positions 2-7", subtract the single missing categories, and add back the over-counted intersections: (36^2)(39^6) - (26^2)(29^6) - (10^2)(13^6) - 36^8 + 26^8 + 10^8 = 1,545,525,825,480. According to Wolfram Alpha, that's about 5 times the amount of stars in our galaxy, which is a cute tidbit to know. =D
    Last edited: Mar 23, 2013
  5. Mar 23, 2013 #4
    I think we can formulize your solution as follows:

    Let [itex]n(A)[/itex] : # of passwords without any number, [itex]n(B)[/itex]: # of passwords without any letter, [itex]n(C)[/itex]: # of passwords without any symbol, [itex]n(S)[/itex]: # of passwords in the full set.

    Then, we calculate [itex]n(S)-n(A\cup B\cup C)[/itex], where [itex]n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(A\cap C)-n(B\cap C)+n(A\cap B\cap C)[/itex] to find the answer.
  6. Mar 23, 2013 #5
    Thanks to each of you.

    Slider, your well-written explanation is exactly what I was looking for. I followed the thought process and it makes sense to me now. I appreciate your time.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook