Skip to content
Research Article Open access CC BY 4.0

Breaking Modulus of the form \(N = p^rq^s\) with Improved Polynomial Attacks

Sadiq Shehu, Hamza Abdullahi, Aminu A. Ibrahim, Rufai Ahmad

Journal of Advances in Mathematics and Computer Science · pp. 33–46 · Published 17 Jun 2023

10.9734/jamcs/2023/v38i81788

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.

Unbalance prime numbers factorization LLL algorithm diophantine approximations continued fraction

References (16)

  1. 1 New directions in cryptography [DOI]
  2. 2 A method for obtaining digital signatures and public-key cryptosystems [DOI]
  3. 3 Factoring polynomials with rational coefficients [DOI]
  4. 4 Cryptanalysis of short RSA secret exponents [DOI]
  5. 5 Fast RSA-type cryptosystem modulo p k q [DOI]
  6. 6 Cryptanalysis of RSA with Small Prime Difference [DOI]
  7. 7 Revisiting Wiener’s Attack – New Weak Keys in RSA [DOI]
  8. 8 A Generalized Takagi-Cryptosystem with a Modulus of the Form prqs [DOI]
  9. 9 Revisiting Prime Power RSA [DOI]
  10. 10 Factoring $$N=p^rq^s$$ for Large r and s [DOI]
  11. 11 New Attacks on RSA with ModulusN=p2qUsing Continued Fractions [DOI]
  12. 12 Improved Factorization of $$N=p^rq^s$$ [DOI]
  13. 13 Polynomial Time Attacks for Modulus N = p^2 q^2 [DOI]
  14. 14 IEEE Transactions on Information Theory [DOI]
  15. 15 New RSA Vulnerabilities Using Lattice Reduction Methods
  16. 16 Applicable Algebra in Engineering, Communication and Computing [DOI]

Cited by 4

Revisiting Takagi-Lim et al. family schemes

George Teşeleanu · Discrete Applied Mathematics · 2026

Small Private Exponent Attacks on Takagi Family Schemes

George Teşeleanu · Lecture Notes in Computer Science · 2025

Showing 2 of 4 known citations — external sources report more than can currently be individually listed.

Related research

Article metrics

Real usage data collected on this platform.

44

Page views

0

PDF downloads

8

Outbound clicks

4

Citations

Views over time

Views by country

Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".

Traffic sources

Referring site, by host.

Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.