Factorization Algorithm for Semi-primes and the Cryptanalysis of Rivest-Shamir-Adleman (RSA) Cryptography

Richard Omollo *

Department of Computer Science and Software Engineering, School of Informatics and Innovative Systems, Kenya and Jaramogi Oginga Odinga University of Science and Technology, Box 210-40601, Bondo, Kenya.

Arnold Okoth

Department of Computer Science and Software Engineering, School of Informatics and Innovative Systems, Kenya and Jaramogi Oginga Odinga University of Science and Technology, Box 210-40601, Bondo, Kenya.

*Author to whom correspondence should be addressed.


Abstract

This paper introduces a new factoring algorithm called Anorld’s Factorization Algorithm that utilizes semi-prime numbers and their implications for the cryptanalysis of the Rivest-Shamir-Adleman (RSA) cryptosystem. While using the concepts of number theory and algorithmic design, we advance a novel approach that notably enhances the efficiency of factoring large semi-prime numbers compared to other algorithms that have been developed earlier. In our approach, we propose a three-step algorithm that factorizes relatively large semi-primes in polynomial time. We have introduced factorization up to 12-digit semi-prime using Wolfram|Alpha, a mathematical software suitable for exploring polynomials. Additionally, we have discussed the implications of the new algorithm for the security of RSA-based cryptosystems. In conclusion, our research work emphasizes the important role of factoring algorithms in the cryptanalysis of RSA cryptosystems and proposes a novel approach that bolsters the efficiency and effectiveness of semi-prime factorization, thereby informing the development of more powerful cryptographic protocols.

Keywords: Arnold’s Factorization Algorithm (A.F.A.), modular factorial, euclidean algorithm, RSA cryptography


How to Cite

Omollo, Richard, and Arnold Okoth. 2024. “Factorization Algorithm for Semi-Primes and the Cryptanalysis of Rivest-Shamir-Adleman (RSA) Cryptography”. Asian Journal of Research in Computer Science 17 (6):85-95. https://doi.org/10.9734/ajrcos/2024/v17i6458.