I found an GNU library for fast multi-precision arithmetic called gmp and decided to try my graphically inspired factoring algorithm. I’m pretty sure it’s just an inefficient version of Lehman’s Method, which is only an improvement over Fermat’s Method. And to illustrate how much a minor player Lehman’s Method is, consider that the best web page I could find for it consists of a photocopied page from a textbook.
Undeterred by reality, I continued on. After working out some details so that my code could factor 10-digit test numbers, I moved on to the smallest RSA challenge number I could find, RSA-140, which was factored in 1999 with tons of computing horsepower. My algorithm didn’t find any factors, of course.
I scaled back to a 20-digit number which I made by multiplying to 10-digit primes. Success! Gaining confidence, I tried the product of two 20-digit primes. No luck there (after 30 minutes), so back to the drawing board.
And it really is luck I’m counting on, since the algorithm is not rigorous — it just looks for factors in places where it can check lots of candidates at once. The real factors may not be in any of those neighborhoods.
Oh well, maybe I should just plug in RSA-2048 and see if I randomly win the prize…