# mixedmath

Explorations in math and programming
David Lowry-Duda

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.

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)$$.