View Single Post
Old 2014-11-23, 21:12   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

32·5·71 Posts
Default

Regarding the Suyama test:

Quote:
Originally Posted by philmoore View Post
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.
Quote:
Originally Posted by philmoore View Post
One small error in my above post: The Pepin residue is 3 raised to the power of 22[SUP]n-1[/SUP] mod Fn. So my residue R1 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.
ATH is offline   Reply With Quote