On random walks for Pollard's rho method
Author:
Edlyn Teske
Journal:
Math. Comp. 70 (2001), 809825
MSC (2000):
Primary 11Y16; Secondary 65C05, 94A60
Published electronically:
February 18, 2000
MathSciNet review:
1697652
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We consider Pollard's rho method for discrete logarithm computation. Usually, in the analysis of its running time the assumption is made that a random walk in the underlying group is simulated. We show that this assumption does not hold for the walk originally suggested by Pollard: its performance is worse than in the random case. We study alternative walks that can be efficiently applied to compute discrete logarithms. We introduce a class of walks that lead to the same performance as expected in the random case. We show that this holds for arbitrarily large prime group orders, thus making Pollard's rho method for prime group orders about faster than before.
 [AB82]
James
Arney and Edward
A. Bender, Random mappings with constraints on coalescence and
number of origins, Pacific J. Math. 103 (1982),
no. 2, 269–294. MR 705228
(84h:05110)
 [BM]
S.R. Blackburn and S. Murphy, The number of partitions in Pollard rho, Private communication, May 1998.
 [BP81]
Richard
P. Brent and John
M. Pollard, Factorization of the eighth Fermat
number, Math. Comp. 36
(1981), no. 154, 627–630. MR 606520
(83h:10014), http://dx.doi.org/10.1090/S00255718198106065205
 [DH97]
Jack
J. Dai and Martin
V. Hildebrand, Random random walks on the integers mod
𝑛, Statist. Probab. Lett. 35 (1997),
no. 4, 371–379. MR 1483024
(99f:60128), http://dx.doi.org/10.1016/S01677152(97)000357
 [GLV]
R. Gallant, R. Lambert, and S. Vanstone, Improving the parallelized Pollard lambda search on binary anomalous curves, to appear in Mathematics of Computation.
 [Har60]
Bernard
Harris, Probability distributions related to random mappings,
Ann. Math. Statist. 31 (1960), 1045–1062. MR 0119227
(22 #9993)
 [Hil94]
Martin
Hildebrand, Random walks supported on random points of
𝐙/𝐧𝐙, Probab. Theory Related Fields
100 (1994), no. 2, 191–203. MR 1296428
(95j:60015), http://dx.doi.org/10.1007/BF01199265
 [HV]
J. Horwitz and R. Venkatesan, Random Cayley graphs and the discrete log, Preprint, 1998.
 [Kec93]
D. B. Kececioglu, Reliability and life testing handbook, vol. 1, Prentice Hall, Englewood Cliffs, New Jersey, 1993.
 [Knu73]
Donald
E. Knuth, The art of computer programming. Volume 3,
AddisonWesley Publishing Co., Reading, Mass.LondonDon Mills, Ont., 1973.
Sorting and searching; AddisonWesley Series in Computer Science and
Information Processing. MR 0445948
(56 #4281)
 [LiD97]
LiDIA Group, Technische Universität Darmstadt, LiDIA  a library for computational number theory, version 1.3, 1997, Available from http://www.informatik.tudarmstadt.de/TI/LiDIA.
 [MvOV96]
Alfred
J. Menezes, Paul
C. van Oorschot, and Scott
A. Vanstone, Handbook of applied cryptography, CRC Press
Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton,
FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797
(99g:94015)
 [PH78]
Stephen
C. Pohlig and Martin
E. Hellman, An improved algorithm for computing logarithms over
𝐺𝐹(𝑝) and its cryptographic significance, IEEE
Trans. Information Theory IT24 (1978), no. 1,
106–110. MR 0484737
(58 #4617)
 [Pol]
J. M. Pollard, Private communications, March 1998, March 1999.
 [Pol75]
J.
M. Pollard, A Monte Carlo method for factorization, Nordisk
Tidskr. Informationsbehandling (BIT) 15 (1975),
no. 3, 331–334. MR 0392798
(52 #13611)
 [Pol78]
J.
M. Pollard, Monte Carlo methods for index
computation (𝑚𝑜𝑑\𝑝), Math. Comp. 32 (1978), no. 143, 918–924. MR 0491431
(58 #10684), http://dx.doi.org/10.1090/S00255718197804914319
 [SL84]
C.P.
Schnorr and H.
W. Lenstra Jr., A Monte Carlo factoring algorithm with
linear storage, Math. Comp.
43 (1984), no. 167, 289–311. MR 744939
(85d:11106), http://dx.doi.org/10.1090/S00255718198407449395
 [SSY82]
Robert
Sedgewick, Thomas
G. Szymanski, and Andrew
C. Yao, The complexity of finding cycles in periodic
functions, SIAM J. Comput. 11 (1982), no. 2,
376–390. MR
652911 (83f:68045), http://dx.doi.org/10.1137/0211030
 [Tes98a]
E. Teske, New algorithms for finite abelian groups, Ph.D. thesis, Technische Universität Darmstadt, Germany, 1998, Shaker Verlag, Aachen.
 [Tes98b]
Edlyn
Teske, A space efficient algorithm for group
structure computation, Math. Comp.
67 (1998), no. 224, 1637–1663. MR 1474658
(99a:11146), http://dx.doi.org/10.1090/S0025571898009685
 [Tes98c]
E. Teske, Speeding up Pollard's rho method for computing discrete logarithms, Algorithmic Number Theory Seminar ANTSIII, Lecture Notes in Computer Science, vol. 1423, SpringerVerlag, 1998, pp. 541554.
 [vOW99]
P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, Journal of Cryptology 12 (1999), 128. MR 99i:49054
 [WZ98]
M. Wiener and R. Zuccerato, Faster attacks on elliptic curve cryptosystems, Proceedings of SAC, Workshop on Selected Areas in Cryptography, Lecture Notes in Computer Science, 1998.
 [AB82]
 J. Arney and E. A. Bender, Random mappings with constraints on coalescence and number of origins, Pacific Journal of Mathematics 103 (1982), 269294. MR 84h:05110
 [BM]
 S.R. Blackburn and S. Murphy, The number of partitions in Pollard rho, Private communication, May 1998.
 [BP81]
 R.P. Brent and J.M. Pollard, Factorization of the eighth Fermat number, Mathematics of Computation 36 (1981), 627630. MR 83h:10014
 [DH97]
 J. J. Dai and M. V. Hildebrand, Random random walks on the integers , Statistics and Probability Letters 35 (1997), 371379. MR 99f:60128
 [GLV]
 R. Gallant, R. Lambert, and S. Vanstone, Improving the parallelized Pollard lambda search on binary anomalous curves, to appear in Mathematics of Computation.
 [Har60]
 B. Harris, Probability distributions related to random mappings, Annals of Math. Statistics 31 (1960), 10451062. MR 22:9993
 [Hil94]
 M. V. Hildebrand, Random walks supported on the random points of , Probability Theory and Related Fields 100 (1994), 191203. MR 95j:60015
 [HV]
 J. Horwitz and R. Venkatesan, Random Cayley graphs and the discrete log, Preprint, 1998.
 [Kec93]
 D. B. Kececioglu, Reliability and life testing handbook, vol. 1, Prentice Hall, Englewood Cliffs, New Jersey, 1993.
 [Knu73]
 D. E. Knuth, The art of computer programming. volume 3: Sorting and searching, AddisonWesley, Reading, Massachusetts, 1973. MR 56:4281
 [LiD97]
 LiDIA Group, Technische Universität Darmstadt, LiDIA  a library for computational number theory, version 1.3, 1997, Available from http://www.informatik.tudarmstadt.de/TI/LiDIA.
 [MvOV96]
 A. Menezes, P. van Oorschot, and S. A. Vanstone, Handbook of applied cryptography, CRC Press, 1996. MR 99g:94015
 [PH78]
 S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over and its cryptographic significance, IEEETransactions on Information Theory 24 (1978), 106110. MR 58:4617
 [Pol]
 J. M. Pollard, Private communications, March 1998, March 1999.
 [Pol75]
 J. M. Pollard, A Monte Carlo method for factorization, BIT 15 (1975), no. 3, 331335. MR 52:13611
 [Pol78]
 J. M. Pollard, Monte Carlo methods for index computation (mod ), Mathematics of Computation 32 (1978), no. 143, 918924. MR 58:10684
 [SL84]
 C. P. Schnorr and H. W. Lenstra, Jr., A Monte Carlo factoring algorithm with linear storage, Mathematics of Computation 43 (1984), no. 167, 289311. MR 85d:11106
 [SSY82]
 R. Sedgewick, T. G. Szymanski, and A. C. Yao, The complexity of finding cycles in periodic functions, SIAM J. Computing 11 (1982), no. 2, 376390. MR 83f:68045
 [Tes98a]
 E. Teske, New algorithms for finite abelian groups, Ph.D. thesis, Technische Universität Darmstadt, Germany, 1998, Shaker Verlag, Aachen.
 [Tes98b]
 E. Teske, A space efficient algorithm for group structure computation, Mathematics of Computation 67 (1998), 16371663. MR 99a:11146
 [Tes98c]
 E. Teske, Speeding up Pollard's rho method for computing discrete logarithms, Algorithmic Number Theory Seminar ANTSIII, Lecture Notes in Computer Science, vol. 1423, SpringerVerlag, 1998, pp. 541554.
 [vOW99]
 P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, Journal of Cryptology 12 (1999), 128. MR 99i:49054
 [WZ98]
 M. Wiener and R. Zuccerato, Faster attacks on elliptic curve cryptosystems, Proceedings of SAC, Workshop on Selected Areas in Cryptography, Lecture Notes in Computer Science, 1998.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
11Y16,
65C05,
94A60
Retrieve articles in all journals
with MSC (2000):
11Y16,
65C05,
94A60
Additional Information
Edlyn Teske
Affiliation:
University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1
Email:
eteske@cacr.math.uwaterloo.ca
DOI:
http://dx.doi.org/10.1090/S0025571800012138
PII:
S 00255718(00)012138
Keywords:
Pollard's rho method,
discrete logarithm,
random walks in groups
Received by editor(s):
February 23, 1999
Received by editor(s) in revised form:
May 24, 1999
Published electronically:
February 18, 2000
Article copyright:
© Copyright 2000
American Mathematical Society
