The Complexity of Finding Cycles in Periodic Functions

DOI10.1137/0211030MaRDI QIDQ3936192zbMATH OpenOpenAlexWikidataFDO

Authors Robert Sedgewick, Thomas G. Szymanski, Andrew Chi-Chih Yao

Publication date 1982

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0211030

zbMATH Keywords

cycle detectrontime-space tradeoff

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Analysis of algorithms and problem complexity (68Q25)

Cited in

(16)

• Improved lower bounds for the cycle detection problem
• Is the data encryption standard a group? (Results of cycling experiments on DES)
• Lower bounds for the cycle detection problem
• Improved classical cryptanalysis of SIKE in practice
• Solving discrete logarithm problems faster with the aid of pre-computation
• Cycle detection using a stack
• On random walks for Pollard's rho method
• Using random error correcting codes in near-collision attacks on generic hash-functions
• Time-memory trade-offs for near-collisions
• The Hash Function Family LAKE
• Speeding Up the Pollard Rho Method on Prime Fields
• Preimage Attacks on 3-Pass HAVAL and Step-Reduced MD5
• Accelerating Pollard's rho algorithm on finite fields
• DYNAMICAL CHARACTERISTICS OF DISCRETIZED CHAOTIC PERMUTATIONS
• Faster Multicollisions
• Cycle detection algorithms and their applications

This page was built for publication: The Complexity of Finding Cycles in Periodic Functions

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