# integer factoring using Fermat's method

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.

• What size are the integers you want to factor with this method? – naitoon Oct 7 '13 at 17:16
• for n = 27 your code initializes with x = 6 and y = 3, which satisfy the while loop condition and give wrong result (6, 3) btw there seems to be a typo in your code initialization – user45022 Jan 17 '16 at 15:21

## 2 Answers

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.

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.

• Incidentally, Fermat in his original description mentioned this idea, e.g. looking at the last few digits of $x^2 - n$ to have to find square roots only very rarely. – ShreevatsaR Apr 15 at 23:36