mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-04-05, 04:49   #67
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111112 Posts
Default

Quote:
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
Old 2010-04-05, 14:11   #68
warut
 
Dec 2009

89 Posts
Default

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.
IIRC, this is Suyama's trick.
warut is offline   Reply With Quote
Old 2010-04-05, 15:45   #69
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111112 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2010-04-07, 04:54   #70
msft
 
msft's Avatar
 
Jul 2009
Tokyo

10011000102 Posts
Default

Quote:
Originally Posted by philmoore View Post
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
File Type: gz result.tar.gz (5.1 KB, 125 views)
msft is offline   Reply With Quote
Old 2010-04-07, 17:56   #71
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2010-04-07, 22:34   #72
msft
 
msft's Avatar
 
Jul 2009
Tokyo

2·5·61 Posts
Default

Quote:
Originally Posted by philmoore View Post
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.
msft is offline   Reply With Quote
Old 2014-06-07, 09:41   #73
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×151 Posts
Default

How is the double-check test on the cofactors of F25, F26, F27 going?

Luigi
ET_ is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 08:19.


Sun Nov 28 08:19:30 UTC 2021 up 128 days, 2:48, 0 users, load averages: 0.80, 1.00, 1.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.