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 $N$ : we seek to write $N$ as a difference of two squares, $N = a^2 - b^2 = (a+b)(a-b) \quad ; (a+b), (a-b) > 1$. To do this, we start guessing, $a = \lceil \sqrt N \rceil, \; a = \lceil \sqrt N + 1, \; ...$. We then test whether $a^2 - N$ is a square or not.
A Method due to R. Sherman Lehman
Our first improvement allows $N = pq$ to be factored in $O(N^{1/3})$ 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 $r$, let $S_r$ be the sequence of rational numbers $\frac{a}{b}; \; \; 0 \leq a \leq b, \; b > 0, \; ab \leq r; \; \; \mathrm{gcd} (a,b) = 1$. And let this sequence be arranged in order, from smallest to largest. So, for example, $S_{15}$ would be
$\frac{0}{1}, \; \frac{1}{15}, \; \frac{1}{14}, \; \frac{1}{13}, \; \frac{1}{12}, \; \frac{1}{11}, \; \frac{1}{10}, \; \frac{1}{9}, \; \frac{1}{8}, \; \frac{1}{7}, \; \frac{1}{6}, \; \frac{1}{15}, \; \frac{1}{4}, \; \frac{2}{7}, \; \frac{1}{3}, \; \frac{2}{5}, \; \frac{1}{2}, \; \frac{3}{5}, \; \frac{2}{3}, \; \frac{3}{4}, \; \frac{1}{1}$
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 $\frac{a}{b}$ and $\frac{a'}{b'}$ are two successive terms of $S_r$, then we have that $a'b - ab' = 1$ and $(a+a')(b + b') > r$.
Note that we can generate the Semi-Farey Series of order r in the following manner. Start with $\frac{0}{1}$ and $\frac{1}{1}$. Between two successive terms of the sequence thus generated, say $\frac{a}{b}$ and $\frac{a'}{b'}$, insert their 'mediant' $\frac{a + a'}{b + b'}$ 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 $a'b - ab' = 1$, 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').$\diamondsuit$
We will break up the interval $[0, 1]$ with divisions corresponding to the points of $S_r$. In fact, each point of $S_r$ will correspond to the mediant before and after it, also known as the points that precede and succeed it in the series $S_{r+1}$. If $\frac{a'}{b'}, \; \frac{a}{b}, \; \frac{a''}{b''}$ are three successive terms of $S_r$, then we will associate the subinterval
$$\left[ \dfrac{a + a'}{b + b'} , \dfrac{a + a''}{b + b''} \right]$$
By Lemma 1, we have that
$$\dfrac{a + a'}{b + b'} = \dfrac{a}{b} - \dfrac{1}{b(b+b')}, \qquad \dfrac{a + a''}{b + b''} = \dfrac{a}{b} + \dfrac{1}{b(b+b'')} \tag{1}$$
This brings us to our second lemma.
If $\alpha$ is in the subinterval corresponding to $\frac{a}{b}$ in the partition or $S_r$ described above, then $$\frac{a}{b} ( 1 - \delta (a + \frac{1}{4} \delta ^2) ^{1/2} + \frac{1}{2} \delta ^2 ) \leq \alpha \leq \frac{a}{b} (1 + \delta (1 + \frac{1}{4} \delta ^2) ^{1/2} + \frac{1}{2} \delta ^2)$$ where $\delta = (ab(r + 1))^{-1/2}$
Again, let $\frac{a'}{b'}$ and $\frac{a''}{b''}$ be the terms preceding and following $\frac{a}{b}$, respectively, in $S_r$. Suppose also that $\alpha$ is in the interval corresponding to $\frac{a}{b}$ with $1 \leq a \leq b$. Then by (1) and Lemma 1, $$r + 1 \leq (a + a')(b + b') = \dfrac{a + a'}{b + b'} (b + b')^2 = \dfrac{a}{b} (b + b')^2 - \dfrac{b + b'}{b} \tag{2}$$ and $$r + 1 \leq \frac{a}{b} (b + b'')^2 + \frac{b + b''}{b} \tag{3}$$
If we use (2), solve for $(b + b')$ using the quadratic formula, and remember that $b + b' > 0$, we get $$b + b' \geq \dfrac{1 + \sqrt{1 + 4ab(r + 1)}}{2a}$$ and $$\dfrac{1}{b(b + b')} \leq \dfrac{a}{b} \dfrac{2}{1 + \sqrt{1 + 4ab(r+1)} } = \dfrac{a}{b}( - \frac{1}{2} \cdot \delta ^2 + \sqrt{ \delta ( 1 + \frac{1}{4} + \delta^2) })$$
With (3), we get $$b + b'' \geq \dfrac{(-1 + \sqrt{ 1 + 4ab(r + a) } ) }{2a}$$ and $$\dfrac{1}{b(b + b'')} \leq \dfrac{a}{b} ( \frac{1}{2} \delta^2 + \delta \sqrt{1 + \frac{1}{4} \delta^2} )$$
These complete the proof of the second lemma.$\diamondsuit$
We are now ready to present and prove this method. The main idea is that we will now be looking at $x^2 - y^2 = 4kn, \; k = ab; \; 1 \leq k \leq r$. 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. $1 \leq r \leq \sqrt n$ If $n = pq$, p, q, both primes, and $\sqrt{ \dfrac{n}{r+a} } < p \leq \sqrt n$, then there are nonnegative integers x, y, and k s.t.
$$x^2 - y^2 = 4k, \quad 1 \leq k \leq r$$ $$x \equiv k + 1 \mod 2$$ $$x \equiv k + n \mod 4$$ if k is odd, $$0 \leq x - \sqrt{ 4kn} \leq \dfrac{1}{4(r+1)} \sqrt{ \dfrac{n}{k} }$$ and, very importantly, $$p = \mathrm{min} ( \mathrm{gcm} (x + y, n), \; \mathrm{gcd} (x - y, n) ) \tag{*}$$ 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 $n = pq$ with $p, q$ primes.
First, there are $O( \left( \dfrac{n}{r} \right) ^{1/2} )$ divisions done to eliminate any small factors less than $\left( \dfrac{n}{r+1} \right) ^ {1/2}$. Counting the elementary operations, and assuming that the extraction of a root is one operation, we get $\sum _{1 \leq k \leq r} O( (\frac{1}{r} \frac{n}{k}^{1/2} + 1)$ operations. Let $r = \lfloor 0.1 \cdot n^{1/3} \rfloor$. This is not quite optimal, but it's pretty close. Then we see that $O(n^{1/3})$ elementary operations are necessary.
And this can still be improved.
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.