Math 511, Fermat's Factoring Method

Factoring Methods

What is the factorization of 9991? One way to approach this problem is to try different prime factors in turn up to the Ö(9991). This works, but it takes a long time. A quicker method is to recognize that 9991 = 10000 - 9 = 100² - 3² = (100 + 3)(100 - 3) = 103 ´ 97. This trick goes back to the 17^th century French jurist and amateur (but extraordinarily gifted) mathematician Pierre de Fermat. This observation can be turned into a different algorithm for factoring than the usual guess and check.

Algorithm: To factor a number r.

Step 1: Calculate Ö(r)

Step 2: Compute n² - r starting with n the first integer greater than Ö(r) and continuing until you reach a square m².

Step 3: Since n² - r = m², we conclude r = n² - m² and so r factors into r = (n + m) ´ (n - m).

Step 4: Don't quit too soon. Be sure to factor n + m and n - m if they aren't prime.

Example: Factor 426749

Step 1: Ö(426749) = 653.26...

Step 2: Starting at n = 654, compute n² - 654

n	n² - 426749
654	967
655	2276
656	3587
657	4900

We observe 4900 = 70².

Step 3: 426749 = (657 + 70)(657 - 70) = 727 ´ 587.

Step 4: Since 727 and 587 are prime, we have obtained the prime factorization of 426749.

Fermat's factoring method works by finding pairs a and b such that a² = b² (mod n) with a¹ (mod n). Fermat's method works well when the number factors into two terms of approximately equal size. It works poorly when the factors are of very different sizes. But we can develop a more sophisticated variation on this algorithm that works well even in the more general case. In the 1920s, Maurice Kraitchik published a trick to find such pairs quickly for more general numbers. It is easiest to understand Kraitchik's method by seeing an example. Suppose we want to factor 2041. We start by computing a table of values of Q(x) = x² - 2041 for x near 45 (which is the closest integer to the square root of 2041). We also factor all the values the polynomial takes in our table.

x	Q(x)	Factorization of Q(x)
40	-441	-1 ´3² ´ 7²
41	-360	-1 ´ 2³ ´ 3² ´ 5
42	-277	-1 ´ 277
43	-192	-1 ´ 2⁶ ´ 3
44	-105	-1 ´ 3 ´ 5 ´ 7
45	-16	-1 ´ 2⁴
46	75	3 ´ 5²
47	168	2³ ´ 3 ´ 7
48	263	1 ´ 263
49	360	2³ ´ 3² ´ 5
50	459	3³ ´ 17
51	560	2⁴ ´ 5 ´ 7
52	663	3 ´ 13 ´ 17
53	768	2⁸ ´ 3

We note that x² = Q(x) (mod 2041), so if any of the Q(x) were squares we would be done. Unfortunately, none of them are. But we can try to build squares out of the different terms in the table. For example,

41² ´ 45² ´ 49² = 2¹⁰ ´ 3⁴ ´ 5² = (2⁵ ´ 3² ´ 5)² (mod 2041) so we have (41 ´ 45 ´ 49)² = (2⁵ ´ 3² ´ 5)² (mod 2041). Multiplying this out, we find 41 ´ 45 ´ 49 = 601 (mod 2041) and 2⁵ ´ 3² ´ 5 = 1440 (mod 2041). Unfortunately, 1440 = -601 (mod 2041), so knowing 601² = 1440² (mod 2041) doesn't get us any closer to a factorization of 2041. But there are other ways we can combine entries to build squares (actually there are more than a half-dozen ways I can see). After some experimentation we found in class that 43² ´ 45² ´ 46² = 2¹⁰ ´ 3² ´ 5² = (2⁵ ´ 3 ´ 5)² (mod 2041) so (43 ´ 45 ´ 46)² = (2⁵ ´ 3 ´ 5)² (mod 2041). This time we get 43 ´ 45 ´ 46 = 1247 (mod 2041) and 2⁵ ´ 3 ´ 5 = 480 (mod 2041) so we have a non-trivial repetition of squares from which we can find the factorization of 2041.

Finishing off the problem now, we proceed as in the homework for last week. From 1247² = 480² (mod 2041) we conclude (1247 + 480)(1247 - 480) = 1727 ´ 767 = 2041 ´ y for some y. Next we compute gcd(767,2041) = 13 using the Euclidean algorithm. So we know 13 is a factor of 2041. Dividing 2041 by 13 we find 2041 = 13 ´ 157. Since both 13 and 157 are primes, we have found the prime factorization of 2041.

There are a number of points to consider about this factoring method. You may have noticed that it would be a lot quicker to use trial division than Kraitchik's method to factor 2041. Kraitchik's method is not the best choice for four digit numbers. But it is easiest to see how the method works with smaller numbers. Once the method is understood, it can be implemented as a computer program to attack larger problems where trial division takes too long.

Of course, it is hard to program a step like "experiment with different combinations to find squares" into a computer. Obviously we need to find a programmable algorithm to find the squares we want. Finally, the toughest part of building our table was factoring. What is particularly bad is that we spend more time on checking that 277 and 263 don't factor than any other lines in the table, and this is useless information because we won't be using such large primes to build squares. In our next lectures we will cover enhancements to Kraitchik's method that fix these problems.

The final comment is on the name "Kraitchik's method." While most number theory books discuss "Fermat's factoring method" by that name, almost none refer to "Kraitchik's method." The reason for this is that people almost never use Kraitchik's method itself, but only the enhanced version that we will study next. This enhanced version is called the "Quadratic Sieve," and is the basic method underlying the UBASIC program mpqsx.