Strategic Way of Factoring Modulus \(N = p^r q\)
Sadiq Shehu *
Department of Mathematics, Faculty of Science, Sokoto State University, Sokoto, Nigeria.
Abdullahi Hussaini
Department of Mathematics, Faculty of Science, Sokoto State University, Sokoto, Nigeria.
Zahriya Lawal
Department of Computer Science, Faculty of Science, Sokoto State University, Sokoto, Nigeria.
*Author to whom correspondence should be addressed.
Abstract
Cryptography is fundamental to the provision of a wider notion of information security. Electronic information can easily be transmitted and stored in relatively insecure environments. This research was present to factor the prime power modulus \(N = p^r q\) for \(r \geq 2\) using the RSA key equation, if \(\frac{y}{x}\) is a convergents of the continued fractions expansions of \(\frac{e}{N - \left(2^{\frac{2r+1}{r+1}} N^{\frac{r}{r+1}} - 2^{\frac{r-1}{r+1}} N^{\frac{r-1}{r+1}}\right)}\). We furthered our analysis on \(n\) prime power moduli \(N_i = p_i^r q_i\) by transforming the generalized key equations into Simultaneous Diophantine approximations and using the LLL algorithm on \(n\) prime power public keys \((N_i,e_i)\) we were able to factorize the \(n\) prime power moduli \(N_i = p_i^r q_i\), for \(i = 1,....,n\) simultaneously in polynomial time.
Keywords: Prime power, Factorization, LLL algorithm, simultaneous diophantine approximations, continued fraction.