**The Fermat factorization method revisited**

*Robert ERRA and Christophe GRENIER*

**Abstract: **We consider the well known Fermat factorization method ({\it FFM}) when it is applied on a balanced RSA modulus $N=p\, q>0$, with primes $p$ and $q$ supposed of equal length. We call the {\it Fermat factorization equation} the equation (and all the possible variants) solved by the FFM like ${\cal P}(x,y)=(x+2R)^2-y^2-4N=0$ (where $R=\lceil N^{1/2} \rceil$).

These equations are bivariate integer polynomial equations and we propose to solve them directly using Coppersmith's methods for bivariate integer polynomials. As we use them as a black box, our proofs will be brief.

We show first that, using Coppersmith's methods, we can factor $N$ in a polynomial time if $|p-q|<N^{3/14}$, with $3/14 \approx 0.214\cdots$ and, using the fact that the Newton polygon of ${\cal P}(x,y)$ is a lower triangle we show a better result: we can indeed factor $N$ in a polynomial time if $|p-q|<N^{1/4}$. Unfortunately this shows that using Coppersmith's methods for bivariate integer polynomials is no better than the FFM, because in that case the FFM is immediate. This is confirmed by numerical experiments.

We then propose another method: solving the {\it modular} Fermat factorization equation $ (x+2R)^2-y^2=0 \mod 4N $. Since Coppersmith's methods for {\it modular} multivariate integer polynomial equations are {\it empirical}, there relies on the the famous {\it "resultant heuristic"}, we get only an empirical method that can factor $N$ in a polynomial time if $|p-q|<N^{1/3}$. We conclude with proposals for future works.

**Category / Keywords: **public-key cryptography / Fermat factoring equation Coppersmith method RSA

**Publication Info: **No publication.

**Date: **received 28 Jun 2009, last revised 23 Jul 2009

**Contact author: **erra at esiea fr

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20090724:005920 (All versions of this report)

**Short URL: **ia.cr/2009/318

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]