Research ArticleOpen AccessGoogle Scholar indexed

Kernel Factor Pairs for Semiprime Factorization

¹ Department of Computer Science, City University of Hong Kong, Hong Kong, China
² Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, USA
³ Hong Kong Institute for Advanced Study and Department of Data Science, City University of Hong Kong, Hong Kong, China
⁴ Department of Systems Engineering, City University of Hong Kong, Hong Kong, China

Advances in Pure Mathematics·Volume 15 (2025)·Pages 629–642·Published 1 September 2025·DOI10.4236/apm.2025.159032

Abstract

We show that any semiprime number can be factorized as the product of two prime numbers in the form of a kernel factor pair of two out of 48 root numbers. Specifically, each natural number without factors of 2, 3, 5 and 7 can be traced back to one unique number of a total of 48 root numbers falling in [ 11 , 220 ] in periods of length 210. Unlike the commonly used sieve-based methods, under no preconditions, will the proposed kernel-factor-pair-based algorithm be guaranteed to successfully factorize any given semiprime α by searching over 1 / 2 log α binary variables. The proposed method is well structured for factorization in breaking RSA encryption and is readily applicable for parallel computation.

KeywordsSemiprimesFactorizationFactor-Pairs Table

Zagier, D. (1977) The First 50 Million Prime Numbers. The Mathematical Intelligencer , 1, 7-19. https://doi.org/10.1007/bf03351556
Zagier, D. (1997) Newman’s Short Proof of the Prime Number Theorem. The American Mathematical Monthly , 104, 705-708. https://doi.org/10.1080/00029890.1997.11990704
Dickson, L.E. (2005) History of the Theory of Numbers, Volume II: Diophantine Analysis. Dover Publications.
Li, H., Huang, Y., Fang, S. and Kuo, W. (2021) A Prime-Logarithmic Method for Optimal Reliability Design. IEEE Transactions on Reliability , 70, 146-162. https://doi.org/10.1109/tr.2020.3020597
Li, H., Fang, S., Lin, B.M.T. and Kuo, W. (2023) Unifying Colors by Primes. Light : Science & Applications , 12, Article No. 32. https://doi.org/10.1038/s41377-023-01073-x
Konheim, A.G. (2006) Computer Security and Cryptography. Wiley. https://doi.org/10.1002/0470083980
Li, D., Luo, M., Zhao, B. and Che, X. (2018) Provably Secure APK Redevelopment Authorization Scheme in the Standard Model. Computers , Materials & Continua , 56, 447-465. https://doi.org/10.3970/cmc.2018.03692
RSA Laboratories (2013) The RSA Factoring Challenge. https://web.archive.org/web/20130921043459/ http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge.htm
Shor, P.W. (1997) Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing , 26, 1484-1509. https://doi.org/10.1137/s0097539795293172
Shoshina, A.V., Borzunov, G.I. and Ivanova, E.Y. (2021) Application of Bio-Inspired Algorithms to the Cryptanalysis of Asymmetric Ciphers on the Basis of Composite Number. 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering ( ElConRus ), St. Petersburg, 26-29 January 2021, 2399-2403. https://doi.org/10.1109/elconrus51938.2021.9396242
Upadhyay, S. and Gupta, V.K. (2022) A Literature Review on the Concept of Cryptography and RSA Algorithm. International J of Advance and Innovative Research , 9, 237-240.
Vandersypen, L.M.K., Steffen, M., Breyta, G., Yannoni, C.S., Sherwood, M.H. and Chuang, I.L. (2001) Experimental Realization of Shor’s Quantum Factoring Algorithm Using Nuclear Magnetic Resonance. Nature , 414, 883-887. https://doi.org/10.1038/414883a
Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thome, E. and Zimmermann, P. (2022) The State of the Art in Integer Factoring and Breaking Public-Key Cryptography. IEEE Security & Privacy , 20, 80-86. https://doi.org/10.1109/msec.2022.3141918

Menu

Kernel Factor Pairs for Semiprime Factorization

Abstract

References (29)