Cryptology ePrint Archive: Report 2016/551

Improved Factorization of $N=p^rq^s$

Jean-Sebastien Coron and Rina Zeitoun

Abstract: Bones et al. showed at Crypto 99 that moduli of the form $N=p^rq$ can be factored in polynomial time when $r \geq \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^rq^s$ can also be factored in polynomial time, but under the stronger condition $r \geq \log^3 p$. In this paper, we show that $N=p^rq^s$ can actually be factored in polynomial time when $r \geq \log p$, the same condition as for $N=p^rq$.

Category / Keywords: public-key cryptography / Factoring, Coppersmith's technique, lattice reduction

Date: received 1 Jun 2016

Contact author: jean-sebastien coron at uni lu, r zeitoun@oberthur com

Available format(s): PDF | BibTeX Citation

Version: 20160602:165747 (All versions of this report)

Short URL: ia.cr/2016/551

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]