A non-uniform birthday problem with applications to discrete logarithms

DOI10.1016/J.DAM.2012.02.019zbMath1246.60015DBLPjournals/dam/GalbraithH12OpenAlexW2090493866WikidataQ61914021 ScholiaQ61914021MaRDI QIDQ427899

Steven D. Galbraith, Mark P. Holmes

Publication date: 18 June 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.02.019

zbMATH Keywords

discrete logarithm problembirthday paradoxprobabilistic analysis of randomised algorithms

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Related Items (13)

A new approach to the discrete logarithm problem with auxiliary inputs ⋮ A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity ⋮ A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs ⋮ Normal approximation and fourth moment theorems for monochromatic triangles ⋮ ON THE COMPLEXITY OF DISCRETE LOGARITHM PROBLEM IN AN INTERVAL IN A FINITE CYCLIC GROUP WITH EFFICIENT INVERSION ⋮ О сложности двупараметрической задачи дискретного логарифмирования в конечной циклической группе с эффективным автоморфизмом ⋮ Computing discrete logarithms in an interval ⋮ Limit theorems for monochromatic stars ⋮ Modified Gaudry-Schost algorithm for the two-dimensional discrete logarithm problem ⋮ The Second-Moment Phenomenon for Monochromatic Subgraphs ⋮ Non-uniform birthday problem revisited: refined analysis and applications to discrete logarithms ⋮ Improving the Gaudry-Schost algorithm for multidimensional discrete logarithms ⋮ Monochromatic subgraphs in randomly colored graphons

Cites Work

• Unnamed Item
• Probability to meet in the middle
• Occupancy with two types of balls
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Poisson approximation for dependent trials
• Kangaroos, monopoly and discrete logarithms
• Poisson approximation and the Chen-Stein method. With comments and a rejoinder by the authors
• The matching, birthday and the strong birthday problem: a contemporary review
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval
• An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems
• Monte Carlo Methods for Index Computation (mod p)
• On waiting time in the scheme of random allocation of coloured particies
• Computing discrete logarithms in an interval
• Algorithmic Number Theory

This page was built for publication: A non-uniform birthday problem with applications to discrete logarithms