Patrick's playground

Given the input

 # yafu "factor(10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897)" -threads 4 -v -noecm

if one is patient enough gives this output:

sqrtTime: 1163
NFS elapsed time = 3765830.4643 seconds.
pretesting / nfs ratio was 0.00
Total factoring time = 3765830.6384 seconds


***factors found***

PRP78 = 106603488380168454820927220360012878679207958575989291522270608237193062808643
PRP78 = 102639592829741105772054196573991675900716567808038066803341933521790711307779

What does that mean?
The input number is conveniently chosen from the RSA challenge numbers and was the "world record" until 2003. Advances in algorithms, compilers and hardware have made it possible for me to re-do that record attempt in about a month walltime on a single machine ( 4-core AMD64).

Want to try yourself?

emerge yafu

that's the "easiest" tool to manage. The dependencies are a bit fiddly, but it works well for up to ~512bit, maybe a bit more. It depends on msieve, which is quite impressive, and gmp-ecm, which I find even more intriguing.

If you feel like more of a challenge:

emerge cado-nfs

This tool even supports multi-machine setups out of the box using ssh, but it's slightly intimidating and might not be obvious to figure out. Also for a "small" input in the 120 decimal digits range it was about 25% slower than yafu - but it's still impressive what these tools can do.