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.