View Single Post
Old 2010-04-05, 04:49   #67
philmoore's Avatar
Sep 2002
Tracktown, U.S.A.

3·373 Posts

Originally Posted by Andi47 View Post
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 R1 as 3 raised to the 22[SUP]n[/SUP] power modulo Fn=22[SUP]n[/SUP]+1 (the Pepin residue.)
2) Compute R2 as 3 raised to the power of P-1 mod Fn where P is the product of all known prime factors of Fn.
3) Reduce both of these residues mod C, where C is the remaining co-factor of Fn. If they are not equal, C is composite.
4) Take the GCD of the difference of these two residues R1-R2 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 R1 is costly for large Fermat numbers, but for small factors P, R2 is easily computed. Therefore, it would be quite quick, given R1, to test a new co-factor should a new small factor be discovered in the future.
philmoore is offline   Reply With Quote