Paper 2016/551

Improved Factorization of $N=p^r{q}^s$

Jean-Sebastien Coron and Rina Zeitoun

Abstract

Bones et al. showed at Crypto 99 that moduli of the form $N=p^{r}q$ can be factored in polynomial time when $r\ge \log p$. Their algorithm is based on Coppersmith's technique for finding small roots of polynomial equations. Recently, Coron et al. showed that $N=p^r{q}^s$ can also be factored in polynomial time, but under the stronger condition $r\ge {\log }^{3}p$. In this paper, we show that $N=p^r{q}^s$ can actually be factored in polynomial time when $r\ge \log p$, the same condition as for $N=p^{r}q$.