mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Curious about the Suyama test (https://www.mersenneforum.org/showthread.php?t=19840)

siegert81 2014-11-23 13:47

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?

[URL="http://www.prothsearch.net/fermat.html"]http://www.prothsearch.net/fermat.html[/URL]

ATH 2014-11-23 14:26

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:
[url]http://mersenneforum.org/showthread.php?t=12168[/url]

Ewmayer is using his own code to test up to F29:
[url]http://www.mersenneforum.org/showthread.php?t=18748[/url]

ATH 2014-11-23 21:12

Regarding the Suyama test:

[QUOTE=philmoore;210599]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[SUB]1[/SUB] as 3 raised to the 2[SUP]2[SUP]n[/SUP][/SUP] power modulo F[SUB]n[/SUB]=2[SUP]2[SUP]n[/SUP][/SUP]+1 (the Pepin residue.)
2) Compute R[SUB]2[/SUB] as 3 raised to the power of P-1 mod F[SUB]n[/SUB] where P is the product of all known prime factors of F[SUB]n[/SUB].
3) Reduce both of these residues mod C, where C is the remaining co-factor of F[SUB]n[/SUB]. If they are not equal, C is composite.
4) Take the GCD of the difference of these two residues R[SUB]1[/SUB]-R[SUB]2[/SUB] 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[SUB]1[/SUB] is costly for large Fermat numbers, but for small factors P, R[SUB]2[/SUB] is easily computed. Therefore, it would be quite quick, given R[SUB]1[/SUB], to test a new co-factor should a new small factor be discovered in the future.[/QUOTE]

[QUOTE=philmoore;210655]One small error in my above post: The Pepin residue is 3 raised to the power of 2[SUP]2[SUP]n-1[/SUP][/SUP] mod F[SUB]n[/SUB]. So my residue R[SUB]1[/SUB] is actually the [B]square[/B] 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, [I]The Twenty-second Fermat Number is Composite[/I], Math. of Comp. 64 (1995), pages 863-868, and Crandall, Mayer, and Papadopoulos, [I]The Twenty-fourth Fermat Number is Composite[/I], Math. of Comp. 72 (2002), pages 1555-1572.[/QUOTE]


All times are UTC. The time now is 06:25.

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