Thu Mar 7 03:45:34 CET 2013
Having fun with integer factorization
Given the input
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?
If you feel like more of a challenge:
# yafu "factor(10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897)" -threads 4 -v -noecmif 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 = 102639592829741105772054196573991675900716567808038066803341933521790711307779What 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 yafuthat'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-nfsThis 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.