{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T18:31:55Z","timestamp":1778351515718,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T00:00:00Z","timestamp":1527811200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61502481"],"award-info":[{"award-number":["61502481"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672019"],"award-info":[{"award-number":["61672019"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s10623-018-0492-3","type":"journal-article","created":{"date-parts":[[2018,6,1]],"date-time":"2018-06-01T07:44:42Z","timestamp":1527839082000},"page":"971-986","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A variant of the Galbraith\u2013Ruprai algorithm for discrete logarithms with improved complexity"],"prefix":"10.1007","volume":"87","author":[{"given":"Yuqing","family":"Zhu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1159-7597","authenticated-orcid":false,"given":"Jincheng","family":"Zhuang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hairong","family":"Yi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chang","family":"Lv","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongdai","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,1]]},"reference":[{"key":"492_CR1","unstructured":"Bos J.W., Kleinjung T., Lenstra A.K.: On the use of the negation map in the Pollard rho method. In: Algorithmic Number Theory Symposium-ANTS 2010, pp. 66\u201382. Springer, Berlin (2010)."},{"issue":"10","key":"492_CR2","doi-asserted-by":"publisher","first-page":"1547","DOI":"10.1016\/j.dam.2012.02.019","volume":"160","author":"SD Galbraith","year":"2012","unstructured":"Galbraith S.D., Holmes M.: A non-uniform birthday problem with applications to discrete logarithms. Discret. Appl. Math. 160(10), 1547\u20131560 (2012).","journal-title":"Discret. Appl. Math."},{"key":"492_CR3","unstructured":"Galbraith S.D., Ruprai R.S.: An improvement to the Gaudry\u2013Schost algorithm for multidimensional discrete logarithm problems. In: Proceedings of the 12th IMA International Conference on Cryptography and Coding, pp. 368\u2013382. Springer, Berlin (2009)."},{"key":"492_CR4","unstructured":"Galbraith S.D., Ruprai R.S.: Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval. In: Public Key Cryptography-PKC 2010, pp. 368\u2013383. Springer, Berlin (2010)."},{"key":"492_CR5","unstructured":"Galbraith S.D., Lin X., Scott M.: Endomorphisms for faster elliptic curve cryptography on a large class of curves. In: Advances in Cryptology-EUROCRYPT 2009, pp. 518\u2013535. Springer, Berlin (2009)."},{"issue":"282","key":"492_CR6","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1090\/S0025-5718-2012-02641-X","volume":"82","author":"SD Galbraith","year":"2013","unstructured":"Galbraith S.D., Pollard J.M., Ruprai R.S.: Computing discrete logarithms in an interval. Math. Comput. 82(282), 1181\u20131195 (2013).","journal-title":"Math. Comput."},{"issue":"232","key":"492_CR7","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1090\/S0025-5718-99-01119-9","volume":"69","author":"R Gallant","year":"2000","unstructured":"Gallant R., Lambert R., Vanstone S.: Improving the parallelized Pollard lambda search on anomalous binary curves. Math. Comput. 69(232), 1699\u20131705 (2000).","journal-title":"Math. Comput."},{"key":"492_CR8","unstructured":"Gallant R., Lambert R., Vanstone S.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: Advances in Cryptology-CRYPTO 2001, pp. 190\u2013200. Springer, Berlin (2001)."},{"key":"492_CR9","unstructured":"Gaudry P., Schost \u00c9.: A low-memory parallel version of Matsuo, Chao, and Tsujii\u2019s algorithm. In: Algorithmic Number Theory Symposium-ANTS 2004, pp. 208\u2013222. Springer, Berlin (2004)."},{"key":"492_CR10","unstructured":"Gennaro R.: An improved pseudo-random generator based on discrete log. In: Advances in Cryptology-CRYPTO 2000, pp. 469\u2013481. Springer, Berlin (2000)."},{"key":"492_CR11","unstructured":"Gopalakrishnan K., Th\u00e9riault N., Yao C.: Solving discrete logarithms from partial knowledge of the key. In: Progress in Cryptology-INDOCRYPT 2007, pp. 224\u2013237. Springer, Berlin (2007)."},{"key":"492_CR12","unstructured":"Koblit N.: CM-curves with good cryptographic properties. In: Advances in Cryptology-CRYPTO\u201991, pp. 279\u2013287. Springer, Heidelberg (1992)."},{"key":"492_CR13","unstructured":"Lim C.H., Lee P.J.: A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Advances in Cryptology-CRYPTO\u201997, pp. 249\u2013263. Springer, Berlin (1997)."},{"key":"492_CR14","unstructured":"Liu W.: Improved algorithms for the 2-dimensional discrete logarithm problem with equivalence classes. Master\u2019s thesis, University of Auckland (2010)."},{"key":"492_CR15","unstructured":"Longa P., Sica F.: Four-dimensional Gallant\u2013Lambert\u2013Vanstone scalar multiplication. In: Advances in Cryptology-ASIACRYPT 2012, pp. 718\u2013739. Springer, Berlin (2012)."},{"key":"492_CR16","unstructured":"Matsuo K., Chao J., Tsujii S.: An improved baby step giant step algorithm for point counting of hyperelliptic curves over finite fields. In: Algorithmic Number Theory Symposium-ANTS 2002, pp. 461\u2013474. Springer, Berlin (2002)."},{"key":"492_CR17","unstructured":"Patel S., Sundaram G.S.: An efficient discrete log pseudo random generator. In: Advances in Cryptology-CRYPTO\u201998, pp. 304\u2013317. Springer, Berlin (1998)."},{"issue":"143","key":"492_CR18","first-page":"918","volume":"32","author":"JM Pollard","year":"1978","unstructured":"Pollard J.M.: Monte Carlo methods for index computation (mod \n                    \n                      \n                    \n                    $$p$$\n                    \n                      \n                        p\n                      \n                    \n                  ). Math. Comput. 32(143), 918\u2013924 (1978).","journal-title":"Math. Comput."},{"key":"492_CR19","unstructured":"Quisquater J.J., Delescaille J.P.: How easy is collision search? Application to DES. In: Advances in Cryptology- EUROCRYPT\u201989, pp. 429\u2013434. Springer, Heidelberg (1990)."},{"key":"492_CR20","unstructured":"Shanks D.: Class number, a theory of factorization, and genera. In: Proceedings of Symposia in Pure Mathematics, pp. 415\u2013440 (1971)."},{"key":"492_CR21","unstructured":"Smith B.: Families of fast elliptic curves from \n                    \n                      \n                    \n                    $$\\mathbb{Q}$$\n                    \n                      \n                        Q\n                      \n                    \n                  -curves. In: Advances in Cryptology-ASIACRYPT 2013, pp. 61\u201378. Springer, Berlin (2013)."},{"issue":"234","key":"492_CR22","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1090\/S0025-5718-00-01213-8","volume":"70","author":"E Teske","year":"2001","unstructured":"Teske E.: On random walks for Pollard\u2019s rho method. Math. Comput. 70(234), 809\u2013825 (2001).","journal-title":"Math. Comput."},{"key":"492_CR23","unstructured":"van Oorschot P.C., Wiener M.J.: On Diffie-Hellman key agreement with short exponents. In: Advances in Cryptology-EUROCRYPT\u201996, pp. 332\u2013343. Springer, Berlin (1996)."},{"issue":"1","key":"492_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00003816","volume":"12","author":"PC Oorschot van","year":"1999","unstructured":"van Oorschot P.C., Wiener M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1\u201328 (1999).","journal-title":"J. Cryptol."},{"issue":"3","key":"492_CR25","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10623-005-1598-y","volume":"38","author":"A Weng","year":"2006","unstructured":"Weng A.: A low-memory algorithm for point counting on picard curves. Des. Codes Cryptogr. 38(3), 383\u2013393 (2006).","journal-title":"Des. Codes Cryptogr."},{"key":"492_CR26","unstructured":"Wiener M.J., Zuccherato R.J.: Faster attacks on elliptic curve cryptosystems. In: Selected Areas in Cryptography\u2013SAC\u201998, pp. 190\u2013200. Springer, Berlin (1998)."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-018-0492-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10623-018-0492-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-018-0492-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T02:49:32Z","timestamp":1559357372000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-018-0492-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,1]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["492"],"URL":"https:\/\/doi.org\/10.1007\/s10623-018-0492-3","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,1]]},"assertion":[{"value":"11 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 April 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}