A non-uniform birthday problem with applications to discrete logarithms

DOI10.1016/J.DAM.2012.02.019MaRDI QIDQ427899zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Steven D. Galbraith, Mark 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

birthday paradoxdiscrete logarithm problemprobabilistic analysis of randomised algorithms

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Recommendations

• scientific article; zbMATH DE number 58016
• scientific article; zbMATH DE number 6122929
• An O(n log n) algorithm for the generalized birthday problem

Cites work

• Algorithmic Number Theory
• An Improvement to the Gaudry-Schost Algorithm for Multidimensional Discrete Logarithm Problems
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Computing discrete logarithms in an interval
• scientific article; zbMATH DE number 53571 (Why is no real title available?)
• Kangaroos, monopoly and discrete logarithms
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• Monte Carlo Methods for Index Computation (mod p)
• Occupancy with two types of balls
• On waiting time in the scheme of random allocation of coloured particies
• Poisson approximation and the Chen-Stein method. With comments and a rejoinder by the authors
• Poisson approximation for dependent trials
• Probability to meet in the middle
• The matching, birthday and the strong birthday problem: a contemporary review
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval

Cited in

(17)

• 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
• A variant of the Galbraith-Ruprai algorithm for discrete logarithms with improved complexity
• Refining the asymptotic approximation of the group size in the birthday paradox
• Modified Gaudry-Schost algorithm for the two-dimensional discrete logarithm problem
• A new approach to the discrete logarithm problem with auxiliary inputs
• Computing discrete logarithms in an interval
• Collision times in multicolor urn models and sequential graph coloring with applications to discrete logarithms
• ON THE COMPLEXITY OF DISCRETE LOGARITHM PROBLEM IN AN INTERVAL IN A FINITE CYCLIC GROUP WITH EFFICIENT INVERSION
• О сложности двупараметрической задачи дискретного логарифмирования в конечной циклической группе с эффективным автоморфизмом
• Limit theorems for monochromatic stars
• The Second-Moment Phenomenon for Monochromatic Subgraphs
• A fourth‐moment phenomenon for asymptotic normality of monochromatic subgraphs
• Normal approximation and fourth moment theorems for monochromatic triangles
• Characterizing the fourth-moment phenomenon of monochromatic subgraph counts via influences
• Joint Poisson convergence of monochromatic hyperedges in multiplex hypergraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q427899)