Factoring numbers from Ivar Peterson’s The Mathematical Tourist

August 18, 2013 | Math | By: Mark VandeWettering

I’m a bit of a math geek. I have been periodically fascinated by the factoring of large numbers, which plays such an important role in modern cryptography algorithms like RSA. I’ve coded a few of the non-trivial factorization algorithms, such as Pollard-rho, but haven’t done a whole lot with it. It mostly remains just a curiosity.

Today, I was scanning my bookshelf, and ran across Ivar Peterson’s The Mathematical Tourist. On page 35 in figure 2.5, he duplicated a list of 10 “most wanted” numbers to factored from 1983. It claims that a “specially programmed supercomputer was able to crack all these numbers in the space of a year”. I was curious: thirty years later, what could a state of the art factoring program do on a typical computer.

For my “state of the art” program, I picked YAFU, a factoring utility that I’ve used before. I had previously used it to factor a 100 digit prime, which took almost 8 hours. I was wondering how it would fair on the 1983 list:

The answer is… darned well.

Number Largest factor Time
2211-1 3593875704495823757388199894268773153439 1.4 seconds
2251-1 12070396178249893039969681 7.98 seconds
2212+1 20946001591429012199281424246257 1.32 seconds
1064+1 515217525265213267447869906815873 6.21 seconds
1067-1 28213380943176667001263153660999177245677 6.93 seconds
1071-1 45994811347886846310221728895223034301839 48.09 seconds
3124+1 21775844224805408923066692226998392022049 3.41 seconds
3128+1 153849834853910661121 .26 seconds
1164+1 7032401262704707649518767703756385761576062060673 3.35 seconds
579-1 344120456368919234899 2.99 seconds

Pretty amazing. My own programs can do some pretty amazing feats, but nothing close to this. The combination of improved code and Moore’s law means that the kind of computing we used to do on Crays is now something we can do on Best Buy. Neat.