mersenneforum.org New Fermat factors
 Register FAQ Search Today's Posts Mark Forums Read

2018-07-24, 21:27   #254
rogue

"Mark"
Apr 2003
Between here and the

2×11×269 Posts

Quote:
 Originally Posted by ET_ 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.

2018-07-25, 01:36   #255
Gary

"Gary"
Aug 2015
Texas

1100012 Posts

Quote:
 Originally Posted by rogue Sieved with gfndsieve and tested with pfgw64, both on an 07 running Windows 10.
Congrats Mark! What is an 07?

2018-07-25, 06:44   #256
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·2,383 Posts

Quote:
 Originally Posted by Gary Congrats Mark! What is an 07?
I suppose a Core I7...

2018-07-25, 16:24   #257
rogue

"Mark"
Apr 2003
Between here and the

2·11·269 Posts

Quote:
 Originally Posted by Gary Congrats Mark! What is an 07?
Sorry, i7. :-)

 2018-07-26, 22:50 #258 GP2     Sep 2003 22×3×5×43 Posts 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.
2018-07-27, 00:33   #259
Gary

"Gary"
Aug 2015
Texas

72 Posts

Quote:
 Originally Posted by GP2 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.

2018-08-07, 16:11   #260
GP2

Sep 2003

22·3·5·43 Posts

Quote:
 Originally Posted by Gary 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
 fermat.tar.gz (20.0 KB, 26 views)

 2018-08-07, 23:29 #261 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×33×132 Posts 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
2018-08-08, 01:01   #262
GP2

Sep 2003

22×3×5×43 Posts

Quote:
 Originally Posted by Batalov 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?

 2018-08-08, 04:40 #263 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 912610 Posts Yes
2018-08-08, 05:55   #264
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

11×127 Posts

Quote:
 Originally Posted by GP2 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov Factoring 149 2017-02-20 12:06 yourskadhir Miscellaneous Math 5 2012-12-12 04:18 siegert81 Factoring 1 2011-09-05 23:00 Merfighters Factoring 0 2010-04-13 14:16 UberNumberGeek Factoring 6 2009-06-17 17:22

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

Sun Sep 27 08:18:08 UTC 2020 up 17 days, 5:29, 0 users, load averages: 1.90, 1.62, 1.46

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.