brainwagon

While reading the section on factorization of large numbers in Knuth’s Seminumerical Algorithms, I encountered a reference to an interesting claim by William Stanley Jevons. I did a google search, and found it in google books:

Knuth was quick to point out that the number that he gave was easily factorable in short order (even by hand, even in Jevons’ day) using Fermat’s method. I of course just handed it to the little program I wrote, and it instantly returned

8,616,460,799 =
	89,681 *
	96,079

Addendum: How does Fermat’s method work? You basically try to express the prime as the difference of two squares. Let’s say that the prime P = u * v. If P = x^2 – y^2, then P = (x + y) (x – y), so the two factors u = x + y and v = x – y. You start by setting x to be just above the sqrt(P), and compute x*x – P. If the remainder is a square, then you have have two factors. Knuth gives several hints on how you could avoid testing many possible squares, but even acting trivially, you would only have to try 55 numbers before finding that…

8616460799 = 92880**2 - 3199**2
8616460799 = 96079 * 89681

Addendum: Lehmer factored this number in 1903. Golomb apparently had a Cryptologia article showing how it could be easily factored with a hand calculator, but I don’t want to pay $37 to get the 3 page reprint.