Fermat's factorisation method uses that fact that any number can be
expressed as the difference between two squares. It always works, and
works very quickly when the factors are near the root of the number.
When the factors aren't near the root of the number, the method works
very slowly, perhaps as slowly as trial division, with far more work! See also:
Integer can be written as the Difference between Two Squares
What follows is a rationale and not a strict proof.
We wish to show that any integer, n, can be written as:
Because we are looking at factorisation, then n is odd. (If n is even, we know 2 is a factor, and can divide by 2.)
For any integer, n, we can write:
Where x and y are integers. If n is prime, then the two numbers will be
equal to n and 1. Otherwise, they can also represent the other factors of
n. The Fundamental Theorem of Arithmetic (According to Gauss) tells us
that numbers can be written as the product of primes, so the factors x and y exist (Common sense tells us this).
x and y, in Equation 1.1a are odd integers, because n is odd.
We can do this because 1.2 and 1.3 are indeterminate equations
(Diaphantine Equations), which have a solution when gcd(1,1) divides x
and gcd(1,-1) divides y, which it always does.
Therefore:, by respectively adding and subtraction 2.2 and 2.3, we get:
are integers because x and y are both odd integers and the sum and
difference of two odd integers is an even integer, which divides by 2.
Subtracting the squares of 1.6 and 1.7, we get
[2.6] Of course we already know this, because 1.1a tells us:
n=x•y [1.1a, repeated]
Any odd number can, therefore, be represented as the difference between
Prime Factorisation Method
We are mainly concerned with non-negative integers here;
integers can be processed in the same way by supplying the necessary
minus signs. Also we are concerned with odd integers, because we can
always reduce an even integer to an odd one, and we are seeking a
practical way to find factors.
We can express any odd integer, n, in the form:
Where a and b are integers. If n is even, we know that 2 is a factor,
and continue to divide by 2 until the number is odd. For instance: 3=22−12, 5=32−22
For even integers we have: 4·1=4·(12−02), 2·3=2·(22−12), which is why we prefer to take out the 2 factors and deal with odd numbers.
When n is prime, then (a−b)=1 is
the only solution (for non-negative integers). When n has factors, then there are more solutions
For instance, if n=3, then a-b=1, and a+b=3 are the only solutions. That is, a=2 and b=1, giving (2-1)(2+1)=3 And for 9, we have two solutions: (3-0)(3+0)=32−02, and (5-4)(5+4)=52−42
So for odd numbers we seek a and b such that:
We can start with a1, where a1
is the smallest integer greater than √(n), or ceil
(√(n)). For instance, for 91, we start with a1
smallest integer greater than √91, which is 10. Naturally, if n is a
perfect square then we already have two non-trivial factors,the square
roots. For instance, if n=81, and we find the square root, 9, we already have two roots.
In general, we compute ak2−n
If Δak is a perfect square, then
And we can compute
the factors (a−b) and (a+b). We can then examine the factors found to
search for further factors, if required, perhaps by re-using Fermat's
For 91, we compute ceil(√(91))=ceil(9.5...)=10 102-91=9. As nine is a perfect square, we know (10-3)(10+3), or 7 and 13 are factors of 91. Similarly, for 63, ceil(√(7.9...))=ceil(7.9...)=8. 82-63=1. As 1 is a perfect square, we know (8-1)(8+1), or 7 and 9 are factors of 63.
method works quickly if the factors are near the root of the number,
but otherwise, not so quickly, or even terribly slowly.
For instance, let n=51.
For 51, we compute ceil(√(51))=8 a1=8,
Δa1=82-51=13.This isn't a perfect square. So try the next number up, 9. a2=9,
Δa2=92-51=30. Still no perfect square, so try 10. a3=10,
Δa3=102-51=49. At last a perfect square: 72. So a3-b=(10-7) and a3+b=(10+7), giving us 3 and 17 as factors of 51. If we continue seeking more factors: a4=11,
Δa4=112-51=70. a4+√(Δa4) ≥ n, 11+√(70) ≥ 51 a5=12,
Δa6=132-51=118. ... a32=26,
Δa32=262-51=625. A perfect square: 252. If we reach the end point, then we can stop, knowing we cannot find any more factors.
So a32-b32=(26-25) and a3+b=(26+25), giving us 1 and 51 as factors of 51.Using the formula below, a32+√(Δa32) ≥ 51, 26+√(625) ≥ 51, so we can stop as there are no more factors. The
morale here (From the large amount of work needed) is that we use
Fermat's method for a few tries, but then use something else, perhaps
even trial division. Fermat's method gives factors quickly when they
are near the root of the number. Otherwise it is more work than trial
As a final example in this section, we factorise 5555389669094450920099599 For 5555389669094450920099599, we compute ceil(√(5555389669094450920099599))= ceil(2356987413859.9 ...)=2356987413860 23569874138602-5555389669094450920099599=1. As one is a perfect square, we know (2356987413860
-1)(2356987413860 +1), or 2356987413859 and 2356987413861 are
factors of 5555389669094450920099599. We obtain this result
The point is that Fermat's Method makes light work
of difficult tasks under certain circumstances, but it can also make
hard work of an easy problem.
When to Stop
If a=b, the number is a
perfect square, which we would have discovered when finding the root.
We can then further examine the roots to seek further factors, if
Because (a+b)(a −b)=n, and if n is not a perfect square, and a>b: Then (a−b) cannot be less than 1. The greatest value of (a+b) is then n.
So when ak+√(Δak) ≥
n, we can stop, because there will be no more factors to be found ■
If the only factors found are n and 1, then n is prime.
Factorise 63 (We are not ashamed to begin with a simple example!)
This is a square number. (8+1)(8-1)=9•7=63, so the method gives factors immediately.
We find a square number immediately, so b=2
So we have found the factors 473, 477. We can now further examine these factors to search for prime factors, if required. (Neither 473 nor 477 is prime).
If there is a factor near the square root, Fermat's Method finds it quickly.
This example shows a more complete example of
Fermat's Method, and illustrates when to stop. The method finds
factors, in this case, immediately. n=45
√(45)<7, so we start with a1=7
The following was computed mainly using a spreadsheet:
We can stop when ak+√(Δak) ≥
n, here: 23+22=45, so we have found all the factors.
The above continues until we find our finishing point, which in the above case is when a=23, and b=22.
Looking at the 4th column, "Difference", which shows the difference between one a2-n value and the previous one (where possible), we can note it is a simple arithmetic series, with a difference of 2.
It is also possible to notice that in the example, that: ak+1=Δak+2•ak+1 That is, we get the next "b2" value by adding to the current result double the current a value plus 1.
By this means, the arithmetic can be eased because we do not have to square numbers every time.
The following example shows that even when the number
is relatively large, Fermat's Method find the factors very quickly when
they are close to the square root.n=98604899 √98604899<9930
We immediately find a perfect square, so (9930+1)(9930-1)=9931•9929.
We have established that the number isn't prime, and we can further
examine the factors, if required. (They are, in fact, both prime!)