Fermat's factorization method

The factorization method of Fermat is an algorithm from the mathematical branch number theory . He calculates two divisors and for an odd composite number , for which applies. ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\cdot b=n}$

Fermat's factorization method only has a good runtime if the number to be broken down can be represented as a product of factors of approximately equal size. It also forms the basis of general factoring methods for large numbers, which usually have a better running time.

Pierre de Fermat described this factoring method, which is named after him today, in a letter in 1643 , which was probably addressed to Mersenne or Frénicle de Bessy . In that letter, he demonstrated the process by computing the prime factorization of 2,027,651,281. However, some historians suspect that the method was known earlier.

algorithm

Let be the odd number to be factored. Fermat's factoring method calculates the values ​​one after the other ${\displaystyle n}$

${\displaystyle \left(\left\lceil {\sqrt {n}}\right\rceil \right)^{2}-n}$

${\displaystyle \left(\left\lceil {\sqrt {n}}\right\rceil +1\right)^{2}-n}$

${\displaystyle \left(\left\lceil {\sqrt {n}}\right\rceil +2\right)^{2}-n}$

${\displaystyle \vdots }$

The smallest whole number denotes greater than or equal to . ${\displaystyle \left\lceil {\sqrt {n}}\right\rceil }$ ${\displaystyle {\sqrt {n}}}$

This continues until one of these values ​​is a square number :

${\displaystyle \left(\left\lceil {\sqrt {n}}\right\rceil +z\right)^{2}-n=x^{2}-n=y^{2}}$

Based on the third binomial formula, the following applies

${\displaystyle n=x^{2}-y^{2}=(x+y)(x-y)=a\cdot b.}$

This gives the decomposition of for which the ratio is (with ) the smallest. ${\displaystyle n}$ ${\displaystyle a/b}$ ${\displaystyle a\geq b}$

The following Nassi-Shneiderman diagram shows the sequence of the algorithm as it was already used by Fermat. The repeated squaring of the above description is avoided. The individual values ​​are calculated using the first binomial formula from their respective predecessor:

${\displaystyle \left(s+1\right)^{2}-n=s^{2}+2s+1-n}$

Calculate ${\displaystyle x=\left\lceil {\sqrt {n}}\right\rceil }$
Calculate ${\displaystyle r=x^{2}-n}$
as long as no square number ${\displaystyle r}$
	${\displaystyle r\leftarrow r+2x+1}$
	${\displaystyle x\leftarrow x+1}$
Calculate ${\displaystyle y={\sqrt {r}}}$
Calculate ${\displaystyle a=x+y}$
Calculate ${\displaystyle b=x-y}$

annotation

In many cases, by checking the last two digits of , one can rule out that is a square number. With a square number there are only 22 possibilities: 00, x1, x4, 25, y6 and x9, where x stands for an even and y for an odd number. With many numbers you can therefore rule out that they are square numbers by checking the last two digits. Fermat also used this property of the square numbers. This also works with other quadratic remainders , such as powers of two, which can easily be checked on a classic computer architecture. This idea can be generalized by examining not only the squares but the quadratic equation in two variables with respect to their residues: ${\displaystyle r}$ ${\displaystyle r}$

${\displaystyle x^{2}=y^{2}+n{\bmod {q}}}$

Because of the property there can be maximally possible residues if and are coprime. By combining the remainder classes with respect to different prime numbers (or small prime powers), the solutions for each remainder class used can be almost halved. ${\displaystyle (-x)^{2}=x^{2}}$ ${\displaystyle x}$ ${\displaystyle (q+1)/2}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle x}$

Examples

Example with many iterations

One would like to determine factors of the number 1729. The root of 1729 is about 41.6. So the first number to calculate for is 42. ${\displaystyle x}$ ${\displaystyle r}$

${\displaystyle x}$	${\displaystyle r=x^{2}-n}$	${\displaystyle 2x+1}$
42	35	85
43	120	87
44	207	89
45	296	91
46	387	93
47	480	95
48	575	97
49	672	99
50	771	101
51	872	103
52	975	105
53	1080	107
54	1187	109
55	1296 = 36 2

You can now immediately calculate the two factors of : ${\displaystyle n}$

${\displaystyle y={\sqrt {r}}=36}$

${\displaystyle a=x+y=55+36=91}$

${\displaystyle b=x-y=55-36=19}$

A decomposition from 1729 reads:

${\displaystyle 1729=19\cdot 91}$

Example with a few iterations

The example of the number 290377 shows that there are numbers for which Fermat's factorization method calculates a decomposition very quickly. The square root of 290377 is approximately 538.9. The next whole number is thus 539. It turns out that in the first step there is already a square number: ${\displaystyle x}$ ${\displaystyle r}$

${\displaystyle r=x^{2}-n=539^{2}-290377=144=12^{2}}$

You can now immediately calculate the two factors of : ${\displaystyle n}$

${\displaystyle y={\sqrt {r}}={\sqrt {144}}=12}$

${\displaystyle a=x+y=539+12=551}$

${\displaystyle b=x-y=539-12=527}$

A decomposition of 290377 is thus

${\displaystyle 290377=551\cdot 527}$

Neither are nor prime numbers. But you can apply the algorithm again on 551 and 527 to get the full prime factorization. ${\displaystyle 551=19\cdot 29}$ ${\displaystyle 527=17\cdot 31}$

Graphic example

All integer dividers can be represented as points in a dividing surface. The -axis shows the divisor values, the -axis corresponds to an integer number line (for better comprehensibility in the example the - and -axis are scaled in a ratio of 1 to 16). ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

The dividing points in a dividing surface have u. a. following properties:

• All dividing points of the dividing surface can be assigned to a negative parabola of the shape . ${\displaystyle y=-x^{2}+px}$

• All complementary divisor pairs of a number are on a common parabola.

• The addition of two complementary divisors of a number yields the coefficient of the common negative parabola. ${\displaystyle p}$

Example:

${\displaystyle 145=1\cdot 145=5\cdot 29}$

Fermat's factorization in the divisor plane

The complementary divisor pairs of are the trivial divisors and the non-trivial divisors . ${\displaystyle 145}$ ${\displaystyle 1\cdot 145}$ ${\displaystyle 5\cdot 29}$

The intersections of parabolas form with the parallel to the axis thus providing divider candidates. Shifting the parabola supplies either the non-trivial or, in the very last step, the trivial divisors of a number. ${\displaystyle y=-x^{2}+px}$ ${\displaystyle x}$ ${\displaystyle y=145}$

The first negative parabola with a vertex value greater is identified ( ). After moving it several times, the divisors and are found with the parabola . Is the vertex of this parabola . ${\displaystyle 145}$ ${\displaystyle y=-x^{2}+25x}$ ${\displaystyle p=\lceil ({\sqrt {1}}45)\cdot 2\rceil =25}$ ${\displaystyle 5}$ ${\displaystyle 29}$ ${\displaystyle y=-x^{2}+(5+29)x=-x^{2}+34x}$ ${\displaystyle S(17,289)}$

The number can thus be represented as the difference between the squares . The non-trivial factors can be calculated using and . ${\displaystyle 145}$ ${\displaystyle 17^{2}-(17-5)^{2}=17^{2}-12^{2}=289-144}$ ${\displaystyle 17-12=5}$ ${\displaystyle 17+12=29}$

Since parabolas of the form only provide complementary divisors to even numbers, they are not taken into account in Fermat's method. ${\displaystyle y=-x^{2}+(2p+1)x}$

functionality

Fermat's factorization method looks for two squares and that satisfy the equation . Based on the 3rd binomial formula , then ${\displaystyle x^{2}}$ ${\displaystyle y^{2}}$ ${\displaystyle x^{2}-n=y^{2}}$

${\displaystyle n=x^{2}-y^{2}=(x+y)(x-y)}$

and and are the divisors of . Fermat's method finds precisely those divisors and that are closest to the root of . ${\displaystyle a=x+y}$ ${\displaystyle b=x-y}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle n}$

The question arises whether there are always two square numbers and that satisfy the above equation. If this were not the case, the algorithm would get into an infinite loop . In the following, an odd composite number is assumed, as in Fermat's factoring method. Then is the product of two odd numbers and and so are ${\displaystyle x^{2}}$ ${\displaystyle y^{2}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle x={\frac {a+b}{2}}}$ and ${\displaystyle y={\frac {a-b}{2}}}$

whole numbers. A simple calculation using the binomial formulas shows that : ${\displaystyle x^{2}-y^{2}=n}$

${\displaystyle x^{2}-y^{2}=\left({\frac {a+b}{2}}\right)^{2}-\left({\frac {a-b}{2}}\right)^{2}={\frac {a^{2}+2ab+b^{2}}{4}}-{\frac {a^{2}-2ab+b^{2}}{4}}=ab=n}$

The number can therefore always be represented as the difference between two square numbers. ${\displaystyle n}$

Runtime analysis

The method will find a solution in a few iterations if a number can be broken down into two approximately equal factors. We can write the larger factor in the form with one . If the value is much smaller than 1, the number of iterations required is approximate . In this case, the procedure is much faster than the trial division. ${\displaystyle a=\left(1+\epsilon \right){\sqrt {n}}}$ ${\displaystyle \epsilon >0}$ ${\displaystyle \epsilon }$ ${\displaystyle {\frac {{\epsilon }^{2}}{2}}{\sqrt {n}}}$

However, if the factors are far apart, this method also needs a large number of iterations. In the worst case at , where is a prime number, this method takes many iterations. ${\displaystyle n=3p}$ ${\displaystyle p}$ ${\displaystyle \Omega (n)}$

Extension: Factoring a multiple

In order to avoid the bad running time for numbers that are not the product of two approximately equal factors, the factoring method can be carried out for a multiple of the original number . The greatest common divisors between and each of the calculated factors and of then each provide a divisor of . ${\displaystyle n'=k\cdot n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a'}$ ${\displaystyle b'}$ ${\displaystyle n'}$ ${\displaystyle n}$

As an example, consider number 1729, which the normal factoring method takes 14 steps. The number can be broken down into factors 420 and 494 after just two iterations. A divisor of 1729 can be calculated as the greatest common divisor: ${\displaystyle 120\cdot 1729=207480}$

${\displaystyle \operatorname {ggT} (1729,420)=7}$

With one has a factorization of the number 1729: ${\displaystyle {\frac {1729}{7}}=247}$

${\displaystyle 1729=7\cdot 247}$

The problem now arises of finding a suitable factor . Russell Sherman Lehman has 1,974 to the factorization of Lehman developed a method that such place. This shortens the running time to . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(n^{\frac {1}{3}}\log \log n)}$

Fermat's factorization method as a prime number test

Fermat's factorization method can be used as a primality test , although it is not particularly efficient. From the runtime analysis it is known that the most unfavorable input for the algorithm is a number of the form ( is a prime number). In this case it is ${\displaystyle n=3p}$ ${\displaystyle p}$

${\displaystyle x={\frac {3+p}{2}}={\frac {3+{\tfrac {n}{3}}}{2}}={\frac {9+n}{6}}}$

If one now allows any odd numbers as input to the algorithm and none of the numbers is ${\displaystyle n}$

${\displaystyle \left(\lceil {\sqrt {n}}\rceil \right)^{2}-n,\left(\lceil {\sqrt {n}}\rceil +1\right)^{2}-n,\dotsc ,\left({\frac {9+n}{6}}\right)^{2}-n}$

a square number, so is a prime number. ${\displaystyle n}$

literature

• Hans Riesel : Prime Numbers and Computer Methods for Factorization. 2nd Edition. Birkhäuser, Boston 1994, ISBN 0-8176-3743-5 .
• Donald E. Knuth : The Art of Computer Programming . Volume 2. Seminumerical Algorithms. 3. Edition. Addison-Wesley, 1998, ISBN 0-201-89684-2 .

Web links

• Eric W. Weisstein : Fermat's Factorization Method . In: MathWorld (English).
• The Prime Glossary: Fermat's method of factoring.
• Bruno Lehnen (GeoGebra materials): Fermat's factorization in the divisor plane.

Individual evidence

1. ^ Leonard E. Dickson : History of the Theory of Numbers. Volume 1. Divisibility and Primality. Dover Publications, 2005, ISBN 0-486-44232-2 , p. 357.
2. ^ Richard Crandall , Carl Pomerance : Prime Numbers. A Computational Perspective. 2nd Edition. Springer-Verlag, New York, 2005, ISBN 0-387-25282-7 , pp. 191-192.