The Fermat factorization method revisited.
Robert Erra, Christophe Grenier · 2009
We consider the well known Fermat factorization method, we call the Fermat factorization equation the equation solved by it: P(x, y) = (x + 2R) 2 − y 2 − 4N = 0; where N = p q> 0 is a RSA modulus with primes p and q supposed of equal length. This equation is a bivariate integer polynomial equation and we propose to solve it directly using Coppersmith’s methods for bivariate integer polynomials. As we use them as a black box, our proofs will be brief. We show a first result: we can factor N in a polynomial time if |p − q | < N 5/18. Using the fact that the Newton polygon of P(x, y) is in fact a lower triangle we show a better result: we can indeed factor N in a polynomial time if |p − q | < N 1/3. We conclude with proposals for future works. 1