{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T00:05:53Z","timestamp":1780358753596,"version":"3.54.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,11,12]],"date-time":"2010-11-12T00:00:00Z","timestamp":1289520000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2012,4]]},"DOI":"10.1007\/s00145-010-9093-7","type":"journal-article","created":{"date-parts":[[2010,11,11]],"date-time":"2010-11-11T17:12:36Z","timestamp":1289495556000},"page":"195-242","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Accelerating Pollard\u2019s Rho Algorithm on Finite Fields"],"prefix":"10.1007","volume":"25","author":[{"given":"Jung Hee","family":"Cheon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jin","family":"Hong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minkyu","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,11,12]]},"reference":[{"key":"9093_CR1","first-page":"55","volume-title":"Proc. of the IEEE 20th Annual Symposium on Foundations of Computer Science (FOCS)","author":"L. Adleman","year":"1979","unstructured":"L. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, in Proc. of the IEEE 20th Annual Symposium on Foundations of Computer Science (FOCS) (1979), pp.\u00a055\u201360"},{"key":"9093_CR2","unstructured":"J.W. Bos, M.E. Kaihara, T. Kleinjung, A.K. Lenstra, P.L. Montgomery, Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction. Private communication"},{"key":"9093_CR3","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/BF01933190","volume":"20","author":"R. Brent","year":"1980","unstructured":"R. Brent, An improved Monte Carlo factorization algorithm. BIT\n                           20, 176\u2013184 (1980)","journal-title":"BIT"},{"key":"9093_CR4","series-title":"LNCS","first-page":"471","volume-title":"ASIACRYPT \u201908","author":"J. Cheon","year":"2008","unstructured":"J. Cheon, J. Hong, M. Kim, Speeding up the Pollard rho method on prime fields, in ASIACRYPT \u201908. LNCS, vol.\u00a05350 (Springer, Berlin, 2008), pp.\u00a0471\u2013488"},{"key":"9093_CR5","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1109\/TIT.1984.1056941","volume":"30","author":"D. Coppersmith","year":"1984","unstructured":"D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two. IEEE Trans. Inf. Theory\n                           30, 587\u2013594 (1984)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9093_CR6","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W. Diffie","year":"1976","unstructured":"W. Diffie, M. Hellman, New directions in cryptology. IEEE Trans. Inf. Theory\n                           22, 644\u2013654 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9093_CR7","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-3-540-48000-6_10","volume-title":"ASIACRYPT \u201999","author":"I. Duursma","year":"1999","unstructured":"I. Duursma, P. Gaudry, F. Morain, Speeding up the discrete log computation on curves with automorphisms, in ASIACRYPT \u201999. LNCS, vol.\u00a01716 (Springer, Berlin, 1999), pp.\u00a0103\u2013121"},{"key":"9093_CR8","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T. ElGamal","year":"1985","unstructured":"T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory\n                           31, 469\u2013472 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9093_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/3-540-46885-4_34","volume-title":"EUROCRYPT \u201989","author":"P. Flajolet","year":"1990","unstructured":"P. Flajolet, A.M. Odlyzko, Random mapping statistics, in EUROCRYPT \u201989. LNCS, vol.\u00a0434 (Springer, Berlin, 1990), pp.\u00a0329\u2013354"},{"key":"9093_CR10","doi-asserted-by":"crossref","first-page":"1699","DOI":"10.1090\/S0025-5718-99-01119-9","volume":"69","author":"R. Gallant","year":"2000","unstructured":"R. Gallant, R. Lambert, S. Vanstone, Improving the parallelized Pollard lambda search on binary anomalous curves. Math. Comput.\n                           69, 1699\u20131705 (2000)","journal-title":"Math. Comput."},{"key":"9093_CR11","series-title":"LNCS","first-page":"54","volume-title":"PKC \u201909","author":"M. Kim","year":"2009","unstructured":"M. Kim, J. Cheon, J. Hong, Subset-restricted random walks for Pollard rho method on \n                    \n                      \n                    \n                    $\\mathbf{F}_{p^{m}}$\n                  , in PKC \u201909. LNCS, vol.\u00a05443 (Springer, Berlin, 2009), pp.\u00a054\u201367"},{"key":"9093_CR12","series-title":"LNCS","first-page":"402","volume-title":"ANTS-VIII 2008","author":"J.H. Kim","year":"2008","unstructured":"J.H. Kim, R. Montenegro, Y. Peres, P. Tetali, A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm, in ANTS-VIII 2008. LNCS, vol.\u00a05011 (Springer, Berlin, 2008), pp.\u00a0402\u2013415"},{"key":"9093_CR13","volume-title":"The Art of Computer Programming, vol. II: Seminumerical Algorithms","author":"D. Knuth","year":"1969","unstructured":"D. Knuth, The Art of Computer Programming, vol. II: Seminumerical Algorithms (Addison-Wesley, Reading, 1969)"},{"key":"9093_CR14","volume-title":"The Art of Computer Programming, vol. III: Sorting and Searching","author":"D. Knuth","year":"1973","unstructured":"D. Knuth, The Art of Computer Programming, vol. III: Sorting and Searching (Addison-Wesley, Reading, 1973)"},{"key":"9093_CR15","volume-title":"Handbook of Applied Cryptography","author":"A.J. Menezes","year":"1997","unstructured":"A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of Applied Cryptography (CRC Press, Boca Raton, 1997)"},{"key":"9093_CR16","unstructured":"NIST, Digital signature standard, NIST. U.S. Department of Commerce. Federal Information Processing Standards Publication (FIPS PUB) 186, May 1994"},{"key":"9093_CR17","unstructured":"NIST, Recommendation for key management-part 1: General (revisited), \n                    http:\/\/csrc.nist.gov\/groups\/ST\/toolkit\/documents\/SP800-57Part1_3-8-07.pdf"},{"key":"9093_CR18","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.ipl.2004.01.016","volume":"90","author":"G. Nivasch","year":"2004","unstructured":"G. Nivasch, Cycle detection using a stack. Inf. Process. Lett.\n                           90, 135\u2013140 (2004)","journal-title":"Inf. Process. Lett."},{"key":"9093_CR19","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/TIT.1978.1055817","volume":"24","author":"S. Pohlig","year":"1978","unstructured":"S. Pohlig, M. Hellman, An improved algorithm for computing discrete logarithms over GF(p) and its cryptographic significance. IEEE Trans. Inf. Theory\n                           24, 106\u2013110 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"143","key":"9093_CR20","first-page":"918","volume":"32","author":"J.M. Pollard","year":"1978","unstructured":"J.M. Pollard, A\u00a0Monte Carlo method for index computation (modp). Math. Comput.\n                           32(143), 918\u2013924 (1978)","journal-title":"Math. Comput."},{"key":"9093_CR21","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s001450010010","volume":"13","author":"J.M. Pollard","year":"2000","unstructured":"J.M. Pollard, Kangaroos, monopoly and discrete logarithms. J.\u00a0Cryptol.\n                           13, 437\u2013447 (2000)","journal-title":"J.\u00a0Cryptol."},{"key":"9093_CR22","series-title":"LNCS","first-page":"429","volume-title":"EUROCRYPT \u201989","author":"J. Quisquater","year":"1989","unstructured":"J. Quisquater, J. Delescaille, How easy is collision search? Application to DES, in EUROCRYPT \u201989. LNCS, vol.\u00a0434 (Springer, Berlin, 1989), pp.\u00a0429\u2013434"},{"key":"9093_CR23","first-page":"65","volume":"6","author":"J. Sattler","year":"1985","unstructured":"J. Sattler, C. Schnorr, Generating random walks in groups. Ann. Univ. Sci. Budapest. Sect. Comput.\n                           6, 65\u201379 (1985)","journal-title":"Ann. Univ. Sci. Budapest. Sect. Comput."},{"issue":"167","key":"9093_CR24","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1090\/S0025-5718-1984-0744939-5","volume":"43","author":"C. Schnorr","year":"1984","unstructured":"C. Schnorr, H. Lenstra Jr., A Monte Carlo factoring algorithm with linear storage. Math. Comput.\n                           43(167), 289\u2013311 (1984)","journal-title":"Math. Comput."},{"key":"9093_CR25","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Sch\u00f6nhage","year":"1971","unstructured":"A. Sch\u00f6nhage, V. Strassen, Schnelle multiplikation Grobner zahlen. Computing\n                           7, 281\u2013292 (1971)","journal-title":"Computing"},{"issue":"2","key":"9093_CR26","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1137\/0211030","volume":"11","author":"R. Sedgewick","year":"1982","unstructured":"R. Sedgewick, T. Szymanski, A. Yao, The complexity of finding cycles in periodic functions. SIAM J. Comput.\n                           11(2), 376\u2013390 (1982)","journal-title":"SIAM J. Comput."},{"key":"9093_CR27","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1090\/pspum\/020\/0316385","volume":"20","author":"D. Shanks","year":"1971","unstructured":"D. Shanks, Class number, a theory of factorization and genera. Proc. Symp. Pure Math.\n                           20, 415\u2013440 (1971)","journal-title":"Proc. Symp. Pure Math."},{"key":"9093_CR28","unstructured":"V. Shoup, NTL: a library for doing number theory, Ver 5.5.1, \n                    http:\/\/shoup.net\/ntl\/"},{"key":"9093_CR29","series-title":"LNCS","first-page":"541","volume-title":"ANTS \u201998","author":"E. Teske","year":"1998","unstructured":"E. Teske, Speeding up Pollard\u2019s rho method for computing discrete logarithms, in ANTS \u201998. LNCS, vol.\u00a01423 (Springer, Berlin, 1998), pp.\u00a0541\u2013554"},{"key":"9093_CR30","doi-asserted-by":"crossref","first-page":"809","DOI":"10.1090\/S0025-5718-00-01213-8","volume":"70","author":"E. Teske","year":"2001","unstructured":"E. Teske, On random walks for Pollard\u2019s rho method. Math. Comput.\n                           70, 809\u2013825 (2001)","journal-title":"Math. Comput."},{"key":"9093_CR31","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0166-218X(02)00590-5","volume":"130","author":"E. Teske","year":"2003","unstructured":"E. Teske, Computing discrete logarithms with the parallelized kangaroo method. Disrete Appl. Math.\n                           130, 61\u201382 (2003)","journal-title":"Disrete Appl. Math."},{"key":"9093_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","volume":"12","author":"P. Oorschot van","year":"1999","unstructured":"P. van Oorschot, M. Wiener, Parallel collision search with cryptanalytic applications. J.\u00a0Cryptol.\n                           12, 1\u201328 (1999)","journal-title":"J.\u00a0Cryptol."},{"key":"9093_CR33","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00145-004-0221-0","volume":"18","author":"J. Gathen von\u00a0zur","year":"2005","unstructured":"J. von\u00a0zur Gathen, M. N\u00f6cker, Polynomial and normal bases for finite fields. J.\u00a0Cryptol.\n                           18, 337\u2013355 (2005)","journal-title":"J.\u00a0Cryptol."},{"key":"9093_CR34","series-title":"LNCS","first-page":"190","volume-title":"SAC \u201998","author":"M. Wiener","year":"1999","unstructured":"M. Wiener, R. Zuccherato, Fast attacks on elliptic curve cryptosystems, in SAC \u201998. LNCS, vol.\u00a01556 (Springer, Berlin, 1999), pp.\u00a0190\u2013200"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-010-9093-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-010-9093-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-010-9093-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-010-9093-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T08:49:33Z","timestamp":1586335773000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-010-9093-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,12]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9093"],"URL":"https:\/\/doi.org\/10.1007\/s00145-010-9093-7","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,12]]},"assertion":[{"value":"4 February 2010","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2010","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}