Welcome to the resource topic for
**2015/071**

**Title:**

Factoring N=p^r q^s for Large r and s

**Authors:**
Jean-Sebastien Coron, Jean-Charles Faugere, Guenael Renault, Rina Zeitoun

**Abstract:**

Boneh et al. showed at Crypto 99 that moduli of the form N=p^r q can be factored in polynomial time when r=log p. Their algorithm is based on Coppersmith’s technique for finding small roots of polynomial equations. In this paper we show that N=p^r q^s can also be factored in polynomial time when r or s is at least (log p)^3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli N with k prime factors; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the k exponents is large enough.

**ePrint:**
https://eprint.iacr.org/2015/071

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .