How did Cole factor $2^{67}-1$ in 1903?

Question

I just heard a This American Life episode which recounted the famous anecdote about Frank Nelson Cole factoring $N:=2^{67}-1$ as $193{,}707{,}721\times 761{,}838{,}257{,}287$. There doesn't seem to be a historical record of how Cole achieved this; all we have I could find his statement that it took "three years of Sundays". Ira Glass's guest, Paul Hoffman, suggests that this was done by trial division.

But this is nuts, unless I am missing something. Three years of Sundays is $156$ days. If he works $10$ hours a day, that's $93{,}600$ minutes. There are $10{,}749{,}692$ primes up to $193{,}707{,}721$. So that is more than $100$ trial divisions a minute. Worse than that, existing prime tables didn't go high enough: According to Chapter XIII of Dickson's History of the Theory of Numbers, existing tables of primes only ran to something like $10{,}000{,}000$ ($664{,}579$ primes), so for the vast majority of the trial divisions, he'd have to find the primes first. (Lehmer, in 1914, went up to $10{,}006{,}721$.)

But I'm puzzled thinking what else Cole could have done. I skimmed Chapter XIV in Dickson. The methods which seem to have existed at the time are:

• Various ways to speed up trial division for the first $1000$'s of prime numbers. That only helps at the start.

• Writing $N$ as $x^2-y^2$. But $y$ would be $380{,}822{,}274{,}783$, which is an even larger search.

• Since $2$ is a square modulo $N$ (namely, $(2^{34})^2 \equiv 2 \mod N$), we know that all prime factors must be $\pm 1 \bmod 8$, which cuts the time in half. But that's only a factor of $2$.

• Since $N \equiv 3 \mod 4$, there must be a prime factor which is $3 \bmod 4$, so we could try only checking those primes. But this turns out to make things worse, since the SMALL factor is the one which is $1 \bmod 4$.

• If we could write $N$ as a sum of squares in two ways, we'd be done. But $N$ isn't a sum of squares, since it is $3 \bmod 4$. Generalizations to other positive definite quadratic forms were known at the time, but how would Cole know which quadratic form to try?

• A variant of the above would be to use the quadratic form $2x^2-y^2$, since we already have one solution. Dickson doesn't mention any work using mixed signature forms, but it would work. And since $\mathbb{Z}[\sqrt{2}]$ is a PID, there must be a second way to write $N$ as $2x^2-y^2$, not related to the previous by units of $\mathbb{Z}[\sqrt{2}]$. I'm not sure how large this second solution is.

So, my question is:

How could someone find the prime factors of $N$ in $100{,}000$ minutes of hand computation?

Answer 1

The paper by Cole "On the factoring of large numbers." BAMS (1903) discusses this.

Answer 2

Summarizing what Cole says for my own understanding: By methods which he doesn't make clear to me, Cole found solutions to $x^2 \equiv a \bmod N$ for many small values of $a$ and convinced himself (but not rigorously) that many other $a$ were not achievable. This gave many congruence conditions on possible divisors of $N$. In this manner, he was rapidly able to filter the integers up to $16$ million down to just a few trial divisors, none of which worked. (Note that it is okay if he winds up trying some non-prime divisors in the process.)

At this point, he used his data in a different way. Suppose that $N=pq$ and look at one of his small values of $a$, for example $a=-7$. Since he knew $-7$ was square modulo $N$, we deduce that $p$ and $q$ are each $ 1$ , $2$ or $4 \bmod 7$ and, since $2^{67}-1 \equiv 1 \bmod 7$, we get that $(p,q)$ is $(1,1)$, $(2,4)$ or $(4,2) \bmod 7$. This means that $(p+q)/2 \equiv 1$ or $3 \bmod 7$. In this way, he obtained many modular conditions on $(p+q)/2$, giving a few possibilities. For each possibility $x$, he checked whether $x^2-N$ was square. When he tried the right option, he had $x^2-N = ((p+q)/2)^2 - N = ((p-q)/2)^2$ and won.

Answer 3

You assume that he did his computations by hand, but that's not a necessity. At the time, mechanical calculators (arithmometers) were widely available. It's not at all unusual that the kind of person who devotes Sundays to factoring would own one.

These machines are orders of magnitude faster and more precise than doing computations by hand. This model from 1875 could handle 20-digit numbers, for instance. ($2^{67}$ has 21 digits.)

Multiplying two numbers on one of them takes a few seconds. To multiply 761838257287 by 193707721, for instance (assuming they fit on the machine, which isn't the case for the machine in the picture --- it can multiply two ten-digit numbers at most, natively), you'd have to:

• reset the machine by turning a certain small reset crank or switch.
• slide up and down the 10 linear switches in the lower-right part, one by one, to the positions corresponding to the digits of 761838257287.
• turn the crank one time, then slide the upper slab to the right by one notch, then turn the crank again 2 times, then move the slab, then turn it 7 times, and so on for each digit of the second number, for a total of 1+9+3+7+0+7+7+2+1 = 37 turns. The number of turns made in each position is displayed on an indicator, to reduce mistakes. (those ten tiny circular holes on top of the linear switches, I think).
• then you can read off the digits of the result in the upper row of 20 rotating indicators.

Similarly, to divide (with remainder) a certain number $A<10^{20}$ by a $B<10^{10}$, you can do the following, which directly mimics grade school division:

• set up the machine so that the row of digits in the upper moving slab shows the number $A$.
• slide the upper slab to the right a certain number $k$ of times, so that the most significant digit of $A$ is aligned with the most significant digit of $B$.
• turn the crank in the reverse direction between 0 and 10 times; each turn subtracts $10^k B$ from $A$. Stop when you'd reach below zero. In practice, these machines work modulo $10^{20}$, and many models make a bell sound when you move below zero; so you can turn the crank until you hear the bell, then make one turn back.
• slide the upper slab one notch to the left, and continue by subtracting multiples of $10^{k-1}B$ from the number in the top row. Continue until the upper slab is back to the original position (which means you're subtracting multiples of $10^{0}B$ and can't slide it left anymore. Then you can read the remainder on the top row, and the quotient on a tiny (barely visible here) row of numbers below it, which kept track of how many turns were made in each position.

I don't have much manual skill with these machines, but it looks like the method could be performed in a completely mindless way --- turn the crank until you hear the bell, turn it back one turn, slide left, repeat.

Answer 4

While the question how Cole factored $N := 2^{67}−1$ has already been answered by quid, David Speyer's more general question is how someone could find the factors of that number in $100000$ minutes of hand computation.

Assuming one would try Pollard's rho algorithm and compute the sequence $x_1 := 1$, $x_{k+1} := (x_k^2+1) \!\! \mod n$, then one would find that $\gcd(x_{8064} - x_{2536},n) = 193707721$. This requires $2 \cdot 8063 = 16126$ multiplications mod $n$ (in practice a bit more, since one doesn't take Gcd's after every step), and taking a couple of Gcd's with $n$. Now, doing a multiplication modulo a $21$-digit number in $6$ minutes by hand is maybe tough, but plausibly possible.

Another option would be to try the quadratic sieve. In this case, we try to see whether what FactInt's MPQS routine does could be done by hand as well. --

FactInt chooses a factor base of size $92$, and takes $4096$ as length of the sieving interval. With this, it takes $8$ polynomials until it finds enough factorizations over the factor base (including relations with a large factor) to obtain a factorization of $N$. Doing the sieving by hand on standard A4 $5$mm-squared paper by marking squares would require $2$ sheets of paper for each sieving interval of $4096$ numbers, as there are $41 \cdot 58 = 2378$ squares on each sheet, hence the sieving would take in total $8 \cdot 2 = 16$ sheets of paper.

Finally one would need to find the nullspace of a sparse $\mathbb{F}_2$ matrix with $114$ columns and a few more rows, which one could write down on $6$ of the said sheets of squared paper glued together if one uses one square for each entry. Doing Gaussian elimination would now probably be a little tedious by hand and would likely take up the rest of the writing pad, but it would certainly not be infeasible with a supply of time as generous as the assumed $100000$ minutes.

Answer 5

I imagine it took Cole longer than he said. If I were to undertake the project, here is how I would proceed:

I would start sifting the set of numbers {134k + 1} for primes. One can modify the Sieve of Eratosthenes to produce quite a few of the primes quickly, and then just do certain members of the arithmetic progression whether they are prime or not (say those coprime to 2310).

I might do trial division, but for the larger numbers, modular exponentiation/ multiplication is the way to go. I make a table up to 2^33 of powers of two. Given p, I multiply by the largest power of 2 less than p to get a product less than p and then double that carefully and subtract p, and then repeat until I get to 2^67 mod p. The nice thing about this is that I can leverage earlier work: If I have 2^s = p + K for some small K, the next prime q = p +r will have 2^s = p + (K-r) + r, and so some work can be saved on some iterations. I can see processing two or three primes in parallel this way by hand.

Gerhard "Wonder Which TI Was Used" Paseman, 2015.05.22