Fermat Factorization II

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 $latex N$ : we seek to write $latex N$ as a difference of two squares, $latex N = a^2 – b^2 = (a+b)(a-b) \quad ; (a+b), (a-b) > 1$. To do this, we start guessing, $latex a = \lceil \sqrt N \rceil, \; a = \lceil \sqrt N + 1, \; …$. We then test whether $latex a^2 – N$ is a square or not.

A Method due to R. Sherman Lehman

Our first improvement allows $latex N = pq$ to be factored in $latex 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 $latex r$, let $latex S_r$ be the sequence of rational numbers $latex \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, $latex S_{15}$ would be

$latex \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

Lemma 1:
If $latex \frac{a}{b}$ and $latex \frac{a’}{b’}$ are two successive terms of $latex S_r$, then we have that $latex a’b – ab’ = 1$ and $latex (a+a’)(b + b’) > r$.

Proof: Note that we can generate the Semi-Farey Series of order r in the following manner. Start with $latex \frac{0}{1}$ and $latex \frac{1}{1}$. Between two successive terms of the sequence thus generated, say $latex \frac{a}{b}$ and $latex \frac{a’}{b’}$, insert their ‘mediant’ $latex \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 $latex 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’). $latex \large \diamond$

We will break up the interval $latex [0, 1]$ with divisions corresponding to the points of $latex S_r$. In fact, each point of $latex S_r$ will correspond to the mediant before and after it, also known as the points that precede and succeed it in the series $latex S_{r+1}$. If $latex \frac{a’}{b’}, \; \frac{a}{b}, \; \frac{a”}{b”}$ are three successive terms of $latex S_r$, then we will associate the subinterval

$latex \left[ \dfrac{a + a’}{b + b’} , \dfrac{a + a”}{b + b”} \right]$

By Lemma 1, we have that

$latex \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”)} \ \ \ \ \ (1)$

This brings us to our second lemma.

Lemma 2:
If $latex \alpha$ is in the subinterval corresponding to $latex \frac{a}{b}$ in the partition or $latex S_r$ described above, then

$latex \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 $latex \delta = (ab(r + 1))^{-1/2}$

Proof: Again, let $latex \frac{a’}{b’}$ and $latex \frac{a”}{b”}$ be the terms preceding and following $latex \frac{a}{b}$, respectively, in $latex S_r$. Suppose also that $latex \alpha$ is in the interval corresponding to $latex \frac{a}{b}$ with $latex 1 \leq a \leq b$. Then by (1) and Lemma 1,

$latex 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} \ \ \ \ \ (2)$
$latex r + 1 \leq \frac{a}{b} (b + b”)^2 + \frac{b + b”}{b} \ \ \ \ \ (3)$

If we use (2), solve for $latex (b + b’)$ using the quadratic formula, and remember that $latex b + b’ > 0$, we get

$latex b + b’ \geq \dfrac{1 + \sqrt{1 + 4ab(r + 1)}}{2a}$
$latex \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

$latex b + b” \geq \dfrac{(-1 + \sqrt{ 1 + 4ab(r + a) } ) }{2a}$
$latex \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. $latex \diamond$

We are now ready to present and prove this method. The main idea is that we will now be looking at $latex 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. $latex 1 \leq r \leq \sqrt n$ If $latex n = pq$, p, q, both primes, and $latex \sqrt{ \dfrac{n}{r+a} } < p \leq \sqrt n$, then there are nonnegative integers x, y, and k s.t.

$latex x^2 – y^2 = 4k, \quad 1 \leq k \leq r$
$latex x \equiv k + 1 \mod 2$
$latex x \equiv k + n \mod 4$ if k is odd,
$latex 0 \leq x – \sqrt{ 4kn} \leq \dfrac{1}{4(r+1)} \sqrt{ \dfrac{n}{k} }$
and, very importantly,
$latex p = \mathrm{min} ( \mathrm{gcm} (x + y, n), \; \mathrm{gcd} (x – y, n) ) \ \ \ \ \ (\star )$

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 $latex n = pq$ with $latex p, q$ primes.

First, there are $latex O( \left( \dfrac{n}{r} \right) ^{1/2} )$ divisions done to eliminate any small factors less than $latex \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 $latex \sum _{1 \leq k \leq r} O( (\frac{1}{r} \frac{n}{k}^{1/2} + 1)$ operations. Let $latex r = \lfloor 0.1 \cdot n^{1/3} \rfloor$. This is not quite optimal, but it’s pretty close. Then we see that $latex O(n^{1/3})$ elementary operations are necessary.

And this can still be improved.

This entry was posted in Expository, Math.NT, Mathematics and tagged , , , , , , . Bookmark the permalink.

Leave a Reply