New Fermat factors

[rogue]

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.

[Gary]

Originally Posted by rogue

Sieved with gfndsieve and tested with pfgw64, both on an 07 running Windows 10.

Congrats Mark! What is an 07?

[ET_]

Originally Posted by Gary

Congrats Mark! What is an 07?

I suppose a Core I7...

[rogue]

Originally Posted by Gary

Congrats Mark! What is an 07?

Sorry, i7. :-)

[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.

[Gary]

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.

[GP2]

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.

[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

[GP2]

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?

[Batalov]

Yes

[R. Gerbicz]

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.