GIMPS' first Fermat factor!

[philmoore]

Originally Posted by Andi47

It seems that your results of proving the compositeness of F25, F26 (and now F27) did not make it to Wilfried Keller's Page. Can you please send him an email?

I had an email from Wilfrid Keller just a few days ago in which he discussed this exact topic. He complained that the status of the Fermat co-factors is somewhat murky, although the smaller ones have undoubtedly been tested independently enough times that their status as composites is not in doubt. But he says that even the composite co-factor of F22 does not meet his standard of two matching tests using different hardware and different software.

A simple prp test done on two different machines using different software should verify this status as composite. Doesn't Ernst's MLucas code also contain routines for doing calculations modulo Fermat numbers?

On the other hand, historically, the following test has often been done, and has the advantage that if the full result of the Pepin test is saved, and another factor is discovered in the future, the new cofactor can be tested easily without repeating another long Pepin test. The test is as follows:

1) Compute R₁ as 3 raised to the 2^2[SUP]n[/SUP] power modulo F_n=2^2[SUP]n[/SUP]+1 (the Pepin residue.)
2) Compute R₂ as 3 raised to the power of P-1 mod F_n where P is the product of all known prime factors of F_n.
3) Reduce both of these residues mod C, where C is the remaining co-factor of F_n. If they are not equal, C is composite.
4) Take the GCD of the difference of these two residues R₁-R₂ with C. If the GCD is equal to 1, C cannot be a prime power. (If it is not equal to 1, we have discovered a new factor of C.)

Note that computing R₁ is costly for large Fermat numbers, but for small factors P, R₂ is easily computed. Therefore, it would be quite quick, given R₁, to test a new co-factor should a new small factor be discovered in the future.

[warut]

Originally Posted by philmoore

On the other hand, historically, the following test has often been done, and has the advantage that if the full result of the Pepin test is saved, and another factor is discovered in the future, the new cofactor can be tested easily without repeating another long Pepin test.

IIRC, this is Suyama's trick.

[philmoore]

One small error in my above post: The Pepin residue is 3 raised to the power of 2^2[SUP]n-1[/SUP] mod F_n. So my residue R₁ is actually the square of the Pepin residue.

Yes, it is the Suyama test with the "extension" to prove the co-factor is not a prime power. For references, see Crandall, Doenias, Norrie, and Young, The Twenty-second Fermat Number is Composite, Math. of Comp. 64 (1995), pages 863-868, and Crandall, Mayer, and Papadopoulos, The Twenty-fourth Fermat Number is Composite, Math. of Comp. 72 (2002), pages 1555-1572.

[msft]

Originally Posted by philmoore

A simple prp test done on two different machines using different software should verify this status as composite. Doesn't Ernst's MLucas code also contain routines for doing calculations modulo Fermat numbers?

mprime:

$ cat worktodo.txt
[Worker #1]
PRP=1,2,4194304,+1,"64658705994591851009055774868504577"

$ cat results.txt
[Wed Apr 7 00:53:07 2010]
F22/64658705994591851009055774868504577 is not prime.
RES64: BEAE94F64C12B741. Wd2: 98BEB11D,00000000
_______^^^^^^^^^^^^^^^^^^^^^

genefer.c base program:

F22 = 64658705994591851009055774868504577 C1262577

A = 3^((2^(2^22)+1)/64658705994591851009055774868504577-1) mod (2^(2^22)+1).
B = A mod ((2^(2^22)+1)/64658705994591851009055774868504577).
if B != 1,((2^(2^22)+1)/64658705994591851009055774868504577) is composite;otherwise ((2^(2^22)+1)/64658705994591851009055774868504577) is 3-PRP.

$ cc f22.before.gmp.c -lgmp
$ ./a.out > f22.input.hex
$ cc -o hextobin.out hextobin.c
$ ./hextobin.out < f22.input.hex > f22.input.bin
$ cc -O4 f22.genefer.c -lm -lfftw3
$ time ./a.out < f22.input.bin f22.param //3^((2^(2^22)+1)/64658705994591851009055774868504577-1) mod (2^(2^22)+1)
...
4194000 err= 6.62e-12
65536^262144+1 is a probable composite (err = 5.22e-04).

real 1294m22.005s
user 1291m41.436s
sys 2m43.070s

$ cat genefer.result
4fcded8a4ae1f173763a9.......a59f5a8cd54f8cd2950
$ cc f22.after.gmp.c -lgmp
$ ./a.out < genefer.result > result.txt // A mod ((2^(2^22)+1)/64658705994591851009055774868504577)
$ cat result.txt
377678e9844b29..........63369c894155bceb9bbeae94f64c12b741
______________________________________^^^^^^^^^^^^^^^^^^

((2^(2^22)+1)/64658705994591851009055774868504577) is composite

You can compare "beae94f64c12b741".

[philmoore]

Thank you, this clarifies the cofactor of F22 quite nicely! I also have a note from Ernst saying that future enhancements of MLUCAS should help us come up with verifications of the cofactors of F25, F26, and F27, but it may be a month or more before he can finish the enhancements.

[msft]

Originally Posted by philmoore

I also have a note from Ernst saying that future enhancements of MLUCAS should help us come up with verifications of the cofactors of F25, F26, and F27, but it may be a month or more before he can finish the enhancements.

Good news,

Few month ago, I try rewrite lucdwt.c and failing.

[ET_]

How is the double-check test on the cofactors of F₂₅, F₂₆, F₂₇ going?

Luigi

[ewmayer]

Originally Posted by philmoore

Thank you, this clarifies the cofactor of F22 quite nicely! I also have a note from Ernst saying that future enhancements of MLUCAS should help us come up with verifications of the cofactors of F25, F26, and F27, but it may be a month or more before he can finish the enhancements.

OK, so it took a little bit longer - but from F25 all the way through F30, the latter having required roughly 100x the compute effort of a current GIMPS wavefront-PRP test.