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:
What follows is a rationale and not a strict proof.
We wish to show that any integer, n, can be written as:
n=a2−b2 [1.1]
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:
n=x•y [1.1a]
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.
Let
x=a+b [1.2]
And
y=a−b [1.3]
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:
x+y=2a [1.4]
x-y=2b [1.5]
So:
[1.6]
And
[1.7]
a
and b
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
two squares.■
Fermat's
Prime Factorisation Method
We are mainly concerned with non-negative integers here;
negative
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:
n=a2−b2 [2.01]
or (factorised):
n=(a+b)(a−b) [2.02]
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
than (a−b)=1.
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:
n=a2−b2
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
as the
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
or:
Δak=ak2−n
If Δak is a perfect square, then
b=√(Δak).
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
Method.
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.
Fermat's
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,
Δa5=122-51=93. a6=13,
Δ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
division.
As a final example in this section, we factorize 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
immediately.
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
required.
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:
(a+b)≤n
As
Δak=ak2−
n=bk2.
Therefore:
ak+√(Δak)
≤ n
Because:
bk=√(Δak)
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.
Examples
Example 1
Factorise 63 (We are not ashamed to begin with a simple example!)
√(63)<8
a1=8
a2
−n
b2
82
−63
1=12
This is a square number. (8+1)(8-1)=9•7=63, so the method gives factors immediately.
Example 2
Factorise 22,5621
√(225621)<475
a1=475
a2
−n
b2
4752
−225621=
4 (22)
We find a square number immediately, so b=2
a+b=475+2=477
a-b=475-2=473
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.
Example 3
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:
Number,
n=45
Factors
Comments
k
ak
ak2-n (Δak)
Difference, (ak2-n)−(ak-12-n)
b=√(ak²-n)
Perfect
Square?
x
y
1
7
4
2
yes
5
9
2
8
19
15
4.36
no
no
no
3
9
36
17
6
yes
3
15
4
10
55
19
7.42
no
no
no
5
11
76
21
8.72
no
no
no
6
12
99
23
9.95
no
no
no
7
13
124
25
11.14
no
no
no
8
14
151
27
12.29
no
no
no
9
15
180
29
13.42
no
no
no
10
16
211
31
14.53
no
no
no
11
17
244
33
15.62
no
no
no
12
18
279
35
16.7
no
no
no
13
19
316
37
17.78
no
no
no
14
20
355
39
18.84
no
no
no
15
21
396
41
19.9
no
no
no
16
22
439
43
20.95
no
no
no
17
23
484
45
22
yes
1
45
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.
Example 4
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
a2
−n
b2
9930=986049002
−98604899=
1
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!)
[1.6]
[1.7]
[2.6]