Recently I was standing around in the Computer History Museum’s “visible storage area” where two Lehmer factoring engines were on display. I tried to quickly explain how they worked and only then realized that it was more complex than I had recalled. Indeed perhaps I had never understood from the day that D. H. Lehmer explained them to us in a 1953 Berkeley course on Numerical Analysis.

Here is a reconstruction that you may find convincing on how they work.

First I quote from a page about primes

There is a photograph and explanation of Dr. Lehmer’s factoring machine in the Dover book “Recreations in the Theory of Numbers” by Albert Beiler.

To Recognize a Square

While few people recognize large squares at sight, many will declare quickly that 46082 is not a square. How can this be? Often even they will not know, but there is a simple reason. The unit digit of a square is never 2. Many know this without knowing that they know it.

One proof of this is that the unit digit of x² depends only on the unit digit of x. If you think about how you multiply this will be clear. If you know what “mod 10” means it will be clear in another way. The squares of 0 thru 9 are: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81. 2 is never the unit digit of a square.

What has this to do with factoring? For several centuries people have noted that if you could express N as x² − y² then you could factor N as (x+y)(x−y). Note that x² must be larger than N. If we start trying values for x starting as soon as x² > N then we must watch for x² − N being a square. If we find such an x we are done. But how to quickly recognize squares. Well you can throw them out if they end in 2, but it gets better.

More generally you can quickly throw out many many more by knowing x² − N modulo many different numbers, just as we discarded 46082 since that was 2 mod 10. If we did the calculation radix 29, there would be about half of the low digits that would preclude the number from being a square. Better, these excluded numbers would be different, about half of the time, from the numbers excluded by our radix 10 test. If the radixes to which we keep our candidates are relatively prime we avoid redundant tests. We will use primes.

As we step thru successive values of x, the values of x² − N vary in a way that is convenient to calculate, as Fermat noted in the 17th century. (x+1)² − x² = 2x + 1 and thus we need only add successive odd numbers to calculate successive values for x² − N.

The wheels and bicycle chains of Lehmer’s machines step by one’s however. There is yet one more wrinkle in the design. Lets factor N = 14,234,111. The least x for which x² > N is 3773. We thus start with 3773² − N = 1418, a manifest non-square. We add 2x + 1 to 1418 to get 7547 + 1418 yielding 8965. We will have to continue adding successive odd numbers for a while yet.

We shall switch to mod 7 immediately and indeed keep only the low digit in that radix, for higher digits do not concern us. 1418 mod 7 = 4. Radix 7 squares end in 0, 1, 2 and 4. 1418 is thus a candidate as far as our radix 7 consideration is concerned but we shall exclude it via other radixes. We continue the radix 7 work first, however. We add successive odd numbers to our number 1418 mod 7. Those odd numbers 7547, 7549, ... are, mod 7, {1, 3, 5, 0, 2, 4, 6, 1, 3, 5, 0, ...}. Note that they repeat, every 7 steps. When we add each of those to 1418, mod 7, we get the sequence {4, 5, 1, 6, 6, 1, 5, ...}. The answer as to whether our value for x² − N is possibly square thus repeats: {yes, no, yes, no, no, yes, no, ...}. The 3 “yes”es in this sequence correspond to the 3 holes around a wheel with 7 teeth.

For radix 11 the unit digits of squares are {0, 1, 3, 4, 5, 9}. The unit digits of the candidates for squares are {10, 0, 3, 8, 4, 2, 2, 4, 8, 3, 0, 10,...} and the tests results are {no, yes, yes, no, yes, no, no, yes, no, yes, yes, ...} repeating in groups of 11.

In the Lehmer engine each wheel has a prime number of teeth and each wheel is a different size. You may have noticed from above that where the holes are located in the wheels depends on the number that you are factoring. The smallest wheel has about 100 teeth for mechanical reasons, I suppose. They may not be of prime circumference, but I would bet that the tooth counts were at least relatively prime.

All of the wheels turn at the constant tooth rate. When k teeth have gone by then (x+k)² − N will probably be a square if you can see all the way thru the wheels. The holes must then line up for each square and will seldom do so otherwise.

To finish our example we replace “yes” and “no” by 1 and 0 and align our tests as follows: The successive rows are for periods (wheels) 7, 11 and 10. 10100101010010101001010100101010010101001010100101010010101001010100101010010 01101001011011010010110110100101101101001011011010010110110100101101101001011 0111001110011100111001110011100111001110011100111001110011100111001110
The first column corresponds to our first candidate with x = 3773, we see that we should try x = 3775, 3780 and 3785. We quickly find that 14,234,111 = 3780² − 233² and thus N = 3547 * 4013.

Lets tackle the bicycle chain details specifically. There is a counter attached to the common shaft that counts how many links have passed the sensing station. As we turn the shaft x and the counter increase. We initialize this counter to the least number x, whose square exceeds N, which we want to factor. We must arrange the chains so that as we turn the shaft the chain of length k will have a long screw at the sensing station just if x²−N is a quadratic residue modulo k.

For factoring N we enumerate the quadratic residues of k, and plan the long screws thus:

{
char q[k];
int x = 1+(int)sqrt(N);
  {int j=k; while(j--) q[j]=0;} // Initialize array to zero.
  {int j=k; while(j--) q[j*j%k] = 1;} // set q[j] for those j that are residues.
  printf("The quadratic residue modulo %d are: ", k);
  {int j; for(j=0; j<k; ++j) if(q[j]) printf("%d, ", j); printf("\n");}
  printf("Put long screws at links: ");
  {int j; for(j=x; j<x+k; ++j) if(q[(j*j-N)%k]) printf(" %d", j-x); printf("\n");}
}

The above calculation is possible to do by hand for the cases we need. If you try it you will find that the second half of the second loop sets no more q’s to 1 and that if k is prime the first half sets distinct q’s.

To factor 31937559 run this program which yields this prescription for the long screws.