I am comparing the actual probability of no collisions to the probability approximation formula of no collisions from the Understanding Cryptography text.

The approximation is as follows:

$$P(\mathtt{no\ collisions}) = \exp\left(\frac{-t(t-1)}{2}\right)\cdot2^n $$

I know that $t$ represents the number of elements but I am confused about the denominator. The text says that $n$ is the output width of $h()$. I don't really understand this. Does this mean that for lets say the Birthday Paradox, $n = 365$? So the denominator would be $2\cdot2^{365}$?

  • 1
    $\begingroup$ Welcome to Math.SE. I added MathJax formatting to your post. If the edit seems incorrect, please roll it back. $\endgroup$ – zahbaz Dec 5 '15 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.