integer factoring using Fermat's method

Question

Reading an article on integer factorization I implemented the following - rather inefficient - factorization method:

Every odd composite can be factored as a difference of squares: $$ ab = \left[\tfrac{1}{2}(a+b)\right]^2 - \left[\tfrac{1}{2}(a-b)\right]^2$$ We can look at values of $f(x) = x^2 - n$ until we find a perfect square and factor.

Here's my implementation in Python.

def fermat(n):
    x = int(np.sqrt(n))+1
    y = int(np.sqrt(abs(y*y - n)))

    while( n - x*x + y*y != 0):
        x += 1
        y = int(np.sqrt(abs(x*x - n)))

    return x, y

How expensive are the square root calculations here? Are they necessary? In order to check I have a perfect square, I compute $\lfloor \sqrt{x^2-n}\rfloor$ many times.

Answer 1

Square roots can be computed via several methods (binary search, Newton iterations) rather fast. Note, however, that you are computing floating-point square roots, which are implemented by hardware and so should be even faster; but they are less appropriate if you want to factor large numbers, since floating-point computations are only approximate, and moreover the range of floating-point numbers is limited. Use a bignum package instead.

Answer 2

You absolutely don't have to compute most of the square roots.

You want to know whether the square root of $x^2 - n$ is an integer, that is you want to know whether $x^2 - n$ itself is a square. You don't need to know the actual square root as long as you know it is no integer.

Take d = 20,160 and create a bitmap of which integers are a square modulo 20,160 - only one in 30 is. Check whether ($x^2 - n$) modulo 20,160 is in the table. In 29 out of 30 cases the answer is "no", and $x^2 - n$ is not a square.

Also, less than one in 7 integers are squares modulo 20,387, 21,607, 17,641, or 22,231. If you add these tests then calculating a square root is needed in less than one 72,000 cases.