Abstract
Large integer decomposition is the most direct attack method of RSA public key encryption algorithm, and it is closely related to the security of RSA. Therefore, the problem of large integer decomposition has become a problem for cryptographers and mathematicians. The main purpose of this paper is to discuss the current research situation of large integer decomposition problem, analyze the basic principle and implementation method of the current mainstream large integer decomposition algorithm, and forecast the future research trend of large integer decomposition.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Li, D., Luo, M., Zhao, B.: Provably secure APK redevelopment authorization scheme in the standard model. Comput. Mater. Cortinua 56(3), 447–465 (2018)
Pomerance, C.: A tale of two sieves. Not. AMS 43(12), 1473–1485 (1996)
MathWorld Headline news. http://mathworld.wolfram.com/news/2003-12-05/rsa/. Accessed 24 Oct 2018
Factorization of RSA-180. https://eprint.iacr.org/2010/270.pdf,last. Accessed 24 Oct 2018
RSA-190 factored. https://mersenneforum.org/showpost.php?p=236114&postcount=1,last. Accessed 24 Oct 2018
MathWorld Headline news. http://mathworld.wolfram.com/news/2005-11-08/rsa-640/,last. Accessed 24 Oct 2018
RSA-210 factored. https://www.mersenneforum.org/showpost.php?p=354259,last. Accessed 24 Oct 2018
Factorization of RSA-704 with cado-nfs. https://eprint.iacr.org/2012/369.pdf,last. Accessed 24 Oct 2018
Factorization of RSA-220 with cado-nfs. https://members.loria.fr/PZimmermann/papers/rsa220.pdf,last. Accessed 24 Oct 2018
Factorization of a 768-bit RSA modules. https://eprint.iacr.org/2010/006.pdf,last. Accessed 24 Oct 2018
Pollard, J.M.: A Monte Carlo method for factorization. BIT Numer. Math. 15(3), 331–334 (1975)
Brent, R.P.: An improved Monte Carlo factorization algorithm. BIT Numer. Math. 20(2), 176–184 (1980)
Pollard, J.M.: Theorems of factorization and primality testing. In: Proceedings of the Cambridge Philosophical Society, vol. 76, no. 3, pp. 521–528 (1974)
Lenstra, H.W.: Factoring integers with elliptic curves. Ann. Math. 126(3), 64–73 (1987)
Dixon, J.D.: Asymptotically fast factorization of integers. Math. Comput. 36(153), 255–260 (1981)
Pomerance, C.: The quadratic sieve factoring algorithm. In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 169–182. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-39757-4_17
Lenstra, A.K., Lenstra, H.W. (eds.): The Development of the Number Field Sieve. LNM, vol. 1554. Springer, Heidelberg (1993). https://doi.org/10.1007/BFb0091534
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. In: 35th Annual Symposium on Foundations of Computer Science, pp. 124–134. IEEE Computer Society Press, Los Alamitos (1994)
Vandersypen, L.M.K., Steffen, M.: Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature 414(6866), 883–887 (2001)
Tang, X., Xu, J., Duan, B.: A memory-efficient simulation method of Grover’s search algorithm. Comput. Mater. Continua 57(2), 307–319 (2018)
Acknowledgments
This work is funded by the National Key Research and Development Plan (Grant No. 2018YFB0803504) and the National Natural Science Foundation of China (No. U1636215).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhang, X., Li, M., Jiang, Y., Sun, Y. (2019). A Review of the Factorization Problem of Large Integers. In: Sun, X., Pan, Z., Bertino, E. (eds) Artificial Intelligence and Security. ICAIS 2019. Lecture Notes in Computer Science(), vol 11635. Springer, Cham. https://doi.org/10.1007/978-3-030-24268-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-030-24268-8_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-24267-1
Online ISBN: 978-3-030-24268-8
eBook Packages: Computer ScienceComputer Science (R0)