Skip to main content
correct typo
Source Link
Ross Millikan
  • 377.5k
  • 27
  • 257
  • 454

Roughly speaking, you expect a collision when the number of pairs is the number of hashes. If you issue $n$ hashes, you have $\frac {n^2}2$ pairs (I ignored the $-1$ on one of the $m$$n$'s), so you can afford to issue about $\sqrt{2M}=\sqrt {2\cdot 62^{10}}=62^5\sqrt 2\approx 1.3\cdot 10^9$ keys. In the Wikipedia article it shows there is another factor of $\sqrt {\ln 2} \approx 0.83$ which I would ignore but it says you can issue one billion codes before you have a $50\%$ chance of collision.

Roughly speaking, you expect a collision when the number of pairs is the number of hashes. If you issue $n$ hashes, you have $\frac {n^2}2$ pairs (I ignored the $-1$ on one of the $m$'s), so you can afford to issue about $\sqrt{2M}=\sqrt {2\cdot 62^{10}}=62^5\sqrt 2\approx 1.3\cdot 10^9$ keys. In the Wikipedia article it shows there is another factor of $\sqrt {\ln 2} \approx 0.83$ which I would ignore but it says you can issue one billion codes before you have a $50\%$ chance of collision.

Roughly speaking, you expect a collision when the number of pairs is the number of hashes. If you issue $n$ hashes, you have $\frac {n^2}2$ pairs (I ignored the $-1$ on one of the $n$'s), so you can afford to issue about $\sqrt{2M}=\sqrt {2\cdot 62^{10}}=62^5\sqrt 2\approx 1.3\cdot 10^9$ keys. In the Wikipedia article it shows there is another factor of $\sqrt {\ln 2} \approx 0.83$ which I would ignore but it says you can issue one billion codes before you have a $50\%$ chance of collision.

Source Link
Ross Millikan
  • 377.5k
  • 27
  • 257
  • 454

Roughly speaking, you expect a collision when the number of pairs is the number of hashes. If you issue $n$ hashes, you have $\frac {n^2}2$ pairs (I ignored the $-1$ on one of the $m$'s), so you can afford to issue about $\sqrt{2M}=\sqrt {2\cdot 62^{10}}=62^5\sqrt 2\approx 1.3\cdot 10^9$ keys. In the Wikipedia article it shows there is another factor of $\sqrt {\ln 2} \approx 0.83$ which I would ignore but it says you can issue one billion codes before you have a $50\%$ chance of collision.