{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T10:25:24Z","timestamp":1776767124760,"version":"3.51.2"},"reference-count":23,"publisher":"American Mathematical Society (AMS)","issue":"234","license":[{"start":{"date-parts":[[2001,2,18]],"date-time":"2001-02-18T00:00:00Z","timestamp":982454400000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We consider Pollard\u2019s 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\u2019s rho method for prime group orders about\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"20\">\n                        <mml:semantics>\n                          <mml:mn>20<\/mml:mn>\n                          <mml:annotation encoding=\"application\/x-tex\">20%<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    faster than before.\n                  <\/p>","DOI":"10.1090\/s0025-5718-00-01213-8","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:17:46Z","timestamp":1027707466000},"page":"809-825","source":"Crossref","is-referenced-by-count":61,"title":["On random walks for Pollard\u2019s rho method"],"prefix":"10.1090","volume":"70","author":[{"given":"Edlyn","family":"Teske","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2000,2,18]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"crossref","first-page":"269","DOI":"10.2140\/pjm.1982.103.269","article-title":"Random mappings with constraints on coalescence and number of origins","volume":"103","author":"Arney, James","year":"1982","journal-title":"Pacific J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0030-8730","issn-type":"print"},{"key":"2","unstructured":"[BM] S.R. Blackburn and S. Murphy, The number of partitions in Pollard rho, Private communication, May 1998."},{"issue":"154","key":"3","doi-asserted-by":"publisher","first-page":"627","DOI":"10.2307\/2007666","article-title":"Factorization of the eighth Fermat number","volume":"36","author":"Brent, Richard P.","year":"1981","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"4","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/S0167-7152(97)00035-7","article-title":"Random random walks on the integers mod \ud835\udc5b","volume":"35","author":"Dai, Jack J.","year":"1997","journal-title":"Statist. Probab. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0167-7152","issn-type":"print"},{"key":"5","unstructured":"[GLV] R. Gallant, R. Lambert, and S. Vanstone, Improving the parallelized Pollard lambda search on binary anomalous curves, to appear in  Mathematics of Computation."},{"key":"6","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1214\/aoms\/1177705677","article-title":"Probability distributions related to random mappings","volume":"31","author":"Harris, Bernard","year":"1960","journal-title":"Ann. Math. Statist.","ISSN":"https:\/\/id.crossref.org\/issn\/0003-4851","issn-type":"print"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01199265","article-title":"Random walks supported on random points of \ud835\udc19\/\ud835\udc27\ud835\udc19","volume":"100","author":"Hildebrand, Martin","year":"1994","journal-title":"Probab. Theory Related Fields","ISSN":"https:\/\/id.crossref.org\/issn\/0178-8051","issn-type":"print"},{"key":"8","unstructured":"[HV] J. Horwitz and R. Venkatesan, Random Cayley graphs and the discrete log, Preprint, 1998."},{"key":"9","unstructured":"[Kec93] D. B. Kececioglu, Reliability and life testing handbook, vol. 1, Prentice Hall, Englewood Cliffs, New Jersey, 1993."},{"key":"10","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The art of computer programming. Volume 3","author":"Knuth, Donald E.","year":"1973"},{"key":"11","unstructured":"[LiD97] LiDIA Group, Technische Universit\u00e4t Darmstadt, LiDIA - a library for computational number theory, version 1.3, 1997, Available from http:\/\/www.informatik.tu-darmstadt.de\/TI\/LiDIA."},{"key":"12","series-title":"CRC Press Series on Discrete Mathematics and its Applications","isbn-type":"print","volume-title":"Handbook of applied cryptography","author":"Menezes, Alfred J.","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0849385237"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/tit.1978.1055817","article-title":"An improved algorithm for computing logarithms over \ud835\udc3a\ud835\udc39(\ud835\udc5d) and its cryptographic significance","volume":"IT-24","author":"Pohlig, Stephen C.","year":"1978","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"14","unstructured":"[Pol] J. M. Pollard, Private communications, March 1998, March 1999."},{"issue":"3","key":"15","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/bf01933667","article-title":"A Monte Carlo method for factorization","volume":"15","author":"Pollard, J. M.","year":"1975","journal-title":"Nordisk Tidskr. Informationsbehandling (BIT)","ISSN":"https:\/\/id.crossref.org\/issn\/0901-246X","issn-type":"print"},{"issue":"143","key":"16","doi-asserted-by":"publisher","first-page":"918","DOI":"10.2307\/2006496","article-title":"Monte Carlo methods for index computation (\ud835\udc5a\ud835\udc5c\ud835\udc51\ud835\udc5d)","volume":"32","author":"Pollard, J. M.","year":"1978","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"167","key":"17","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/2007414","article-title":"A Monte Carlo factoring algorithm with linear storage","volume":"43","author":"Schnorr, C.-P.","year":"1984","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"2","key":"18","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1137\/0211030","article-title":"The complexity of finding cycles in periodic functions","volume":"11","author":"Sedgewick, Robert","year":"1982","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"19","unstructured":"[Tes98a] E. Teske, New algorithms for finite abelian groups, Ph.D. thesis, Technische Universit\u00e4t Darmstadt, Germany, 1998, Shaker Verlag, Aachen."},{"issue":"224","key":"20","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1090\/S0025-5718-98-00968-5","article-title":"A space efficient algorithm for group structure computation","volume":"67","author":"Teske, Edlyn","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[Tes98c] E. Teske, Speeding up Pollard\u2019s rho method for computing discrete logarithms, Algorithmic Number Theory Seminar ANTS-III, Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, 1998, pp. 541\u2013554.","DOI":"10.1007\/BFb0054891"},{"key":"22","first-page":"656","article-title":"The Weierstrass condition for multiple integral variation problems","volume":"5","author":"Graves, Lawrence M.","year":"1939","journal-title":"Duke Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-7094","issn-type":"print"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[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.","DOI":"10.1007\/3-540-48892-8_15"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01213-8\/S0025-5718-00-01213-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01213-8\/S0025-5718-00-01213-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:35:35Z","timestamp":1776724535000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01213-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2,18]]},"references-count":23,"journal-issue":{"issue":"234","published-print":{"date-parts":[[2001,4]]}},"alternative-id":["S0025-5718-00-01213-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01213-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2000,2,18]]}}}