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