{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:58:03Z","timestamp":1764997083831},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2016,4,9]],"date-time":"2016-04-09T00:00:00Z","timestamp":1460160000000},"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":["AAECC"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00200-016-0291-x","type":"journal-article","created":{"date-parts":[[2016,4,9]],"date-time":"2016-04-09T03:40:26Z","timestamp":1460173226000},"page":"493-521","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Computational hardness of IFP and ECDLP"],"prefix":"10.1007","volume":"27","author":[{"given":"Masaya","family":"Yasuda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Shimoyama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Kogure","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tetsuya","family":"Izu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,9]]},"reference":[{"key":"291_CR1","unstructured":"ANSI X9.62: Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA) (1999)"},{"key":"291_CR2","doi-asserted-by":"crossref","unstructured":"Aoki, K., Franke, J., Kleinjung, T., Lenstra, A.K., Osvik, D.A.: A kilobit special number field sieve factorization. In: Advances in Cryptology-ASIACRYPT 2007. Springer LNCS 4833, pp. 1-12 (2007)","DOI":"10.1007\/978-3-540-76900-2_1"},{"key":"291_CR3","unstructured":"Aoki, K., Kida, Y., Shimoyama T., Ueda, H.: GNFS factoring statistics of RSA-100, 110, ..., 150, IACR ePrint Archive, 2004\/095. Available at https:\/\/eprint.iacr.org\/2004\/095 (2004)"},{"key":"291_CR4","unstructured":"Bailey, D., Baldwin, B., Batina, L., Bernstein, D., Birkner, P., Bos, J., van Damme, G., de Meulenaer, G., Fan, J., G\u00fcneysu, T., Gurkaynak, F., Kleinjung, T., Lange, T., Mentens, N., Paar, C., Regazzoni, F., Schwabe P., Uhsadel, L.: The Certicom challenges ECC2-X, IACR ePrint Archive, 2009\/466. Available at http:\/\/eprint.iacr.org\/2009\/466 (2009)"},{"key":"291_CR5","unstructured":"Bailey et al., D.: Breaking ECC2K-130, IACR ePrint Archive, 2009\/541. Available at http:\/\/eprint.iacr.org\/2009\/541 (2009)"},{"key":"291_CR6","unstructured":"Bahr, F., B\u00f6hm, M., Franke J., Kleinjung, T.: Factorization of RSA-200. Available at http:\/\/www.loria.fr\/ zimmerma\/records\/rsa200 (2005)"},{"key":"291_CR7","doi-asserted-by":"crossref","unstructured":"Bernstein, D., Chen, H., Cheng, C., Lange, T., Niederhagen, R., Schwabe, P., Yang, B.: ECC2K-130 on NVIDIA GPUs. In: Progress in Cryptology-INDOCRYPT 2010. Springer LNCS 6498, pp. 328-344 (2010)","DOI":"10.1007\/978-3-642-17401-8_23"},{"key":"291_CR8","doi-asserted-by":"crossref","unstructured":"Bernstein, D., Lange, T., Schwabe, P.: On the correct use of the negation map in the Pollard rho method. In: Public Key Cryptography-PKC 2011. Springer LNCS 6571, pp. 128-146 (2011)","DOI":"10.1007\/978-3-642-19379-8_8"},{"key":"291_CR9","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107360211","volume-title":"Elliptic Curves in Cryptography","author":"I Blake","year":"1999","unstructured":"Blake, I., Seroussi, G., Smart, N.: Elliptic Curves in Cryptography. Cambridge University Press, Cambridge (1999)"},{"key":"291_CR10","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1090\/S0025-5718-1981-0606520-5","volume":"36","author":"R Brent","year":"1981","unstructured":"Brent, R., Pollard, J.: Factorization of the eighth Fermat number. Math. Comput. 36, 627\u2013630 (1981)","journal-title":"Math. Comput."},{"key":"291_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-314X(83)90002-1","volume":"17","author":"ER Canfield","year":"1983","unstructured":"Canfield, E.R., Erdos, P., Pomerance, C.: On a problem of Oppenheim concerning factorisatio numerorum. J. Number Theory 17, 1\u201328 (1983)","journal-title":"J. Number Theory"},{"key":"291_CR12","unstructured":"Certicom: Certicom ECC challenge. Available at http:\/\/www.certicom.jp\/images\/pdfs\/cert_ecc_challenge (1997)"},{"key":"291_CR13","unstructured":"Certicom: Curves list. Available at http:\/\/www.certicom.jp\/index.php\/curves-list (1997)"},{"key":"291_CR14","unstructured":"Childers, G.: Factorization of a $$1061$$ 1061 -bit number by the special number field sieve. In: IACR ePrint Archive, 2012\/144. Available at http:\/\/eprint.iacr.org\/2012\/444 (2012)"},{"key":"291_CR15","unstructured":"CRYPTREC: CRYPTREC Report 2006. Available at http:\/\/www.cryptrec.go.jp\/report\/c06_wat_final (2006)"},{"key":"291_CR16","unstructured":"ECRYPT II: ECRYPT II report on key sizes. Available at http:\/\/www.keylength.com\/en\/3\/ (2011)"},{"key":"291_CR17","unstructured":"EPFL IC LACAL.: PlayStation 3 computing breaks $$2^{60}$$ 2 60 barrier 112-bit prime ECDLP solved. Available at http:\/\/lacal.epfl.ch\/112bit_prime (2009)"},{"key":"291_CR18","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re, J.C., Perret, L., Petit, C., Renault, G.: Improving the complexity of index calculus algorithms in elliptic curves over binary fields. In: Advances in Cryptology-EUROCRYPT 2012 Springer LNCS 7237, pp. 27-44 (2012)","DOI":"10.1007\/978-3-642-29011-4_4"},{"key":"291_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139012843","volume-title":"Mathematics of Public Key Cryptography","author":"SD Galbraith","year":"2012","unstructured":"Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press, Cambridge (2012)"},{"key":"291_CR20","doi-asserted-by":"crossref","unstructured":"Galbraith, S.D., Ruprail, R.S.: Using equivalence classes to accelerate solving the discrete logarithm problem in a short interval. In: Public Key Cryptography-PKC 2010. Springer LNCS 6056, pp. 368-386 (2010)","DOI":"10.1007\/978-3-642-13013-7_22"},{"key":"291_CR21","doi-asserted-by":"crossref","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 binary anomalous curves. Math. Comput. 69, 1699\u20131705 (2000)","journal-title":"Math. Comput."},{"key":"291_CR22","doi-asserted-by":"crossref","first-page":"1498","DOI":"10.1109\/TC.2008.80","volume":"57","author":"T G\u00fcneysu","year":"2008","unstructured":"G\u00fcneysu, T., Kasper, T., Novotn\u00fd, M., Paar, C., Rupp, A.: Cryptanalysis with COPACOBANA. Trans. Comput. 57, 1498\u20131513 (2008)","journal-title":"Trans. Comput."},{"key":"291_CR23","unstructured":"Granlund, T.: Instruction latencies and throughput for AMD and Intel x86 processors (2012-02-13 version). Available at http:\/\/gmplib.org\/ tege\/x86-timing"},{"key":"291_CR24","volume-title":"Guide to Elliptic Curve Cryptography","author":"D Hankerson","year":"2004","unstructured":"Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography. Springer Professional Computing, New York (2004)"},{"key":"291_CR25","unstructured":"Harley, R.: Elliptic curve discrete logarithms project. Available at http:\/\/pauillac.inria.fr\/ harley\/ecdl\/"},{"key":"291_CR26","first-page":"364","volume":"2007","author":"T Izu","year":"2007","unstructured":"Izu, T., Kogure, J., Shimoyama, T.: CAIRN 2: an FPGA implementation of the sieving step in the number field sieve method. Cryptogr. Hardw. Embed. Syst. 2007, 364\u2013377 (2007)","journal-title":"Cryptogr. Hardw. Embed. Syst."},{"key":"291_CR27","unstructured":"Kleinjung, T.: Estimates for factoring 1024-bit integers. In: Securing Cyberspace: Applications and Foundations of Cryptography and Computer Security, Workshop IV: Special purpose hardware for cryptography: Attacks and Applications, slides are available at http:\/\/www.ipam.ucla.edu\/schedule.aspx?pc=scws4 (2006)"},{"key":"291_CR28","unstructured":"Kleinjung, T.: Evaluation of complexity of mathematical algorithms. CRYPTREC technical report No. 0601 in FY2006. Available at http:\/\/www.cryptrec.jp\/estimation.html (2007)"},{"key":"291_CR29","doi-asserted-by":"crossref","unstructured":"Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thom\u00e9, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., te Riele, H., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA modulus, Advances in Cryptology-CRYPTO 2010. Springer LNCS 6223, pp. 333-350 (2010)","DOI":"10.1007\/978-3-642-14623-7_18"},{"issue":"1","key":"291_CR30","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s10586-010-0149-0","volume":"15","author":"T Kleinjung","year":"2012","unstructured":"Kleinjung, T., Bos, J.W., Lenstra, A.K., Osvik, D.A., Aoki, K., Contini, S., Franke, J., Thom\u00e9, E., Jermini, P., Thi\u00e9mard, M., Leyland, P., Montgomery, P., Timofeev, A., Stockinger, H.: A heterogeneous computing environment to solve the 768-bit RSA. Clust. Comput. 15(1), 53\u201368 (2012)","journal-title":"Clust. Comput."},{"key":"291_CR31","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","volume":"48","author":"N Koblitz","year":"1987","unstructured":"Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48, 203\u2013209 (1987)","journal-title":"Math. Comput."},{"key":"291_CR32","doi-asserted-by":"crossref","unstructured":"Lenstra, A., Lenstra, H., Manasse M., Pollard, J.: The number field sieve. In: Symposium on Theory of Computing-STOC 1990, ACM, pp. 564-572 (1990)","DOI":"10.1145\/100216.100295"},{"key":"291_CR33","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/s00145-001-0009-4","volume":"14","author":"A Lenstra","year":"2001","unstructured":"Lenstra, A., Verheul, E.: Selecting cryptographic key sizes. J. Cryptol. 14, 255\u2013293 (2001)","journal-title":"J. Cryptol."},{"key":"291_CR34","doi-asserted-by":"crossref","first-page":"1639","DOI":"10.1109\/18.259647","volume":"39","author":"A Menezes","year":"1993","unstructured":"Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Trans. Inf. Theory 39, 1639\u20131646 (1993)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"291_CR35","doi-asserted-by":"crossref","unstructured":"Miller, V.S.: Use of elliptic curves in cryptography. In: Advances in Cryptology-CRYPTO 1985. Springer LNCS 218, pp. 417-426 (1986)","DOI":"10.1007\/3-540-39799-X_31"},{"key":"291_CR36","unstructured":"NESSIE: NESSIE security report, February 2003"},{"key":"291_CR37","unstructured":"NIST Special publication 800-57. Available at http:\/\/csrc.nist.gov\/publications\/nistpubs\/800-57\/sp800-57-Part1-revised2_Mar08-2007"},{"key":"291_CR38","doi-asserted-by":"crossref","unstructured":"Orman, H., Hoffman, P.: Determining strengths for public keys used for exchanging symmetric keys. IETF RFC 3766\/BCP 86, April 2004","DOI":"10.17487\/rfc3766"},{"key":"291_CR39","first-page":"918","volume":"32","author":"J Pollard","year":"1978","unstructured":"Pollard, J.: Monte Carlo methods for index computation mod $$p$$ p . Math. Comput. 32, 918\u2013924 (1978)","journal-title":"Math. Comput."},{"key":"291_CR40","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R Rivest","year":"1978","unstructured":"Rivest, R., Shamir, A., Adelman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"key":"291_CR41","unstructured":"RSA Laboratories: A cost-based security analysis of symmetric and asymmetric key lengths. RSA Labs Bulletin, no. 13, April 2000 (Revised November 2001)"},{"key":"291_CR42","unstructured":"RSA Laboratories: The RSA challenge numbers. Available at http:\/\/japan.emc.com\/emc-plus\/rsa-labs\/historical\/the-rsa-challenge-numbers.htm"},{"key":"291_CR43","first-page":"81","volume":"47","author":"T Satoh","year":"1998","unstructured":"Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Univ. Sancti Pauli 47, 81\u201392 (1998)","journal-title":"Comment. Math. Univ. Sancti Pauli"},{"key":"291_CR44","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1090\/S0025-5718-98-00887-4","volume":"67","author":"I Semaev","year":"1998","unstructured":"Semaev, I.: Evaluation of discrete logarithms in a group of $$p$$ p -torsion points of an elliptic curve in characteristic $$p$$ p . Math. Comput. 67, 353\u2013356 (1998)","journal-title":"Math. Comput."},{"key":"291_CR45","doi-asserted-by":"crossref","unstructured":"Shamir, A.: Factoring large numbers with the TWINKLE device (extended abstract). In: Cryptographic Hardware and Embedded Systems-CHES 1999. Springer LNCS 1717, pp. 2-12 (1999)","DOI":"10.1007\/3-540-48059-5_2"},{"key":"291_CR46","doi-asserted-by":"crossref","unstructured":"Shamir, A., Tromer, E.: Factoring large numbers with the TWIRL Device. In: Advances in Cryptology-CRYPTO 2003. Springer LNCS 2729, pp. 1-26 (2003)","DOI":"10.1007\/978-3-540-45146-4_1"},{"key":"291_CR47","first-page":"110","volume":"12","author":"NP Smart","year":"1999","unstructured":"Smart, N.P.: The discrete logarithm problem on elliptic curves of trace one. J. Cryptol. 12, 110\u2013125 (1999)","journal-title":"J. Cryptol."},{"key":"291_CR48","doi-asserted-by":"crossref","unstructured":"Teske, E.: Speeding up Pollard\u2019s rho method for computing discrete logarithms. In: Algorithmic Number Theory-ANTS III. Springer LNCS 1423, pp. 541-554 (1998)","DOI":"10.1007\/BFb0054891"},{"key":"291_CR49","doi-asserted-by":"crossref","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, 809\u2013825 (2001)","journal-title":"Math. Comput."},{"key":"291_CR50","doi-asserted-by":"crossref","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\u201328 (1999)","journal-title":"J. Cryptol."},{"key":"291_CR51","doi-asserted-by":"crossref","unstructured":"Wiener, M.J., Zuccherato, R.J.: Fast attacks on elliptic curve cryptosystems. In: Selected Areas in Cryptology-SAC 1998. Springer LNCS 1556, pp. 190-200 (1999)","DOI":"10.1007\/3-540-48892-8_15"},{"issue":"2011B\u2014-3","key":"291_CR52","first-page":"107","volume":"3","author":"M Yasuda","year":"2011","unstructured":"Yasuda, M., Izu, T., Shimoyama, T., Kogure, J.: On random walks of Pollard\u2019s rho method for the ECDLP on Koblitz curves. J. Math. Ind. 3(2011B\u2014-3), 107\u2013112 (2011)","journal-title":"J. Math. Ind."},{"key":"291_CR53","doi-asserted-by":"crossref","unstructured":"Yasuda, M., Shimoyma, T., Kogure, J., Izu, T.: On the strength comparison of the ECDLP and the IFP. In: Security and Cryptography for Networks-SCN 2012. Springer LNCS 7485, pp. 302-325 (2012)","DOI":"10.1007\/978-3-642-32928-9_17"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-016-0291-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00200-016-0291-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-016-0291-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-016-0291-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T11:22:28Z","timestamp":1567768948000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00200-016-0291-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,9]]},"references-count":53,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["291"],"URL":"https:\/\/doi.org\/10.1007\/s00200-016-0291-x","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,4,9]]}}}