Download pdf
Advancements and Prospects in Large Integer Factorization: A Comprehensive Review of the Number Field Sieve Method
- 1 Computer science and technology, Macau University of Science and Technology, Macau, China
* Author to whom correspondence should be addressed.
Abstract
The Number Field Sieve (NFS) stands as one of the most effective algorithms for the factorization of large integers, playing a critical role in cryptographic security, particularly in breaking RSA encryption systems. This review paper provides an in-depth analysis of NFS, highlighting its structure, key processes, and computational challenges. NFS is notably effective for integers larger than 110 digits and is recognized for its sub-exponential computational complexity, making it superior to other classical factorization algorithms. The core processes of NFS—polynomial selection, number pair sieving, matrix solving, and square root extraction—are systematically examined to illustrate their roles in factorization. This study also reviews the latest advancements in NFS, including improvements in polynomial selection methods and optimizations in sieving and matrix-solving stages, which have significantly enhanced the algorithm’s efficiency. Moreover, the paper discusses the future prospects of NFS, emphasizing the need for further optimization to reduce computational resource demands and increase practicality in large-scale applications. The ongoing evolution of NFS continues to push the boundaries of cryptographic analysis, driving future research towards even more efficient factorization methods.
Keywords
Number Field Sieve, RSA, algorithm.
[1]. Kudelić, R. (2024). On the Theory of Quantum and Towards Practical Computation. arXiv preprint arXiv:2403.09682.
[2]. Cheng, C., Xu, F., Pan, X. F., Wang, C., Fan, J., Yang, Y., ... & Zheng, J. S. Genetic Mapping of Serum Metabolome to Chronic Diseases Among Han Chinese.
[3]. Wang, Z., Li, Z., Ran, B., Liu, S., Wu, W., Ye, Y., ... & Li, J. (2023). Mid-cretaceous rapid denudation of Eastern Tibetan plateau: Insights from detrital records at the Southwestern corner of Sichuan basin. Frontiers in Earth Science, 11, 1113377.
[4]. Dong, P., Wang, L., Chen, Y., Wang, L., Liang, W., Wang, H., ... & Guo, F. (2024). Germplasm Resources and Genetic Breeding of Huang-Qi (Astragali Radix): A Systematic Review. Biology, 13(8).
[5]. Ahmed, N. (2024). Quantum Computing Algorithms for Integer Factorization: A Comparative Analysis. Modern Dynamics: Mathematical Progressions, 1(1), 6-9.
[6]. Zhu, X., Zhang, Y., Zhao, Z., & Zuo, J. (2019). Radio frequency sensing based environmental monitoring technology. In Proceedings of the Fourth International Workshop on Pattern Recognition (pp. 187-191). Springer.
[7]. Qureshi, F., Yusuf, M., Ahmed, S., Haq, M., Alraih, A. M., Hidouri, T., ... & Ibrahim, H. (2024). Advancements in sorption-based materials for hydrogen storage and utilization: A comprehensive review. Energy, 132855.
[8]. Zhang, Y., Xu, H., & Zhu, X. (2020). Detection and quantization technique of optical distributed acoustic coupling based on φ-OTDR. Journal of Shanghai Jiaotong University (Science), 25, 208-213.
[9]. Ho, H. T., Nguyen, L. V., Le, T. H. T., & Lee, O. J. (2024). Face Detection Using Eigenfaces: A Comprehensive Review. IEEE Access.
[10]. Zhang, Y., Zhao, H., Zhu, X., Zhao, Z., & Zuo, J. (2019). Strain measurement quantization technology based on DAS system. In 2019 IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC) (pp. 214-218). IEEE.
[11]. Letchumanan, I., Yunus, R. M., Mastar, M. S., & Karim, N. A. (2024). Advancements in electrocatalyst architecture for enhanced oxygen reduction reaction in anion exchange membrane fuel cells: A comprehensive review. International Journal of Hydrogen Energy.
[12]. Zhao, Z., Peng, Y., Zhu, X., Wei, X., & Wang, X. (2020). Research on prediction of electricity consumption in smart parks based on multiple linear regression. In 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference (ITAIC) (pp. 812-816). IEEE.
[13]. Kumar, S. L., Sureka, P., Sowmitha, A., Sentisenla, J., & Swathy, M. (2024). Recent advancements of hydroxyapatite and polyethylene glycol (PEG) composites for tissue engineering applications–A comprehensive review. European Polymer Journal, 113226.
[14]. Xu, H., Zhu, X., Zhao, Z., Wei, X., & Wang, X. (2020). Research of pipeline leak detection technology and application prospect of petrochemical wharf. In 2020 IEEE 9th Joint International Information Technology and Artificial Intelligence Conference (ITAIC) (pp. 263-271). IEEE.
[15]. Guo, R., Wang, F., Rhamdhani, M. A., Xu, Y., & Shen, W. (2024). Managing the surge: a comprehensive review of the entire disposal framework for retired lithium-ion batteries from electric vehicles. Journal of Energy Chemistry.
[16]. Zhu, X., Zhao, Z., Wei, X., & Wang, X. (2021). Action recognition method based on wavelet transform and neural network in wireless network. In Proceedings of the 2021 5th International Conference on Digital Signal Processing (pp. 60-65). IEEE.
[17]. Wang, R., Zhu, J., Wang, S., Wang, T., Huang, J., & Zhu, X. (2024). Multi-modal emotion recognition using tensor decomposition fusion and self-supervised multi-tasking. International Journal of Multimedia Information Retrieval, 13(4), 39.Gad I and Daoud S 2014 Int. J. Adv. Comput. Sci. Appl. 5(7) 178-185.
[18]. Raza, S., Hayat, A., Bashir, T., Chen, C., Shen, L., Orooji, Y., & Lin, H. (2024). Electrochemistry of 2D-materials for the remediation of environmental pollutants and alternative energy storage/conversion materials and devices, a comprehensive review. Sustainable Materials and Technologies, e00963.
[19]. Ji, W., Huang, X., Wang, S., & He, X. (2023). A Comprehensive Review of the Research of the “Eye–Brain–Hand” Harvesting System in Smart Agriculture. Agronomy, 13(9), 2237.
[20]. Zheng, Z., Zhou, J., & Zhu, Y. (2024). Computational approach inspired advancements of solid-state electrolytes for lithium secondary batteries: from first-principles to machine learning. Chemical Society Reviews.
[21]. Kong, F., & Chen, W. (2024). Carbon Dioxide Capture and Conversion Using Metal–Organic Framework (MOF) Materials: A Comprehensive Review. Nanomaterials, 14(16).Thomé E 2012 Proc. of the 2012 Int. Workshop on the Arithmetic of Finite Fields LNCS 7369 (Berlin: Springer) 208-224.
[22]. Tewari, C., Tatrari, G., Kumar, S., Pathak, M., Rawat, K. S., Kim, Y. N., ... & Sahoo, N. G. (2023). Can graphene-based composites and membranes solve current water purification challenges-a comprehensive review. Desalination, 116952.
[23]. Waqas, M., Hashim, S., Humphries, U. W., Ahmad, S., Noor, R., Shoaib, M., ... & Lin, H. A. (2023). Composting processes for agricultural waste management: a comprehensive review. Processes, 11(3), 731.
[24]. Tawonezvi, T., Nomnqa, M., Petrik, L., & Bladergroen, B. J. (2023). Recovery and recycling of valuable metals from spent lithium-ion batteries: A comprehensive review and analysis. Energies, 16(3), 1365.
[25]. Azami, M., Kazemi, Z., Moazen, S., Dubé, M., Potvin, M. J., & Skonieczny, K. (2024). A Comprehensive Review of Lunar-based Manufacturing and Construction. arXiv preprint arXiv:2408.05823.
[26]. Bavdekar, R., Chopde, E. J., Agrawal, A., Bhatia, A., & Tiwari, K. (2023, January). Post quantum cryptography: A review of techniques, challenges and standardizations. In 2023 International Conference on Information Networking (ICOIN)(pp. 146-151). IEEE.
[27]. Stocco, T. D., Zhang, T., Dimitrov, E., Ghosh, A., da Silva, A. M. H., Melo, W. C., ... & Lobo, A. O. (2023). Carbon nanomaterial-based hydrogels as scaffolds in tissue engineering: a comprehensive review. International Journal of Nanomedicine, 6153-6183.
[28]. Singh, R., Priya, H., Kumar, S. R., Trivedi, D., Prasad, N., Ahmad, F., ... & Rana, S. S. (2024). Gum Ghatti: A Comprehensive Review on Production, Processing, Remarkable Properties, and Diverse Applications. ACS omega, 9(9), 9974-9990.
Cite this article
Gao,J. (2024). Advancements and Prospects in Large Integer Factorization: A Comprehensive Review of the Number Field Sieve Method. Applied and Computational Engineering,110,115-121.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of CONF-MLA 2024 Workshop: Securing the Future: Empowering Cyber Defense with Machine Learning and Deep Learning
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).