Lehman’s Factoring Method

Our object is to present the factoring algorithm of R. Sherman Lehman (Facoring large integers, Math. Comp. 28 (1974), 637–646) in a simplified and transparent manner.

Theorem 1. Suppose that n = ab where a and b are integers such that

n^{1/3} < a ≤ n^{1/2} ≤ b < n^{2/3} .

Then there exist integers k, x, and y such that

4kn = x^{2} − y^{2}, (1)

1 ≤ k ≤ n^{1/3} + 1, (2)

(4kn)^{1/2} ≤ x ≤ (4kn)^{1/2} + \frac{n^{1/6}}{4k^{1/2}} , (3)

0 ≤ y ≤ n^{1/3} . (4)

Proof. We recall that Dirichlet’s theorem asserts that if S is a real number, S ≥ 1, and if θ is a real number, then there exists an integer s, 1 ≤ s ≤ S, such that ∥θs∥ ≤ 1/S. Here ∥u∥ = min_{n∈ℤ} |u − n| is the distance from u to the nearest integer. (This is the natural metric on the circle group 𝕋 = ℝ/ℤ.) Take θ = b/a, S = a/n^{1/3}. Thus there are integers r and s such that

(5)  |\frac{bs}{a} − r| ≤ \frac{n^{1/3}}{a} ,

with 1 ≤ s ≤ a/n^{1/3}. On multiplying by a, it follows that

(6)  |bs − ar| ≤ n^{1/3} .

From (5) we also see that r > 0, since bs/a ≥ 1 and n^{1/3}/a < 1. Also from (5) we see that

r ≤ \frac{bs}{a} + \frac{n^{1/3}}{a} .

Since s ≤ a/n^{1/3}, it follows that

1 ≤ rs ≤ \frac{bs^{2}}{a} + \frac{n^{1/3}s}{a} ≤ n^{1/3} + 1 .

Lehman’s Method

We take k = rs, and note that (2) is satisfied. Set x = ar + bs, y = |ar − bs|. Then

x^{2} − y^{2} = (ar + bs)^{2} − (ar − bs)^{2} = 4arbs = 4kn .

Thus (1) is satisfied. By (6) we see that (4) is also satisfied. It remains to show that (3) holds. To this end we note that x^{2} = 4kn + y^{2}. Hence

(4kn)^{1/2} ≤ x ≤ (4kn + y^{2})^{1/2} ≤ (4kn + n^{2/3})^{1/2} = (4kn)^{1/2}(1 + \frac{1}{4kn^{1/3}} )^{1/2}.

The inequality (1 + u)^{1/2} ≤ 1 + u/2 holds for all real u ≥ −1. Hence the above is

≤ (4kn)^{1/2}(1 + \frac{1}{8kn^{1/3}} ) = (4kn)^{1/2} + \frac{n^{1/6}}{4k^{1/2}} .

Thus we have (3), and the proof is complete.

As a partial converse to Theorem 1, we prove

Theorem 2. Suppose that n ≥ 8, and that there exist integers k, x, and y such that (1)–(4) hold. Then (n, x + y) and (n, x − y) are proper divisors of n.

Proof. From (1) we see that n|(x + y)(x − y). Thus if (n, x + y) = 1, then n|(x − y), and if (n, x − y) = 1, then n|(x + y). Hence it suffices to show that n ∤ (x + y) and that n ∤ (x − y). We achieve this by showing that 0 < x − y ≤ x + y < n. From (2)–(4) we see that

y ≤ n^{1/3} < (4n)^{1/2} ≤ (4kn) ≤ x .

Hence x − y > 0. On the other hand, from (3) and (4) we see that

(7)  x + y ≤ (4kn)^{1/2} + \frac{n^{1/6}}{4k^{1/2}} + n^{1/3} .

Put

f(u) = (4un)^{1/2} + \frac{n^{1/6}}{4u^{1/2}} + n^{1/3}.

It is easy to verify that f is increasing. Set K = [n^{1/3} + 1]. From (7) we deduce that

x + y ≤ 2K^{1/2}n^{1/2} + \frac{n^{1/6}}{4K^{1/2}} + n^{1/3} ≤ 2K^{1/2}n^{1/2} + n^{1/3} + \frac{1}{4}

since K ≥ n^{1/3}. In the opposite direction we find that

K^{1/2} ≤ (n^{1/3} + 1)^{1/2} = n^{1/6}(1 + \frac{1}{n^{1/3}} )^{1/2} ≤ n^{1/6}(1 + \frac{1}{2n^{1/3}} ) = n^{1/6} + \frac{1}{2n^{1/6}} .

Hence x + y ≤ 2n^{2/3} + 2n^{1/3} + 1. Put g(u) = u^{3} − 2u^{2} − 2u − 1. Since g(u) = (u − 3)(u^{2} + u + 1) + 2, it is clear that g(u) > 0 for u ≥ 3. Hence 2n^{2/3} + 2n^{1/3} + 1 < n, and the proof is complete.

Suppose we know that n has no factor ≤ n^{1/3}. Then n is either prime, or the product of two primes. If the system (1)–(4) has no solution, then n is prime. If it has a solution, then the prime factors of n are the numbers (n, x ± y). To search for a solution, put K = [n^{1/3} + 1]. For each x in the interval (3) we test to see whether x^{2} − 4kn is a perfect square, say by the square-detecting algorithm described on pp. 38–41 of H. Cohen, A course in computational algebraic number theory, Springer-Verlag (Berlin). The number of tests is

≪ ∑_{k=1}^{K} (\frac{n^{1/6}}{k^{1/2}} + 1) ≪ n^{1/6}K^{1/2} + K ≪ n^{1/3} .