mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-04-01, 20:17   #1
Arkadiusz
 
Dec 2009

33 Posts
Lightbulb The fastest primality test for Fermat numbers.

The test states that for n > 2,
F(n) is prime iff 5^((F(n)-1)/4) == sqrt(F(n)-1) (mod F(n)).


<Thread posted on April 01, 2011.

Last fiddled with by Arkadiusz on 2011-04-01 at 20:20
Arkadiusz is offline   Reply With Quote
Old 2011-04-01, 21:35   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Arkadiusz View Post
The test states that for n > 2,
F(n) is prime iff 5^((F(n)-1)/4) == sqrt(F(n)-1) (mod F(n)).


<Thread posted on April 01, 2011.
it says the date already:

so you say:

5^(2^(2^n-2)) mod (2^(2^n)+1) = 2^((2^n)/2) according to my research. I'll have to think on this more, I'm not that advanced.

Last fiddled with by science_man_88 on 2011-04-01 at 21:38
science_man_88 is offline   Reply With Quote
Old 2011-04-01, 23:39   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
it says the date already:

so you say:

5^(2^(2^n-2)) mod (2^(2^n)+1) = 2^((2^n)/2) according to my research. I'll have to think on this more, I'm not that advanced.
5^(2^(n+1)-4) mod (2^(2^n)+1) = 2^(2^(n-1)) is what I've worked it down to.
science_man_88 is offline   Reply With Quote
Old 2011-04-01, 23:50   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
5^(2^(n+1)-4) mod (2^(2^n)+1) = 2^(2^(n-1)) is what I've worked it down to.
which I believe simplifies to 5^(2n-2) mod (2^(2^n)+1) = 2^(2n-2). though I'm not great at remembering math when I want it.
science_man_88 is offline   Reply With Quote
Old 2011-04-02, 00:11   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
which I believe simplifies to 5^(2n-2) mod (2^(2^n)+1) = 2^(2n-2). though I'm not great at remembering math when I want it.
okay I have to remember things better.
science_man_88 is offline   Reply With Quote
Old 2011-04-05, 16:58   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Code:
(13:56)>for(n=1,100,print1(isprime(F(n))","))
1,1,1,1,0,0,0,0,0,0,0,0,0,
  *** isprime: user interrupt after 15,468 ms.
(13:57)>for(n=1,100,print1(5^((F(n)-1)/4)%(F(n)) == sqrt(F(n)-1)","))
0,0,1,1,
  *** _^_: user interrupt after 12,782 ms.
F(n)= 2^(2^n)+1

it fails twice in the first 4.
science_man_88 is offline   Reply With Quote
Old 2011-04-05, 19:39   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Code:
(13:56)>for(n=1,100,print1(isprime(F(n))","))
1,1,1,1,0,0,0,0,0,0,0,0,0,
  *** isprime: user interrupt after 15,468 ms.
(13:57)>for(n=1,100,print1(5^((F(n)-1)/4)%(F(n)) == sqrt(F(n)-1)","))
0,0,1,1,
  *** _^_: user interrupt after 12,782 ms.
F(n)= 2^(2^n)+1

it fails twice in the first 4.
forgot the n>2 part
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fastest software for Mersenne primality test? JonathanM Information & Answers 25 2020-06-16 02:47
What are the Primality Tests ( not factoring! ) for Fermat Numbers? Erasmus Math 46 2014-08-08 20:05
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37
Two Primality tests for Fermat numbers T.Rex Math 2 2004-09-11 07:26

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

Wed Dec 2 13:05:25 UTC 2020 up 83 days, 10:16, 3 users, load averages: 4.37, 4.29, 4.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.