Number Theoretical Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 27

imation to hold. The reader can easily verify this voodoo math by verifying in a calculator that 1 - (1/365) ≈
0.9972603 and e -1/365 ≈ 0.9972640, which are pretty close.
We now have the previous quantity rewritten, approximately, as

Combining the exponents by adding them yields

This might remind us of the familiar identity that 1 + 2 + 3 + ... + n = n ( n + 1)/2, allowing us the further simpli-
fication

Now this is something we can use. Specifically, we will want to know the value of k , relative to n , for us to
have a certain probability of no repetition (and, therefore, the probability of at least one repetition). It's easy to
know when there is a 100% chance: Just let k = n (for birthdays, pick 365 people, and there will be a repetition).
Something more useful to know would be the tipping point: When will the probability be about half (0.5)? In
this case, the probability of no repetition is the same as the probability of at least one repetition (since 1 - 0.5 =
0.5), thus we can just set the previous approximation for our probability equal to 0.5 and solve for k in terms of
n:

If we take the natural logarithm of both sides, we get

Since In(1/ x ) = -ln x , because of the rules of exponents, we have

And multiplying both sides by 2 n :

We can solve this for k exactly (using the quadratic formula from college algebra), but the results look a little
inelegant. Since we already have made one approximation, there's not too much harm in making another one,
especially if it simplifies our final result. In this particular case, we are already assuming that n is large. We can
kind of gauge then that k is going to be a bit large too, but not quite as much so as n. But if k is still pretty large,
then k ≈ k - 1, so that k ( k - 1) ≈ k 2 . For example, if k were about 100, then there would be very little difference
between 100(100 - 1) = 9, 900 and 100 2 = 10, 000: The difference is only 1%.
This allows us to write the preceding statement as

Taking the positive square root of both sides (since a negative k would not make sense):

We can take the outside, and substitute its approximation:

This is pretty significant. It means that if we have n possibilities, we need only to look at a constant times the
square root of that number of events in order to have about a 50% chance of having a repetition. For birthdays
(with n = 365), this means that k ≈ 22.494. Rounding up to get a better than half chance, we get k = 23. That