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 $N$ can be written as the difference of two squares, i.e. $N = a^2 - b^2$, then we can factor $N$ as $N = (a+b)(a-b)$. 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: $a^4 + 4 b^4 = ( (a+b)^2 + b^2)((a - b)^2 +b^2) =$ $(a^2 + 2ab + 2b^2)(a^2 - 2ab + 2b^2) $ By the way, a Sophie Germain prime is a prime $p$ such that $2p + 1$ 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 $ a$ in the hope that $a^2 - N = c$ is a square, i.e. $c = b^2$ for some integer $b$. So the algorithm proper might be like:
- Set $a = \lceil \sqrt N \rceil$
- $c = a^2 - N$
- Test if c is a square. If it is, look at $a - \sqrt c$ and $a + \sqrt c$. If not, go to step 4.
- Increase a by 1 and set $c = a^2 - N $. 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 $\sqrt N$. 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 $N = 123456789123$ (astoundingly enough, 1234567891 is prime, and was going to be my first example). One sees that $\lceil N \rceil = 351365$. 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:
- $351365^2 - N = 574102$; and $\sqrt{574102} = 757.7$
- $351366^2 - N = 1276833$; and $\sqrt{1276833} = 1129.97$
- $351367^2 - N = 1979566$ and $\sqrt{1979566} = 1406.97$
- $351368^2 - N = 2682301$ and $\sqrt{2682301} = 1637.77$
- ...
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 $351368 - 1637.77 = 349730$. 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 $d > \sqrt N$ and uses Fermat to find factors between $\sqrt N$ and $d$, then the resulting necessary bound for trial division is $d - \sqrt{d^2 - N}$.
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 $0, 1, 4, 5, 9,\; \mathrm{or} \; 16 \mod 20$. Suppose we have calculated a particular value of $a^2 - N \mod 20$. The last two digits are cyclic too - they repeat with each increase by 10. So calculating a couple of values of $a^2 - N$ 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 $\sqrt N$, that doesn't happen too often. But if one can somehow divine (or guess) an approximate ratio of the two factors, suppose something like $ \frac{p}{q}$, then one can choose a rational number $\frac{l}{m}$ near that value and then perform Fermat's Method on $Nlm = pm \cdot du$, which should pull the factors $cv \; \mathrm{and} \; du$ 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 $n$ 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.
Info on how to comment
To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.
bold, italics, and plain text are allowed in comments. A reasonable subset of markdown is supported, including lists, links, and fenced code blocks. In addition, math can be formatted using
$(inline math)$or$$(your display equation)$$.Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.