Accelerating Pollard's rho algorithm on finite fields

DOI10.1007/S00145-010-9093-7MaRDI QIDQ431795zbMATH OpenOpenAlexFDO

Authors Jung Hee Cheon, Jin Hong, Minkyu Kim

Publication date 3 July 2012

Published in Journal of Cryptology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00145-010-9093-7

zbMATH Keywords

\(r\)-adding walkdiscrete logarithm problemdistinguished pointfinite fieldPollard's rho

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Cryptography (94A60)

Recommendations

• An efficient collision detection method for computing discrete logarithms with Pollard's rho
• Speeding Up the Pollard Rho Method on Prime Fields
• On random walks for Pollard's rho method
• scientific article; zbMATH DE number 2165762
• On an probabilistic algorithm solving discrete logarithm problem

Cites work

• A Monte Carlo Factoring Algorithm With Linear Storage
• A public key cryptosystem and a signature scheme based on discrete logarithms
• An improved algorithm for computing logarithms over<tex>GF(p)</tex>and its cryptographic significance (Corresp.)
• An improved Monte Carlo factorization algorithm
• Computing discrete logarithms with the parallelized kangaroo method.
• Cycle detection using a stack
• Fast evaluation of logarithms in fields of characteristic two
• Fast multiplication of large numbers
• scientific article; zbMATH DE number 4069911 (Why is no real title available?)
• scientific article; zbMATH DE number 1186971 (Why is no real title available?)
• scientific article; zbMATH DE number 16479 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1304118 (Why is no real title available?)
• scientific article; zbMATH DE number 1504543 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• scientific article; zbMATH DE number 3353398 (Why is no real title available?)
• Improving the parallelized Pollard lambda search on anomalous binary curves
• Kangaroos, monopoly and discrete logarithms
• Monte Carlo Methods for Index Computation (mod p)
• New directions in cryptography
• On random walks for Pollard's rho method
• Parallel collision search with cryptanalytic applications
• Polynomial and normal bases for finite fields
• Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction
• Speeding Up the Pollard Rho Method on Prime Fields
• Subset-Restricted Random Walks for Pollard rho Method on ${\mathbf{F}_{p^m}}$
• The Complexity of Finding Cycles in Periodic Functions

Cited in

(10)

• Improving the Gaudry-Schost algorithm for multidimensional discrete logarithms
• Speeding Up the Pollard Rho Method on Prime Fields
• An efficient collision detection method for computing discrete logarithms with Pollard's rho
• Improved Pollard rho method for computing discrete logarithms over finite extension fields
• scientific article; zbMATH DE number 2165762 (Why is no real title available?)
• scientific article; zbMATH DE number 2085207 (Why is no real title available?)
• On an probabilistic algorithm solving discrete logarithm problem
• On improvements of ther-adding walk in a finite field of characteristic 2
• Combining Montgomery multiplication with tag tracing for the Pollard rho algorithm in prime order fields
• Bounds in various generalized settings of the discrete logarithm problem

Describes a project that uses

Uses Software

• NTL

This page was built for publication: Accelerating Pollard's rho algorithm on finite fields

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