mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2014-11-23, 13:47   #1
siegert81
 
Dec 2010

2·37 Posts
Default 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
siegert81 is offline   Reply With Quote
Old 2014-11-23, 14:26   #2
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

C6816 Posts
Default

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
ATH is online now   Reply With Quote
Old 2014-11-23, 21:12   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23·397 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 online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Just curious houding Information & Answers 16 2014-07-19 08:32
Just curious... NBtarheel_33 Information & Answers 0 2011-02-20 09:07
Brent-Suyama extension of P-1 factoring S485122 Math 1 2009-08-23 15:21
Just curious.... schickel Lounge 13 2009-01-06 08:56
brent suyama extension in P-1 bsquared Factoring 9 2007-05-18 19:24

All times are UTC. The time now is 09:28.


Fri Oct 22 09:28:16 UTC 2021 up 91 days, 3:57, 1 user, load averages: 1.07, 1.48, 1.42

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.