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

Jean-Sebastien Coron; Rina Zeitoun

Paper 2016/551

Improved Factorization of

Jean-Sebastien Coron and Rina Zeitoun

Abstract

Bones et al. showed at Crypto 99 that moduli of the form can be factored in polynomial time when . Their algorithm is based on Coppersmith's technique for finding small roots of polynomial equations. Recently, Coron et al. showed that can also be factored in polynomial time, but under the stronger condition . In this paper, we show that can actually be factored in polynomial time when , the same condition as for .

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Factoring Coppersmith's technique lattice 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: 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},
      url = {https://eprint.iacr.org/2016/551}
}