Accelerating Pollard's rho algorithm on finite fields

DOI10.1007/S00145-010-9093-7zbMath1277.94018OpenAlexW2011765981MaRDI QIDQ431795

Jin Hong, Jung Hee Cheon, 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

finite fielddiscrete logarithm problemdistinguished point\(r\)-adding walkPollard's rho

Mathematics Subject Classification ID

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

Related Items (2)

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

Uses Software

• NTL

Cites Work

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

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