Pete's Log: Factoring Pete's Number

Entry #1991, (Coding, Hacking, & CS stuff, Random Crap)
(posted when I was 43 years old.)

I'm not sure if it's a good thing or a bad thing, but I don't really know much about factoring large numbers other than it's hard. An email exchange with Brian and Branden got me thinking about how I've not done much analysis on Pete's Number beyond how many digits it is. So today I did something about that.

Pete's Number is not prime. Through some naive trial division, I quickly found the first two factors of PN are 19 and 53. Slightly less quickly, but still through naive trial division, I found the next factor is 25715687. I then switched to a different strategy, using the first piece of code I was able to get working quickly to find one more factor: 190528216559. At this point I am guessing the low-hanging fruit has all been picked. But I could very well be wrong.

Multiplying those four factors together gives us a 22 digit number. Dividing PN by that number leaves us with 75064 of PN's 75086 digits. I really don't know how to wrap my head around numbers this big.

The algorithm that gave me 190528216559 is called Pollard's rho algorithm, and it is apparently better suited to factoring numbers with small factors. And since I'm now left trying to find the next factor which is going to be larger than 190528216559, I'm pretty sure I'm out of the realm of small factors.

PN requires 249428 bits to represent it in binary and if I'm reading things correctly, the records for factoring large numbers are significantly lower than that. But my understanding is also that there's a lot of luck involved in factoring, depending on what the actual factors are. I will probably at some point spend a little more time looking for a suitable algorithm to run for some longer period of time, even if it's just to find one more factor. Until then, I guess it does no harm to let Pollard's rho run overnight. Since it's single-threaded it's not really taxing Esgerbeastie too much.

Is there any chance of factoring PN in my lifetime? I have no idea. But almost a quarter century after claiming it as mine, at least I finally know it's not prime.