Lehman’s Factoring Algorithm
August 22, 2017
The oldest algorithm for factoring integers, still used today, is trial division, which takes time proportional to the square root of the number being factored. In the 17th century, Pierre de Fermat invented a different algorithm, based on finding a difference of squares, that also takes time proportional to the square root of the number being factored, but works well when a number’s two factors are both near the square root of the number; we studied Fermat’s algorithm in a previous exercise. In today’s exercise we will study a factoring algorithm due to R. Sherman Lehman that modifies Fermat’s algorithm so it takes time proportional to the cube root of the number being factored. Lehman’s algorithm suffers the same problem as Fermat’s — it is slow unless the two factors are near each other — but in cases where it is appropriate, it is much faster than Fermat’s algorithm.
Let’s begin by recapping Fermat’s algorithm. It starts by taking the smallest integer larger than the square root of the number n being factored, call that number a, then increases a by 1 until b = a2 − n is a square, at which point we have n = a2 − b2 = (a − b) (a + b) = n by algebraic identity. Pomerance likes to use the example 8051 = 902 − 72 = (90 − 7) (90 + 7) = 83 × 97; he tells the story of an arithmetic contest in his school days that he lost because he didn’t recognize the difference of squares. Here is how Crandall and Pomerance give Fermat’s algorithm in their book Prime Numbers: A Computational Perspective:
Algorithm 5.1.1 (Fermat method). We are given an odd integer n > 1. This algorithm either produces a nontrivial divisor of n or proves n prime.
1. [Main loop]
for (⌈√n⌉ ≤ a ≤ (n + 9) / 6) {
if (b = √(a2 − n) is an integer) return a − b
}
return "n is prime"
In their book, Crandall and Pomerance prove the odd termination condition of the loop.
There are tricks, both mathematical and computational, that can speed up Fermat’s algorithm, but in general you will have to accept that it is pretty slow, because no matter what you do you have to count from √n to n, which is a long way.
One useful trick is to multiply n by a multiplier. Crandall and Pomerance give the example of n = 2581. Fermat’s algorithm has us start with a = 51 and take 9 square roots, finding a difference of squares when a = 59, so that 592 − 2581 = 900 = 302 and 2581 = (59 − 30) (50 + 30) = 29 × 89. But if we take the multiplier k = 3, then kn = 3 × 2581 = 7743, Fermat’s algorithm starts with a = 88, and on the first iteration through the loop b = 882 − 7743 = 1, the factorization of kn = (88 − 1) (88 + 1) = 87 × 89, and the factorization of n = gcd(87, n) × gcd(89, n) = 29 × 89.
Of course, there is no way to know a priori that multiplier k = 3 leads to a quick factorization. Lehman’s method systematizes the search for a good multiplier. Here is how Crandall and Pomerance give Lehman’s algorithm:
Algorithm 5.1.2 (Lehman method). We are given an integer n > 21. This algorithm either provides a nontrivial factor of n or proves n prime.
1. [Trial division]
Check whether n has a nontrivial divisor d ≤ n1/3, and if so, return d.
2. [Loop]
for (1 ≤ k ≤ ⌈n1/3) {
for (⌈√(4kn⌉)⌉ ≤ a ≤ ⌊√(4kn) + n1/6 / (4√k)⌋) {
if (b = √(a2 − 4kn) is an integer) return gcd(a + b, n)
}
}
return "n is prime"
Again, Crandall and Pomerance prove the odd termination condition in their book, and also the odd input condition n > 21. They also prove that Lehman’s algorithm takes time proportional to the cube root of the number being factored. Lehman’s algorithm is of historical importance, as it was the first factoring algorithm to take less than time proportional to the square root of the number being factored, but it is was never used in practice, as Jon Pollard’s rho algorithm was published shortly after Lehman’s algorithm, and it has both a better time complexity, taking time proportional to the fourth root of the number being factored, and is also significantly faster in practice.
Your task is to implement the factoring algorithms of Fermat and Lehman; you might want to do some timing experiments to compare them to each other and to naive trial division. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python.
def td_factor(n, limit=10**6): 'stop after first factor found' for f in accumulate(chain((2, 1, 2, 2), cycle((4, 2, 4, 2, 4, 6, 2, 6)))): if f*f > n or f > limit: return 0 if n % f == 0: return f def fermat(n): for a in range(isqrt(n)+1, (n + 9) // 6 + 1): b = a * a - n if is_square(b): return a - isqrt(b) return 0 def lehman(n): s3n = ceil(n ** (1/3)) f = td_factor(n, limit=s3n) if f: return f for k in range(1, s3n + 1): sk = 2*sqrt(k*n) for a in range(ceil(sk), floor(sk + n**(1/6) / (4*sqrt(k)))+1): b = a*a - 4*k*n if is_square(b): return gcd(a + isqrt(b), n) return 0I shall show this to my father, he celebrated his 89th birthday yesterday. He will be pleased that the algorithm that carries his name is still in use.