Factoring numbers from Ivar Peterson’s The Mathematical Tourist…
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.
I suspect the world would be better if that percentage were even greater.
Apparently 15% of all web traffic is cat related. There's no reason for Brainwagon be any different.
Thanks Mal! I'm trying to reclaim the time that I was using doom scrolling and writing pointless political diatribes on…
Brainwagons back! I can't help you with a job, not least because I'm on the other side of our little…
Congrats, glad to hear all is well.