Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Speeding Up the Pollard Rho Method on Prime Fields
verfasst von : Jung Hee Cheon, Jin Hong, Minkyu Kim
Erschienen in: Advances in Cryptology - ASIACRYPT 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a method to speed up the
r
-adding walk on multiplicative subgroups of the prime field. The
r
-adding walk is an iterating function used with the Pollard rho algorithm and is known to require less iterations than Pollard’s original iterating function in reaching a collision. Our main idea is to follow through the
r
-adding walk with only partial information about the nodes reached.
The trail traveled by the proposed method is a normal
r
-adding walk, but with significantly reduced execution time for each iteration. While a single iteration of most
r
-adding walks on
F
p
require a multiplication of two integers of log
p
size, the proposed method requires an operation of complexity only linear in log
p
, using a pre-computed table of size
O
((log
p
)
r
+ 1
·loglog
p
). In practice, our rudimentary implementation of the proposed method increased the speed of Pollard rho with
r
-adding walks by a factor of more than 10 for 1024-bit random primes
p
.