mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2011-03-22, 21:27   #1
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default New Fermat factors

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 is offline   Reply With Quote
Old 2011-03-22, 21:30   #2
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2011-03-22, 21:59   #3
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,849 Posts
Default

Quote:
Originally Posted by philmoore View Post
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?
rogue is online now   Reply With Quote
Old 2011-03-23, 01:18   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

7,013 Posts
Default

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?
Prime95 is offline   Reply With Quote
Old 2011-03-23, 01:56   #5
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

43638 Posts
Default

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.

Last fiddled with by ixfd64 on 2011-03-23 at 01:56
ixfd64 is offline   Reply With Quote
Old 2011-03-23, 02:17   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×11×131 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
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
ATH is offline   Reply With Quote
Old 2011-03-23, 13:09   #7
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

129616 Posts
Default

Quote:
Originally Posted by rogue View Post
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
ET_ is offline   Reply With Quote
Old 2011-03-23, 19:29   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

1,117 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
philmoore is offline   Reply With Quote
Old 2011-03-24, 01:36   #9
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

2×11×131 Posts
Default

I tried using the GMP function mpz_powm to calculate 32[sup]2^(n-1)[/sup] mod Fn=22[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.98n with R2 = 0.9999225.

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

Last fiddled with by ATH on 2011-03-24 at 01:37
ATH is offline   Reply With Quote
Old 2011-03-24, 01:47   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67078 Posts
Default

Quote:
Originally Posted by philmoore View Post
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.
jasonp is offline   Reply With Quote
Old 2011-03-24, 02:32   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101011000012 Posts
Default

Quote:
Originally Posted by ATH View Post
I tried using the GMP function mpz_powm to calculate 32[sup]2^(n-1)[/sup] mod Fn=22[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.98n with R2 = 0.9999225.

This means n=25 would take roughly 7*108 sec ~ 22 years.
By FFT that should be O(4^n*n*log(n)).
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New Generalized Fermat factors Batalov Factoring 149 2017-02-20 12:06
Best case Fermat Factors yourskadhir Miscellaneous Math 5 2012-12-12 04:18
Generalized Fermat factors - why? siegert81 Factoring 1 2011-09-05 23:00
Weighted Fermat factors Top 20 Merfighters Factoring 0 2010-04-13 14:16
Fermat 12 factors already found? UberNumberGeek Factoring 6 2009-06-17 17:22

All times are UTC. The time now is 12:28.

Fri Aug 7 12:28:16 UTC 2020 up 21 days, 8:15, 1 user, load averages: 2.39, 2.26, 2.30

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.