This is a continuation of my last factoring post. I thought that I might have been getting ahead of myself, as I left out a relatively simple idea that led to great gains in factorization. The key of this post is Fermat’s Factorization, and a continuation by R. Lehman.

The main idea here is very simple. When a number can be written as the difference of two squares, i.e. , then we can factor as . And as long as neither are 1, it yields a proper factorization.

Now I mention a brief aside, not relevant to Fermat Factorization. There is another, lesser-known identity called Sophie Germain’s Identity:

By the way, a Sophie Germain prime is a prime such that is also a prime. It is unknown whether or not there are infinitely many Sophie Germain primes.

Now, the idea of this factorization method is to try different values of in the hope that is a square, i.e. for some integer . So the algorithm proper might be like:

1. Set

2.

3. Test if c is a square. If it is, look at and . If not, go to step 4.

4. Increase a by 1 and set . Return to step 3.

Of course, one should end the algorithm sometime if no factorization is found. So perhaps one should use a counter. But that’s besides the point.

Clearly, this algorithm works best when the factors are about the size of . Done naively, Fermat’s Algorithm works slower than trial diversion in the worst case. But there is a quick way to combine Fermat’s Algorithm and trial division that is faster than doing either separately. This is only the first of a few possible optimizations.

Let’s look at an example. Suppose we want to factor (astoundingly enough, 1234567891 is prime, and was going to be my first example). One sees that . So with trial division, we would need to test numbers up to 351365. But let’s do a couple of iterations of Fermat’s Method:

Step:

1: ; and

2: ; and

3: and

4: and

…

So no result yet, it might seem. But Fermat’s Method *does not miss factors* in the range that it sweeps through. Thus from these 4 iterations, we have looked for factors as low as . So in just 4 iterations, we narrowed the range to be tested by trial division from every between 1 and 351365 to everything between 1 and 349730. 4 iterations reduces the 1000 most complicated trial division tests (there are 210 primes in that range, so at least that many).

In general, if one chooses a bound and uses Fermat to find factors between and , then the resulting necessary bound for trial division is .

There is another easy modification to speed up this test, involving a sieve. Let’s make a couple of observations.

### First Note

Note that all squares end in . Suppose we have calculated a particular value of . The last two digits are cyclic too – they repeat with each increase by 10. So calculating a couple of values of allows us to decide which a to continue to calculate. This leads to calculating only a fraction of the a values and a fraction of the subsequent square root calculations.

There is nothing special about 20, really. Any modulus will do. But 10, 20, or (for larger values) a prime power. Or one can combine a few with the Chinese Remainder Theorem. Unfortunately, this only really changes the overall time complexity by a constant factor.

### Second Note

While it is clear that Fermat’s Method works best for factors near , that doesn’t happen too often. But if one can somehow divine (or guess) an approximate ratio of the two factors, suppose something like , then one can choose a rational number near that value and then perform Fermat’s Method on , which should pull the factors first.

This is turning out to be longer than I was expecting, so I’m splitting this post into 2 (that way I can finish the other half tomorrow). In the next, we will continue to improve upon Fermat’s Factorization, firstly by splitting up the interval wittily. Secondly, by coming up with a method that heuristically splits a composite number in $O(n^{1/4 + \epsilon})$ steps by using a slight generalization. Finally, I have heard of an improvement of Grenier that allows polynomial time factorization if the primes are relatively close to each other. More on that in the next few days.

(twice).

why ask: ?

Good catch – I suppose I get used to expanding and I reverted for a moment. I have changed it to b so that it is correct.

[…] in my last post on factoring, I spoke of Sophie Germain’s identity. I’ve had a case of Mom’s Corollary* with […]

[…] is a direct continuation of my last post on factoring. In this post, we will look into some of the more intricate refinements of Fermat’s Method of […]