mersenneforum.org > Math Curious about the Suyama test
 Register FAQ Search Today's Posts Mark Forums Read

 2014-11-23, 13:47 #1 siegert81   Dec 2010 10010102 Posts Curious about the Suyama test I understand that the Suyama test is used on Fermat number co-factors to see if they're prime. What exactly is the Suyama test? How does it work? Is there an equivalent test for generalized Fermat number co-factors? What is the status of the co-factors of F25, F26, F27, F28... Based on the information in the link below, the status of these co-factors is unknown. Is that true? http://www.prothsearch.net/fermat.html
 2014-11-23, 14:26 #2 ATH Einyen     Dec 2003 Denmark 3,257 Posts I tested the cofactor of F25, F26 and F27 with Prime95, and they are composite, but it is not "official" until it is tested on another hardware with another software. Post #51, #62, #64 in this thread: http://mersenneforum.org/showthread.php?t=12168 Ewmayer is using his own code to test up to F29: http://www.mersenneforum.org/showthread.php?t=18748
2014-11-23, 21:12   #3
ATH
Einyen

Dec 2003
Denmark

3,257 Posts

Regarding the Suyama test:

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

 Similar Threads Thread Thread Starter Forum Replies Last Post houding Information & Answers 16 2014-07-19 08:32 NBtarheel_33 Information & Answers 0 2011-02-20 09:07 S485122 Math 1 2009-08-23 15:21 schickel Lounge 13 2009-01-06 08:56 bsquared Factoring 9 2007-05-18 19:24

All times are UTC. The time now is 05:10.

Thu Jan 27 05:10:40 UTC 2022 up 187 days, 23:39, 1 user, load averages: 2.95, 2.45, 1.94