International Association
for Cryptologic Research

In this paper, we first propose a rigorous polynomial time algorithm based on the univariate Coppersmith theorem that factorizes an integer $N=PQ^r$ with unknown primes $P, Q$ and $r \geq 1$, for an arbitrary given prime $e>N^{\frac{1}{4r}}$ satisfying $e\mid \phi(N)$. Furthermore, the bound $e>N^{\frac{1}{4r}}$ is improved to $e>N^{\beta-r\beta^2}$ if the value of $\beta$ such that $Q\geq N^\beta$ is known. Moreover, these two bounds can also be obtained respectively when $e$ is no longer a prime number. Specifically, we address the scenario where $e$ is a square-free composite number with known factorization, as well as the case where $e$ is a composite number with known factorization, and the corresponding prime factors $P$ and $Q$ of $N$ satisfy $\gcd(P-1, Q-1)=2$. In both cases, in order to make the corresponding algorithms polynomial time, we limit the number of prime factors of $e$ to $O (\log \log N)$ and $r$ to be any integer constant. When applied to the $\phi$-hiding assumption, our bounds are significantly better than previous results. When applied to standard RSA moduli, we extend the case where $e$, which was involved in the previous best bound $e>N^{\frac{1}{4}}$, is no longer a prime number. This can highlight the security vulnerability introduced by the function $\mathrm{RSA}_{N,e}$, as discussed by Kakvi et al. in \cite{May2012}, being at least $e_i$-to-1 lossy for some prime factors $e_i$ of $e$. When applied to decompose the semi-smooth RSA subgroup moduli, we provide a rigorous proof for the second bound presented by Naccache and Stern for the first time. We validate the effectiveness of algorithms through experiments.