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

24·3·52·7 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

24×3×52×7 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

24×3×52×7 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

203208 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

100000110100002 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

20D016 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 06:45.


Mon Sep 26 06:45:49 UTC 2022 up 39 days, 4:14, 0 users, load averages: 1.09, 1.20, 1.16

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔