Proceedings of The 3rd International Conference on Research in Applied Science
Year: 2020
DOI:
A New Method for Factorizing Semi-Primes Using Simple Polynomials
Anthony Overmars, Sitalakshmi Venkatraman
ABSTRACT:
This paper presents a new method to factorize semi-primes using simple polynomials. We consider a semi-prime,, whose factors are both congruent as represented by: According to Fermat’s Christmas Theorem, a sum of two squares can be found for each prime and two sums of two squares for the semi-prime. Using this property, we propose a new method to find the first of these sums of two squares and once this is known, the Brahmagupta identity is used to find the second sum of two squares. Subsequently, a modified Euler factorization is applied to recover the two prime constructs of the semi-prime. The correctness of our new factorization method is established with mathematical proofs.
Keywords: semi-prime factorization, Brahmagupta identity, Euler’s factorization, encryption key.