mersenneforum.org > Math The fastest primality test for Fermat numbers.
 Register FAQ Search Today's Posts Mark Forums Read

 2011-04-01, 20:17 #1 Arkadiusz   Dec 2009 33 Posts 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)).
2011-04-01, 21:35   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

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

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

2011-04-01, 23:39   #3
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by science_man_88 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.

2011-04-01, 23:50   #4
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by science_man_88 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.

2011-04-02, 00:11   #5
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by science_man_88 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.

 2011-04-05, 16:58 #6 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 203428 Posts 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.
2011-04-05, 19:39   #7
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by science_man_88 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

 Similar Threads Thread Thread Starter Forum Replies Last Post JonathanM Information & Answers 25 2020-06-16 02:47 Erasmus Math 46 2014-08-08 20:05 princeps Math 15 2012-04-02 21:49 T.Rex Math 0 2004-10-26 21:37 T.Rex Math 2 2004-09-11 07:26

All times are UTC. The time now is 15:38.

Mon Jan 30 15:38:23 UTC 2023 up 165 days, 13:06, 0 users, load averages: 1.38, 1.38, 1.24