On random walks for Pollard’s rho method

Teske, Edlyn

doi:10.1090/S0025-5718-00-01213-8

On random walks for Pollard’s rho method
HTML articles powered by AMS MathViewer

by Edlyn Teske PDF

Math. Comp. 70 (2001), 809-825 Request permission

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 $20\%$ faster than before.

References

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
S.R. Blackburn and S. Murphy, The number of partitions in Pollard rho, Private communication, May 1998.
Richard P. Brent and John M. Pollard, Factorization of the eighth Fermat number, Math. Comp. 36 (1981), no. 154, 627–630. MR 606520, DOI 10.1090/S0025-5718-1981-0606520-5
Jack J. Dai and Martin V. Hildebrand, Random random walks on the integers mod $n$, Statist. Probab. Lett. 35 (1997), no. 4, 371–379. MR 1483024, DOI 10.1016/S0167-7152(97)00035-7
R. Gallant, R. Lambert, and S. Vanstone, Improving the parallelized Pollard lambda search on binary anomalous curves, to appear in Mathematics of Computation.
Bernard Harris, Probability distributions related to random mappings, Ann. Math. Statist. 31 (1960), 1045–1062. MR 119227, DOI 10.1214/aoms/1177705677
Martin Hildebrand, Random walks supported on random points of $\mathbf Z/n\mathbf Z$, Probab. Theory Related Fields 100 (1994), no. 2, 191–203. MR 1296428, DOI 10.1007/BF01199265
J. Horwitz and R. Venkatesan, Random Cayley graphs and the discrete log, Preprint, 1998.
D. B. Kececioglu, Reliability and life testing handbook, vol. 1, Prentice Hall, Englewood Cliffs, New Jersey, 1993.
Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR 0445948
LiDIA Group, Technische Universität Darmstadt, LiDIA - a library for computational number theory, version 1.3, 1997, Available from http://www.informatik.tu-darmstadt.de/TI/LiDIA.
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
Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817
J. M. Pollard, Private communications, March 1998, March 1999.
J. M. Pollard, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), no. 3, 331–334. MR 392798, DOI 10.1007/bf01933667
J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
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, DOI 10.1090/S0025-5718-1984-0744939-5
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, DOI 10.1137/0211030
E. Teske, New algorithms for finite abelian groups, Ph.D. thesis, Technische Universität Darmstadt, Germany, 1998, Shaker Verlag, Aachen.
Edlyn Teske, A space efficient algorithm for group structure computation, Math. Comp. 67 (1998), no. 224, 1637–1663. MR 1474658, DOI 10.1090/S0025-5718-98-00968-5
E. Teske, Speeding up Pollard’s rho method for computing discrete logarithms, Algorithmic Number Theory Seminar ANTS-III, Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, 1998, pp. 541–554.
Lawrence M. Graves, The Weierstrass condition for multiple integral variation problems, Duke Math. J. 5 (1939), 656–660. MR 99
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.