Daily Archives: 6/29/2009

YAFU factors a 100 digit number for me…

On Friday, I left YAFU factoring a 100 digit number. I returned to find that it had discovered:

57790 93002 97410 10009 81807 59480 96292 62385 64081 79034 01512 68667
60949 55202 41611 02063 00992 86747 29621 36069 = 
85404 41503 10330 70274 85067 33621 20528 36393 71759 33321 * 
67667 37996 94567 83271 38746 19751 00109 79749 75402 10589

It took about 7.6 hours of compute time.

Addendum: I was reading “Factoring by electronic mail”, a 1990 paper by Lenstra and Manasse, and they listed some times for factorization of some large numbers. In Table 4, they list a bunch of challenging numbers, including the 93 digit composite factor of 7139+1. Their system took 13 days. YAFU was able to factor it in about 70 minutes on my current desktop machine:

Total factoring time = 4283.6700 seconds


***factors found***

P1 = 2
P1 = 2
P1 = 2
P3 = 557
PRP22 = 5312442648966139012589
PRP57 = 651666519182971782190402264651775450396158503528225547931
PRP36 = 190705279598948669274660288301207361

It found the small primes via trial division, the 22 digit prime factor via the ECM method, and then churned the rest out using the quadratic sieve.