mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   FermatSearch (https://www.mersenneforum.org/forumdisplay.php?f=133)
-   -   New Fermat factors (https://www.mersenneforum.org/showthread.php?t=15449)

philmoore 2011-03-22 21:27

New Fermat factors
 
I see on Wilfrid Keller's site: [url]http://www.prothsearch.net/fermat.html[/url] 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 [url]http://www.fermatsearch.org/news.html[/url] that it was discovered using Mark Rodenkirch's program GMP-Factor. Congratulations to everyone involved!

philmoore 2011-03-22 21:30

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

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

rogue 2011-03-22 21:59

[QUOTE=philmoore;256385]I see on Wilfrid Keller's site: [url]http://www.prothsearch.net/fermat.html[/url] 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 [url]http://www.fermatsearch.org/news.html[/url] that it was discovered using Mark Rodenkirch's program GMP-Factor. Congratulations to everyone involved![/QUOTE]

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 2011-03-23 01:18

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 2011-03-23 01:56

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 2011-03-23 02:17

[QUOTE=ixfd64;256417]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.[/QUOTE]

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

ET_ 2011-03-23 13:09

[QUOTE=rogue;256390]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?[/QUOTE]

Sure I will! :blush:

Yesterday has been a tough day...

Luigi

philmoore 2011-03-23 19:29

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

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 2011-03-24 01:36

I tried using the GMP function mpz_powm to calculate 3[sup]2[sup]2^(n-1)[/sup][/sup] mod F[sub]n[/sub]=2[sup]2[sup]n[/sup][/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[sup]-11[/sup] * 5.98[sup]n[/sup] with R[sup]2[/sup] = 0.9999225.

This means n=25 would take roughly 7*10[sup]8[/sup] sec ~ 22 years.

jasonp 2011-03-24 01:47

[QUOTE=philmoore;256452]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.[/QUOTE]
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 2011-03-24 02:32

[QUOTE=ATH;256471]I tried using the GMP function mpz_powm to calculate 3[sup]2[sup]2^(n-1)[/sup][/sup] mod F[sub]n[/sub]=2[sup]2[sup]n[/sup][/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[sup]-11[/sup] * 5.98[sup]n[/sup] with R[sup]2[/sup] = 0.9999225.

This means n=25 would take roughly 7*10[sup]8[/sup] sec ~ 22 years.[/QUOTE]

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


All times are UTC. The time now is 18:18.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.