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 x2 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 x2 − y2 then you could factor N as (x+y)(x−y). Note that x2 must be larger than N. If we start trying values for x starting as soon as x2 > N then we must watch for x2 − 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 x2 − 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 x2 − N vary in a way that is convenient to calculate, as Fermat noted in the 17th century. (x+1)2 − x2 = 2x + 1 and thus we need only add successive odd numbers to calculate successive values for x2 − 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 x2 > N is 3773. We thus start with 37732 − 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 x2 − 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)2 − 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.

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 = 37802 − 2332 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 x2−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.