This 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 Factorization.
Recall the general idea of Fermat’s method for factoring a number : we seek to write as a difference of two squares, . To do this, we start guessing, . We then test whether is a square or not.
A Method due to R. Sherman Lehman
Our first improvement allows to be factored in operations (i.e. addition, subtraction, multiplication, division, and taking a square root).
We will need two lemma before we can introduce the improvement.
For a positive integer , let be the sequence of rational numbers . And let this sequence be arranged in order, from smallest to largest. So, for example, would be
This is a sort of relative of the Farey Series of order n. I will refer to it as a Semi-Farey Series (I made this up, but so be it). So the statement of our lemma
If and are two successive terms of , then we have that and .
Proof: Note that we can generate the Semi-Farey Series of order r in the following manner. Start with and . Between two successive terms of the sequence thus generated, say and , insert their ‘mediant’ whenever $(a+a’)(b + b’) \leq r$. Note that this term is necessarily between the two initial fractions, and is also in reduced form (exactly because , it turns out – it’s an iff relation). This is a known property of Farey Sequences, so I will not include the proof in this write-up (as always, I can clarify through comments/edits – I still feel odd leaving proofs ‘as exercises’).
We will break up the interval with divisions corresponding to the points of . In fact, each point of will correspond to the mediant before and after it, also known as the points that precede and succeed it in the series . If are three successive terms of , then we will associate the subinterval
By Lemma 1, we have that
This brings us to our second lemma.
If is in the subinterval corresponding to in the partition or described above, then
Proof: Again, let and be the terms preceding and following , respectively, in . Suppose also that is in the interval corresponding to with . Then by (1) and Lemma 1,
If we use (2), solve for using the quadratic formula, and remember that , we get
With (3), we get
These complete the proof of the second lemma.
We are now ready to present and prove this method. The main idea is that we will now be looking at . We will divide up the unit interval according to our scheme above.
Suppose that n is a positive odd integer, r is an integer s.t. If , p, q, both primes, and , then there are nonnegative integers x, y, and k s.t.
if k is odd,
and, very importantly,
And if n is a prime, then there are no integers satisfying these requirements.
There is a detail in my proof of this theorem that is hanging me up a bit, so I’ll have to return to it. But let’s take that for granted for a moment, and see how fast we can obtain a factorization of a number with primes.
First, there are divisions done to eliminate any small factors less than . Counting the elementary operations, and assuming that the extraction of a root is one operation, we get operations. Let . This is not quite optimal, but it’s pretty close. Then we see that elementary operations are necessary.
And this can still be improved.