Breaking Modulus of the form \(N = p^rq^s\) with Improved Polynomial Attacks
Sadiq Shehu *
Department of Mathematics, Faculty of Science, Sokoto State University, Nigeria.
Hamza Abdullahi
Department of Mathematics, College of Science, Ummaru Ali Shinka Polytechnic Sokoto, Nigeria.
Aminu A. Ibrahim
Department of Mathematics, College of Science, Ummaru Ali Shinka Polytechnic Sokoto, Nigeria.
Rufai Ahmad
Department of Mathematics, Faculty of Science, Sokoto State University, Nigeria.
*Author to whom correspondence should be addressed.
Abstract
Let \(N=p^r q^s\) be prime power moduli where \(p\) and \(q\) are unbalance prime numbers for \(2 \leq s<r\). If \(q<p<\lambda q\) and \(q^s<p^r<\lambda q^s\), and
\[
\phi(N) \approx \lambda^{\frac{r-s}{2 r}}\left(N^{\frac{r+s}{2 r}+N^{\frac{r+s-2}{2 r}}}\right)-N^{\frac{r+s-1}{2 r}}\left(\lambda^{\frac{r-s+1}{2 r}}+\lambda^{\frac{r-s-1}{2 r}}\right)
\]
then
\[
x<\sqrt{\frac{\lambda^{\frac{r-s}{2 r}}\left(N^{\frac{r+s}{2 r}}+N^{\frac{r+s-2}{2 r}}\right)-N^{\frac{r+s-1}{2 r}}\left(\lambda^{\frac{r-s+1}{2 r}}+\lambda^{\frac{r-s-1}{2 r}}\right)}{2 N^{\frac{1+2 \alpha r}{2 r}}}}
\]
which leads to the factorization of the moduli \(N=p^r q^s\) in polynomial time. The second assaults on s multi prime power moduli are described \(N_i=p^r_i q^s_i\) for \(i=1,2,..., \omega.\) We use lattice basis reduction techniques to obtain the parameters (x; yi) or (y; xi) after transforming the system of equations into a simultaneous Diophantine approximation problem, and it resulted in simultaneous factorization of s moduli \(N_i\) in polynomial time.
Keywords: Unbalance prime numbers, factorization, LLL algorithm, diophantine approximations, continued fraction