20100405, 04:49  #67  
"Phil"
Sep 2002
Tracktown, U.S.A.
45F_{16} Posts 
Quote:
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_{1} 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_{2} as 3 raised to the power of P1 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 cofactor of F_{n}. If they are not equal, C is composite. 4) Take the GCD of the difference of these two residues R_{1}R_{2} 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_{1} is costly for large Fermat numbers, but for small factors P, R_{2} is easily computed. Therefore, it would be quite quick, given R_{1}, to test a new cofactor should a new small factor be discovered in the future. 

20100405, 14:11  #68  
Dec 2009
89 Posts 
Quote:


20100405, 15:45  #69 
"Phil"
Sep 2002
Tracktown, U.S.A.
1119_{10} Posts 
One small error in my above post: The Pepin residue is 3 raised to the power of 2^{2[SUP]n1}[/SUP] mod F_{n}. So my residue R_{1} is actually the square of the Pepin residue.
Yes, it is the Suyama test with the "extension" to prove the cofactor is not a prime power. For references, see Crandall, Doenias, Norrie, and Young, The Twentysecond Fermat Number is Composite, Math. of Comp. 64 (1995), pages 863868, and Crandall, Mayer, and Papadopoulos, The Twentyfourth Fermat Number is Composite, Math. of Comp. 72 (2002), pages 15551572. 
20100407, 04:54  #70  
Jul 2009
Tokyo
262_{16} Posts 
Quote:
Quote:
Quote:


20100407, 17:56  #71 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011111_{2} Posts 
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.

20100407, 22:34  #72  
Jul 2009
Tokyo
2×5×61 Posts 
Quote:
Few month ago, I try rewrite lucdwt.c and failing. 

20140607, 09:41  #73 
Banned
"Luigi"
Aug 2002
Team Italia
2×2,417 Posts 
How is the doublecheck test on the cofactors of F_{25}, F_{26}, F_{27} going?
Luigi 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GIMPS' second Fermat factor!  rajula  Factoring  103  20190312 04:02 
New Fermat factor found!  ET_  Factoring  5  20110113 11:40 
New Fermat factor!  ET_  Factoring  21  20100315 21:02 
New Fermat factor!  ET_  Factoring  42  20081201 12:50 
New Fermat factor found!  ET_  Factoring  3  20041214 07:23 