{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:25:09Z","timestamp":1775039109967,"version":"3.50.1"},"reference-count":75,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T00:00:00Z","timestamp":1636675200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JCP"],"abstract":"<jats:p>Semi-prime factorization is an increasingly important number theoretic problem, since it is computationally intractable. Further, this property has been applied in public-key cryptography, such as the Rivest\u2013Shamir\u2013Adleman (RSA) encryption systems for secure digital communications. Hence, alternate approaches to solve the semi-prime factorization problem are proposed. Recently, Pythagorean tuples to factor semi-primes have been explored to consider Fermat\u2019s Christmas theorem, with the two squares having opposite parity. This paper is motivated by the property that the integer separating these two squares being odd reduces the search for semi-prime factorization by half. In this paper, we prove that if a Pythagorean quadruple is known and one of its squares represents a Pythagorean triple, then the semi-prime is factorized. The problem of semi-prime factorization is reduced to the problem of finding only one such sum of three squares to factorize a semi-prime. We modify the Lebesgue identity as the sum of four squares to obtain four sums of three squares. These are then expressed as four Pythagorean quadruples. The Brahmagupta\u2013Fibonacci identity reduces these four Pythagorean quadruples to two Pythagorean triples. The greatest common divisors of the sides contained therein are the factors of the semi-prime. We then prove that to factor a semi-prime, it is sufficient that only one of these Pythagorean quadruples be known. We provide the algorithm of our proposed semi-prime factorization method, highlighting its complexity and comparative advantage of the solution space with Fermat\u2019s method. Our algorithm has the advantage when the factors of a semi-prime are congruent to 1 modulus 4. Illustrations of our method for real-world applications, such as factorization of the 768-bit number RSA-768, are established. Further, the computational viabilities, despite the mathematical constraints and the unexplored properties, are suggested as opportunities for future research.<\/jats:p>","DOI":"10.3390\/jcp1040033","type":"journal-article","created":{"date-parts":[[2021,11,12]],"date-time":"2021-11-12T08:10:22Z","timestamp":1636704622000},"page":"660-674","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["New Semi-Prime Factorization and Application in Large RSA Key Attacks"],"prefix":"10.3390","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7021-4774","authenticated-orcid":false,"given":"Anthony","family":"Overmars","sequence":"first","affiliation":[{"name":"Department of Information Technology, Melbourne Polytechnic, 77 St. Georges Rd., Preston, VIC 3072, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2772-133X","authenticated-orcid":false,"given":"Sitalakshmi","family":"Venkatraman","sequence":"additional","affiliation":[{"name":"Department of Information Technology, Melbourne Polytechnic, 77 St. Georges Rd., Preston, VIC 3072, Australia"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Overmars, A., and Venkatraman, S. (2019). A Fast Factorisation of Semi-Primes Using Sum of Squares. Math. Comput. Appl., 24.","DOI":"10.3390\/mca24020062"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Moreno, C.J., and Wagstaff, S.S. (2005). Sums of Squares of Integers, Chapman and Hall\/CRC Press. [1st ed.].","DOI":"10.1201\/9781420057232"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1093\/qmath\/hay035","article-title":"Sums of Kloosterman Sums Over Primes in an Arithmetic Progression","volume":"70","author":"Dunn","year":"2019","journal-title":"Q. J. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1093\/qmath\/os-6.1.205","article-title":"On the Normal Number of Prime Factors of P-1 and Some Related Problems Concerning Euler\u2019s \u00d8-Function","volume":"os-6","year":"1935","journal-title":"Q. J. Math."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1017\/S0305004100049252","article-title":"Theorems on factorization and primality testing","volume":"76","author":"Pollard","year":"1974","journal-title":"Proc. Camb. Philos. Soc."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"023107","DOI":"10.1063\/1.4975761","article-title":"Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines","volume":"27","author":"Traversa","year":"2017","journal-title":"Chaos Interdiscip. J. Nonlinear Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1287\/ited.2017.0193","article-title":"Puzzle\u2014Solving the n-Fractions Puzzle as a Constraint Programming Problem","volume":"19","author":"Malapert","year":"2018","journal-title":"INFORMS Trans. Educ."},{"key":"ref_8","unstructured":"Rescorla, E. (2001). SSL and TLS: Designing and Building Secure Systems, Addison-Wesley Reading."},{"key":"ref_9","unstructured":"Schneier, B. (1996). Applied Cryptography, John Wiley & Sons, Inc.. [2nd ed.]."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2922","DOI":"10.1109\/TIT.2007.901248","article-title":"Dual RSA and Its Security Analysis","volume":"53","author":"Sun","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1112\/blms\/28.4.351","article-title":"Turning Euler\u2019s Factoring Method into a Factoring Algorithm","volume":"28","author":"McKee","year":"1996","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref_13","first-page":"144","article-title":"A One-Sentence Proof That Every Prime p \u2261 1 (mod 4) Is a Sum of Two Squares","volume":"97","author":"Zagier","year":"1990","journal-title":"Am. Math. Mon."},{"key":"ref_14","unstructured":"Li, S. (2013). The Sum of Two Squares, Cornell University Press."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Agarwal, R.P. (2020). Pythagorean Triples before and after Pythagoras. Computation, 8.","DOI":"10.3390\/computation8030062"},{"key":"ref_16","first-page":"203","article-title":"Twenty years of attacks on the RSA cryptosystem","volume":"46","author":"Boneh","year":"1999","journal-title":"Not. Am. Math. Soc. (AMS)"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Grossklags, J., and Preneel, B. (2017). Factoring as a Service. Financial Cryptography and Data Security. FC 2016. Lecture Notes in Computer Science, Springer.","DOI":"10.1007\/978-3-662-54970-4"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Durumeric, Z., Kasten, J., Bailey, M., and Halderman, J.A. (2013, January 23\u201325). Analysis of the HTTPS certificate ecosystem. Proceedings of the 13th Internet Measurement Conference, Barcelona, Spain.","DOI":"10.1145\/2504730.2504755"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1109\/18.54902","article-title":"Cryptanalysis of short RSA secret exponents","volume":"160","author":"Wiener","year":"1990","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","first-page":"333","article-title":"Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm","volume":"62","author":"Coppersmith","year":"1994","journal-title":"Math. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer, J., and May, A. (2003). New Partial Key Exposure Attacks on RSA. Crypto 2003, LNCS, Springer.","DOI":"10.1007\/978-3-540-45146-4_2"},{"key":"ref_22","first-page":"111","article-title":"Cryptanalysis of RSA with Private Key D Less than N^0.292","volume":"Volume 1592","author":"Boneh","year":"1999","journal-title":"Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques"},{"key":"ref_23","unstructured":"Heninger, N., Durumeric, Z., Wustrow, E., and Halderman, J.A. (2012, January 8\u201310). Mining your Ps and Qs: Detection of widespread weak keys in network devices. Proceedings of the 21st USENIX Security Symposium, Bellevue, WA, USA."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Adrian, D., Bhargavan, K., Durumeric, Z., Gaudry, P., Green, M., Halderman, J.A., Heninger, N., Springall, D., Thom\u00e9, E., and Valenta, L. (2015, January 12\u201316). Imperfect forward secrecy: How Diffie-Hellman Fails in Practice. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.","DOI":"10.1145\/2810103.2813707"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Nemec, M., Sys, M., Svenda, P., Klinec, D., and Matyas, V. (November, January 30). The Return of Coppersmith\u2019s Attack: Practical Factorization of Widely Used RSA Moduli. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA.","DOI":"10.1145\/3133956.3133969"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1090\/S0002-9904-1931-05271-X","article-title":"On Factoring Large Numbers","volume":"37","author":"Lehmer","year":"1931","journal-title":"Bull. Am. Math. Soc."},{"key":"ref_27","first-page":"183","article-title":"A Method of Factoring and the Factorization of F7","volume":"29","author":"Morrison","year":"1975","journal-title":"Math. Comput. Am. Math. Soc."},{"key":"ref_28","first-page":"99","article-title":"Implementation of the Continued Fraction Integer Factoring Algorithm","volume":"37","author":"Pomerance","year":"1983","journal-title":"Congr. Numer."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF01933667","article-title":"A Monte Carlo method for factorization","volume":"Volume 15","author":"Pollard","year":"1975","journal-title":"BIT Numerical Mathematics"},{"key":"ref_30","unstructured":"Pomerance, C. (1985). The Quadratic Sieve Factoring Algorithm. Advances in Cryptology: EUROCRYPT\u201984, Springer."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Kameswari, P.A., and Jyotsna, L. (2018). An Attack Bound for Small Multiplicative Inverse of \u03c6(N) mod e with a Composed Prime Sum p + q Using Sublattice Based Techniques. Cryptography, 2.","DOI":"10.3390\/cryptography2040036"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Kamel Ariffin, M.R., Abubakar, S.I., Yunos, F., and Asbullah, M.A. (2019). New Cryptanalytic Attack on RSA Modulus N = pq Using Small Prime Difference Method. Cryptography, 3.","DOI":"10.3390\/cryptography3010002"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Lenstra, A.K., Lenstra Jr, H.W., Manasse, M.S., and Pollard, J.M. (1993). The Number Field Sieve, Springer.","DOI":"10.1007\/BFb0091537"},{"key":"ref_34","unstructured":"Cheng, Q. (2021, January 18). A New Special-Purpose Factorization Algorithm. Citeseer. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.8.9071&rep=rep1&type=pdf."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Sedlacek, V., Klinec, D., Sys, M., Svenda, P., and Matyas, V. (2019, January 26\u201328). I Want to Break Square-free: The 4p 1 Factorization Method and Its RSA Backdoor Viability. Proceedings of the 16th International Joint Conference on e-Business and Telecommunications (ICETE 2019), Prague, Czech Republic.","DOI":"10.5220\/0007786600250036"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Grosswald, E. (1985). Representations of Integers as Sums of Squares, Springer.","DOI":"10.1007\/978-1-4613-8566-0"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1080\/00029890.2020.1751559","article-title":"A Short Proof of Fermat\u2019s Two-square Theorem","volume":"127","author":"Northshield","year":"2020","journal-title":"Am. Math. Mon."},{"key":"ref_38","unstructured":"Jackson, T. (1995). From Polynomials to Sums of Squares, CRC Press."},{"key":"ref_39","unstructured":"Dickson, L.E. (2005). History of the Theory of Numbers: Diophantine Analysis, Dover Publications. [2nd ed.]."},{"key":"ref_40","unstructured":"Roy, T., and Soni, F.J. (2012). A direct method to generate Pythagorean triples and its generalization to Pythagorean quadruples and n-tuples. arXiv."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1410","DOI":"10.1016\/j.disc.2015.12.002","article-title":"A partition-theoretic proof of Fermat\u2019s Two Squares Theorem","volume":"339","author":"Christopher","year":"2016","journal-title":"Discret. Math."},{"key":"ref_42","unstructured":"Knill, O. (2016). Some experiments in number theory. arXiv."},{"key":"ref_43","first-page":"775081","article-title":"An Original Numerical Factorization Algorithm","volume":"2016","author":"Kostopoulos","year":"2016","journal-title":"J. Inf. Assur. Cyber Secur."},{"key":"ref_44","unstructured":"Kaddoura, I., Abdul-Nabi, S., and Al-Akhrass, K. (2016). New Formulas for Semi-Primes. Testing, Counting and Identification of the nth and next Semi-Primes. arXiv."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"2065","DOI":"10.1090\/mcom3037","article-title":"A Deterministic Algorithm for Integer Factorization","volume":"85","author":"Hiary","year":"2016","journal-title":"Math. Comput."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Overmars, A., and Venkatraman, S. (2020). Mathematical Attack of RSA by Extending the Sum of Squares of Primes to Factorize a Semi-Prime. Math. Comput. Appl., 25.","DOI":"10.3390\/mca25040063"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1729","DOI":"10.1090\/S0025-5718-99-01133-3","article-title":"Speeding Fermat\u2019s factoring method","volume":"68","author":"McKee","year":"1999","journal-title":"Math. Comput."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"242","DOI":"10.3934\/math.2019.2.242","article-title":"A New approach to generate all Pythagorean triples","volume":"4","author":"Overmars","year":"2019","journal-title":"AIMS Math."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/s40329-014-0052-2","article-title":"Lagrange and the four-square theorem","volume":"2","author":"Boucard","year":"2014","journal-title":"Lett. Mat."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Dickson, L.E. (1992). History of the Theory of Numbers, AMS Chelsea Publishing. Carnegie Institute of Washington 1919.","DOI":"10.5962\/t.174912"},{"key":"ref_51","first-page":"159","article-title":"Leonard Dickson\u2019s History of the theory of numbers: An historical study with mathematical implications","volume":"5","author":"Fenster","year":"1999","journal-title":"J. Hist. Math."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"273","DOI":"10.2307\/3622017","article-title":"An alternative characterisation of all Primitive Pythagorean Triples","volume":"85","author":"Mitchell","year":"2001","journal-title":"Math. Gaz."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Venkatraman, S., and Overmars, A. (2019). New method of prime factorisation based attacks on RSA Authentication in IoT. Cryptography, 3.","DOI":"10.3390\/cryptography3030020"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Da Silva, J.C.L. (2010, January 17\u201320). Factoring Semi primes and Possible Implications. Proceedings of the 26th IEEE Convention in Israel, Eliat, Israel.","DOI":"10.1109\/EEEI.2010.5661953"},{"key":"ref_55","first-page":"340","article-title":"Performance Analysis of Fermat Factorization Algorithms","volume":"11","author":"Bahig","year":"2020","journal-title":"Int. J. Adv. Comput. Sci. Appl. (IJACSA)"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1007\/s00209-021-02705-x","article-title":"Diophantine approximation with prime restriction in real quadratic number fields","volume":"299","author":"Baier","year":"2021","journal-title":"Math. Z."},{"key":"ref_57","unstructured":"Lenstra, H.W., and Tijdeman, R. (1982). Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Part 1, Math. Centre Tract 154."},{"key":"ref_58","unstructured":"Hoffstein, J., Pipher, J., and Silverman, J. (2008). An Introduction to Mathematical Cryptography, Springer Publishing Company. [1st ed.]. Incorporated."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Stanoyevitch, A. (2010). Introduction to Cryptography with Mathematical Foundations and Computer Implementations, Chapman & Hall\/CRC. [1st ed.].","DOI":"10.1201\/9780429246609"},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Moreno, C.J., and Wagstaff, S.S. (2006). Sums of Squares of Integers. Discrete Mathematics and Its Applications, Chapman & Hall, CRC.","DOI":"10.1201\/9781420057232"},{"key":"ref_61","unstructured":"Kloster, K. (2020, September 30). Factoring a Semiprime n by Estimating \u03c6(n). Available online: http:\/\/www.gregorybard.com\/papers\/phi_version_may_7.pdf."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"25","DOI":"10.12709\/fbim.05.05.02.03","article-title":"Man in the Middle Attacks and the Internet of Things\u2014Security and economic risks","volume":"5","author":"Cekerevac","year":"2017","journal-title":"FBIM Trans."},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"El-hajj, M., Fadlallah, A., Chamoun, M., and Serhrouchni, A. (2019). A Survey of Internet of Things (IoT) Authentication Schemes. Sensors, 19.","DOI":"10.3390\/s19051141"},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/j.future.2018.08.038","article-title":"Lightweight IoT-based authentication scheme in cloud computing circumstance","volume":"91","author":"Zhou","year":"2019","journal-title":"Future Gen. Comput. Syst."},{"key":"ref_65","doi-asserted-by":"crossref","unstructured":"Yan, S.Y. (2018). Factoring Based Cryptography. In Cybercryptography: Applicable Cryptography for Cyberspace Security, Springer.","DOI":"10.1007\/978-3-319-72536-9"},{"key":"ref_66","doi-asserted-by":"crossref","unstructured":"Su\u00e1rez-Albela, M., Fraga-Lamas, P., and Fern\u00e1ndez-Caram\u00e9s, T.M. (2018). A Practical Evaluation on RSA and ECC-Based Cipher Suites for IoT High-Security Energy-Efficient Fog and Mist Computing Devices. Sensors, 18.","DOI":"10.3390\/s18113868"},{"key":"ref_67","doi-asserted-by":"crossref","unstructured":"Buhler, J.P., Lenstra, H.W., and Pomerance, C. (1993). Factoring Integers with the Number Field Sieve, Springer. Lecture Notes in Mathematics.","DOI":"10.1007\/BFb0091539"},{"key":"ref_68","first-page":"918","article-title":"Monte Carlo methods for index computation (mod p)","volume":"32","author":"Pollard","year":"1978","journal-title":"Math. Comput."},{"key":"ref_69","unstructured":"Overmars, A., and Venkatraman, S. (2020, January 6\u20138). A New Method for Factorizing Semi-primes Using Simple Polynomials. Proceedings of the 3rd International Conference on Research in Applied Science, Munich, Germany."},{"key":"ref_70","doi-asserted-by":"crossref","unstructured":"Stillwell, J. (2010). Mathematics and Its History, Springer. [2nd ed.].","DOI":"10.1007\/978-1-4419-6053-5"},{"key":"ref_71","unstructured":"Vogel, D., Onayemi, Y., and Murad, V. (2021, March 06). Integer Factorization Algorithms. Available online: http:\/\/maths.dk\/teaching\/courses\/math357-spring2016\/projects\/factorization.pdf."},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1090\/bull\/1665","article-title":"Current Trends and Open Problems in Arithmetic Dynamics","volume":"56","author":"Benedetto","year":"2019","journal-title":"Am. Math. Soc."},{"key":"ref_73","doi-asserted-by":"crossref","first-page":"080006","DOI":"10.1063\/1.5079140","article-title":"Representation of primes in the form p = 6\u00b7x \u00b1 1 and its application to the RSA prime factorization","volume":"Volume 2040","author":"Wisniewski","year":"2018","journal-title":"AIP Conference Proceedings"},{"key":"ref_74","doi-asserted-by":"crossref","first-page":"167250","DOI":"10.1109\/ACCESS.2019.2953755","article-title":"The Integer Factorization Algorithm with Pisano Period","volume":"7","author":"Wu","year":"2019","journal-title":"IEEE Access"},{"key":"ref_75","doi-asserted-by":"crossref","unstructured":"Rutkowski, E., and Houghten, S. (2020, January 19\u201324). Cryptanalysis of RSA: Integer Prime Factorization Using Genetic Algorithms. Proceedings of the 2020 IEEE Congress on Evolutionary Computation (CEC), Glasgow, UK.","DOI":"10.1109\/CEC48606.2020.9185728"}],"container-title":["Journal of Cybersecurity and Privacy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2624-800X\/1\/4\/33\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:29:11Z","timestamp":1760167751000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2624-800X\/1\/4\/33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,12]]},"references-count":75,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["jcp1040033"],"URL":"https:\/\/doi.org\/10.3390\/jcp1040033","relation":{},"ISSN":["2624-800X"],"issn-type":[{"value":"2624-800X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,12]]}}}