Paper 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$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
FactoringCoppersmith's techniquelattice reduction
Contact author(s)
jean-sebastien coron @ uni lu
r zeitoun @ oberthur com
History
2016-06-02: received
Short URL
https://ia.cr/2016/551
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/551,
      author = {Jean-Sebastien Coron and Rina Zeitoun},
      title = {Improved Factorization of $N=p^rq^s$},
      howpublished = {Cryptology ePrint Archive, Paper 2016/551},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/551}},
      url = {https://eprint.iacr.org/2016/551}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.