New Fermat factors

[philmoore]

I see on Wilfrid Keller's site: http://www.prothsearch.net/fermat.html that two new factors of Fermat numbers have been discovered recently including a 49-digit factor of F17 by David Bessel that appears to have been discovered using ECM with prime95/mprime. The other factor, the second known of F42 is credited to Roman Maznichenko, and Keller credits Durman for the software, but Luigi says over at http://www.fermatsearch.org/news.html that it was discovered using Mark Rodenkirch's program GMP-Factor. Congratulations to everyone involved!

[philmoore]

I see David's factor was already discussed in this thread:
http://www.mersenneforum.org/showthread.php?t=15358
I don't know how I overlooked it, congrats again!

Moderators: feel free to append this to the other thread.

[rogue]

Originally Posted by philmoore

I see on Wilfrid Keller's site: http://www.prothsearch.net/fermat.html that two new factors of Fermat numbers have been discovered recently including a 49-digit factor of F17 by David Bessel that appears to have been discovered using ECM with prime95/mprime. The other factor, the second known of F42 is credited to Roman Maznichenko, and Keller credits Durman for the software, but Luigi says over at http://www.fermatsearch.org/news.html that it was discovered using Mark Rodenkirch's program GMP-Factor. Congratulations to everyone involved!

Cool! AFAIK this is the first Fermat factor found with my software.

BTW Luigi, it is GMP-Fermat, not GMP-Factor. Would you mind fixing it?

[Prime95]

In reviewing Keller's page, is there any reason why F25 and F26 (and maybe F27) cannot be moved to the "Factorizations known to be incomplete" section?

Who wants to volunteer to do the PRP tests?

[ixfd64]

ATH tested those cofactors a while back and found them to be composite. However, I think that Wilfrid wants them to be independently verified first.

[ATH]

Originally Posted by ixfd64

ATH tested those cofactors a while back and found them to be composite. However, I think that Wilfrid wants them to be independently verified first.

Yeah I did them back following GIMPS first fermat factor. The discussion is in the same thread, post #35-#69: http://www.mersenneforum.org/showthread.php?t=12168

[ET_]

Originally Posted by rogue

Cool! AFAIK this is the first Fermat factor found with my software.

BTW Luigi, it is GMP-Fermat, not GMP-Factor. Would you mind fixing it?

Sure I will!

Yesterday has been a tough day...

Luigi

[philmoore]

Originally Posted by ATH

Yeah I did them back following GIMPS first fermat factor. The discussion is in the same thread, post #35-#69: http://www.mersenneforum.org/showthread.php?t=12168

The idea left hanging there was to do the Suyama test once using the GWNUM routines, and then to do it again using MLUCAS when Ernst got the 2^n+1 code added to it, then compare the residues and verify that they match. I could easily generate the residues with pfgw, but performing the GCD computation will take some thought. SCRIPT files in pfgw are not an efficient way to go on this, because SCRIPT is interpreted, and the overhead makes GCD computations way too slow for numbers the size of F25-F27. (Trust me, I've tried it!) But perhaps it could be done directly using George's GCD routine in the GWNUM library. GMP is another possibility, it would be interesting to compare with GWNUM on large numbers. Perhaps since Wilfrid Keller would like to see the computation done with two different sets of software, the GCD should be done both ways.

[ATH]

I tried using the GMP function mpz_powm to calculate 3^{2[sup]2^(n-1)}[/sup] mod F_n=2^2[sup]n[/sup]+1 and timed it:

n=14: 1.945s
n=15: 12.143s
n=16: 73.373s
n=17: 415.121s

this suggest the time is roughly 2.6*10^-11 * 5.98ⁿ with R² = 0.9999225.

This means n=25 would take roughly 7*10⁸ sec ~ 22 years.

[jasonp]

Originally Posted by philmoore

GMP is another possibility, it would be interesting to compare with GWNUM on large numbers. Perhaps since Wilfrid Keller would like to see the computation done with two different sets of software, the GCD should be done both ways.

GMP has had a sub-quadratic GCD for several years now, and even F31-size GCDs take only a few hours and < 5GB of memory.

[R. Gerbicz]

Originally Posted by ATH

I tried using the GMP function mpz_powm to calculate 3^{2[sup]2^(n-1)}[/sup] mod F_n=2^2[sup]n[/sup]+1 and timed it:

n=14: 1.945s
n=15: 12.143s
n=16: 73.373s
n=17: 415.121s

this suggest the time is roughly 2.6*10^-11 * 5.98ⁿ with R² = 0.9999225.

This means n=25 would take roughly 7*10⁸ sec ~ 22 years.

By FFT that should be O(4^n*n*log(n)).