International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Bernoulli numbers and the probability of a birthday surprise

Authors:
Boaz Tsaban
Download:
URL: http://eprint.iacr.org/2003/137
Search ePrint
Search Google
Abstract: A birthday surprise is the event that, given $k$ uniformly random samples from a sample space of size $n$, at least two of them are identical. We show that Bernoulli numbers can be used to derive arbitrarily exact bounds on the probability of a birthday surprise. This result can be used in arbitrary precision calculators, and it can be applied to better understand some questions in communication security and pseudorandom number generation.
BibTeX
@misc{eprint-2003-11852,
  title={Bernoulli numbers and the probability of a birthday surprise},
  booktitle={IACR Eprint archive},
  keywords={foundations / birthday paradox, arbitrary precision calculators},
  url={http://eprint.iacr.org/2003/137},
  note={Discrete Applied Mathematics 127(3) (2003), 657--663 tsaban@math.huji.ac.il 12250 received 16 Jul 2003},
  author={Boaz Tsaban},
  year=2003
}