mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2018-07-24, 21:27   #254
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

24×7×53 Posts
Default

Quote:
Originally Posted by ET_ View Post
Congrats! Now it's time for me to get one as well

I will update the site tomorrow feel free to pm me the detailed of your setup..
Sieved with gfndsieve and tested with pfgw64, both on an 07 running Windows 10.
rogue is online now   Reply With Quote
Old 2018-07-25, 01:36   #255
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

22·13 Posts
Default

Quote:
Originally Posted by rogue View Post
Sieved with gfndsieve and tested with pfgw64, both on an 07 running Windows 10.
Congrats Mark! What is an 07?
Gary is offline   Reply With Quote
Old 2018-07-25, 06:44   #256
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112408 Posts
Default

Quote:
Originally Posted by Gary View Post
Congrats Mark! What is an 07?
I suppose a Core I7...
ET_ is offline   Reply With Quote
Old 2018-07-25, 16:24   #257
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

24·7·53 Posts
Default

Quote:
Originally Posted by Gary View Post
Congrats Mark! What is an 07?
Sorry, i7. :-)
rogue is online now   Reply With Quote
Old 2018-07-26, 22:50   #258
GP2
 
GP2's Avatar
 
Sep 2003

29·89 Posts
Default

Is there some fast way to verify very big Fermat factors?

For all Mersennes in our typical ranges, modular exponentiation verifies a factor almost instantly. The entire database of millions of known factors can be verified in seconds.

For Fermat factors, though, modular exponentiation slows down drastically when n gets into the tens of thousands. Let alone huge ones like n, m, k = 3329780,3329782,193. There must be some other way.
GP2 is offline   Reply With Quote
Old 2018-07-27, 00:33   #259
Gary
 
Gary's Avatar
 
"Gary"
Aug 2015
Texas

5210 Posts
Default

Quote:
Originally Posted by GP2 View Post
Is there some fast way to verify very big Fermat factors?

For all Mersennes in our typical ranges, modular exponentiation verifies a factor almost instantly. The entire database of millions of known factors can be verified in seconds.

For Fermat factors, though, modular exponentiation slows down drastically when n gets into the tens of thousands. Let alone huge ones like n, m, k = 3329780,3329782,193. There must be some other way.
I do not know of a faster method. If there were a faster method to verify a factor, it seems it could also be used to search for new factors.

I often verify all known factors for n < 1,000,000 whenever I make changes to pmfs or get access to a new system, to make sure it's working correctly. It take about 5 hours, with about 47 minutes being required for n = 960901 alone.
Gary is offline   Reply With Quote
Old 2018-08-07, 16:11   #260
GP2
 
GP2's Avatar
 
Sep 2003

29×89 Posts
Default

Quote:
Originally Posted by Gary View Post
I do not know of a faster method. If there were a faster method to verify a factor, it seems it could also be used to search for new factors.

I often verify all known factors for n < 1,000,000 whenever I make changes to pmfs or get access to a new system, to make sure it's working correctly. It take about 5 hours, with about 47 minutes being required for n = 960901 alone.
I decided to verify all 344 known Fermat factors using a C program that uses the GMP library. It took a bit more than two hours for n, m = 960897, 960901 and about 34 and a half hours for the largest: 3329780, 3329782.

The command was ./factorverify --fermat --vv FERMAT.txt and the files are attached.
Attached Files
File Type: gz fermat.tar.gz (20.0 KB, 30 views)
GP2 is offline   Reply With Quote
Old 2018-08-07, 23:29   #261
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23A316 Posts
Default

Try on the same platform and compare times:
1. download pfgw
2. put all factors in a file
3. run pfgw -N -k -l -gos2 file
Batalov is offline   Reply With Quote
Old 2018-08-08, 01:01   #262
GP2
 
GP2's Avatar
 
Sep 2003

29×89 Posts
Default

Quote:
Originally Posted by Batalov View Post
Try on the same platform and compare times:
1. download pfgw
2. put all factors in a file
3. run pfgw -N -k -l -gos2 file
But I think pfgw is a primality tester?

I just wanted to verify that the known factors of Fermat numbers really are factors, for instance, to check that 193 * 2^3329782 + 1 really does divide 2^(2^3329780) + 1

I used GMP even if it's slower than more specialized software, because it's a very widely used and thoroughly tested library, a precompiled version is a standard component of most Linux distributions, and it's possible to formulate the test in a few simple lines of code, and therefore have extremely high confidence in the result.

Maybe you could use pfgw to verify that the known Fermat factors really are prime factors and not composite factors? But maybe not for the goal I wanted. Or am I misunderstanding?
GP2 is offline   Reply With Quote
Old 2018-08-08, 04:40   #263
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×3,041 Posts
Default

Yes
Batalov is offline   Reply With Quote
Old 2018-08-08, 05:55   #264
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,409 Posts
Default

Quote:
Originally Posted by GP2 View Post
Maybe you could use pfgw to verify that the known Fermat factors really are prime factors and not composite factors?
Just interestingly, if m=k*2^(n+2)+1 | F_n (where k can be even) and 0<k<2^(n+2) then m is prime! And this holds for the known factors in the list (surely) for say n>100.
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 17:00.

Tue Oct 20 17:00:24 UTC 2020 up 40 days, 14:11, 1 user, load averages: 2.58, 2.54, 2.59

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.