Cryptology ePrint Archive: Report 2010/616

A non-uniform birthday problem with applications to discrete logarithms

Steven D. Galbraith and Mark Holmes

Abstract: We consider a generalisation of the birthday problem that arises in the analysis of algorithms for certain variants of the discrete logarithm problem in groups. More precisely, we consider sampling coloured balls and placing them in urns, such that the distribution of assigning balls to urns depends on the colour of the ball. We determine the expected number of trials until two balls of different colours are placed in the same urn. As an aside we present an amusing ``paradox'' about birthdays.

Category / Keywords: birthday paradox, discrete logarithm problem (DLP)

Publication Info: Submitted to Discrete Applied Mathematics

Date: received 1 Dec 2010, last revised 14 Feb 2012

Contact author: s galbraith at math auckland ac nz

Available format(s): PDF | BibTeX Citation

Version: 20120214:211510 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]