mersenneforum.org GIMPS' first Fermat factor!
 Register FAQ Search Today's Posts Mark Forums Read

2010-04-05, 04:49   #67
philmoore

"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts

Quote:
 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 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.

2010-04-05, 14:11   #68
warut

Dec 2009

89 Posts

Quote:
 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.

 2010-04-05, 15:45 #69 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 21378 Posts 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.
2010-04-07, 04:54   #70
msft

Jul 2009
Tokyo

26216 Posts

Quote:
 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:
Quote:
 $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:
Quote:
 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".
Attached Files
 result.tar.gz (5.1 KB, 145 views)

 2010-04-07, 17:56 #71 philmoore     "Phil" Sep 2002 Tracktown, U.S.A. 21378 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.
2010-04-07, 22:34   #72
msft

Jul 2009
Tokyo

11428 Posts

Quote:
 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.

 2014-06-07, 09:41 #73 ET_ Banned     "Luigi" Aug 2002 Team Italia 484410 Posts How is the double-check test on the cofactors of F25, F26, F27 going? Luigi
2022-05-13, 22:16   #74
ewmayer
2ω=0

Sep 2002
República de California

101101110011112 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post rajula Factoring 103 2019-03-12 04:02 ET_ Factoring 5 2011-01-13 11:40 ET_ Factoring 21 2010-03-15 21:02 ET_ Factoring 42 2008-12-01 12:50 ET_ Factoring 3 2004-12-14 07:23

All times are UTC. The time now is 22:58.

Sat May 21 22:58:12 UTC 2022 up 37 days, 20:59, 0 users, load averages: 1.26, 1.37, 1.40