mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-04-10, 05:03   #1
princeps
 
Nov 2011

22×3 Posts
Default Lucasian Criteria for the Primality of 2^n+3

Definition : Let  P_n be a number of the form :

P_n=2^n+3

Definition : Let's define starting seed S as :

S = \begin{cases} 3, & \text{if }n \equiv 0 \pmod 4 \\ 8, & \text{if }n \equiv 2 \pmod 4\\ 7, & \text{if }n \equiv 3 \pmod 4 \end{cases}

Definition : Let's define sequence S_i as :

S_i=S^2_{i-1}-2 ~\text { with }~ S_0=S

Conjecture :

P_n ; (n \geq 3) ~\text{ is a prime iff }~ S_{n-1} \equiv S_0 \pmod {P_n}

I have checked conjecture for all primes in this sequence with exponent below 200000 . Also , for n<5000 there is no composite P_n that satisfies relation from conjecture .

Are there similar criteria in the literature for the numbers of this form ?
princeps is offline   Reply With Quote
Old 2012-04-10, 05:15   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

[Stupid Question]
What if n mod 4 = 1?
[/SQ]
Also, the LL (and LLR) test(s) start with S0 and end with Si-2. Are you sure you meant Si-1, or did you mean S1=S?
Dubslow is offline   Reply With Quote
Old 2012-04-10, 05:25   #3
princeps
 
Nov 2011

148 Posts
Default

Quote:
Originally Posted by Dubslow View Post
[Stupid Question]
What if n mod 4 = 1?
[/SQ]
Also, the LL (and LLR) test(s) start with S0 and end with Si-2. Are you sure you meant Si-1, or did you mean S1=S?
\text{ If } n \equiv 1 \pmod 4 ~\text { and }~n\geq1 ~\text { then }~ 5 \mid 2^n+3 , so 5 is only prime number of the form 2^n+3 with property n \equiv 1 \pmod 4

Yes , I mean : S_{i-1} .

Last fiddled with by princeps on 2012-04-10 at 05:26
princeps is offline   Reply With Quote
Old 2012-04-10, 16:25   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default

Quote:
Originally Posted by princeps View Post
Definition : Let  P_n be a number of the form :

P_n=2^n+3

Definition : Let's define starting seed S as :

S = \begin{cases} 3, & \text{if }n \equiv 0 \pmod 4 \\ 8, & \text{if }n \equiv 2 \pmod 4\\ 7, & \text{if }n \equiv 3 \pmod 4 \end{cases}

Definition : Let's define sequence S_i as :

S_i=S^2_{i-1}-2 ~\text { with }~ S_0=S

Conjecture :

P_n ; (n \geq 3) ~\text{ is a prime iff }~ S_{n-1} \equiv S_0 \pmod {P_n}

I have checked conjecture for all primes in this sequence with exponent below 200000 . Also , for n<5000 there is no composite P_n that satisfies relation from conjecture .

Are there similar criteria in the literature for the numbers of this form ?
This has been discussed before in this forum. Note that P_n - 1 = 2^n + 2
= 2*(2^n-1 + 1).

This test is just a disguised prp test working in the field GF((P_n)^2).
The recursion is just a disguised way of performing exponentiation in this
field.

While the conjecture may be correct, (i.e. that the prp test is a true
prime test) I do not know how to prove this. (nor, I suspect, does anyone
else)
R.D. Silverman is offline   Reply With Quote
Old 2012-04-10, 20:08   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This has been discussed before in this forum. Note that P_n - 1 = 2^n + 2
= 2*(2^n-1 + 1).

This test is just a disguised prp test working in the field GF((P_n)^2).
The recursion is just a disguised way of performing exponentiation in this
field.

While the conjecture may be correct, (i.e. that the prp test is a true
prime test) I do not know how to prove this. (nor, I suspect, does anyone
else)
Note also what happens if n == 1 mod 3. Look at the factorization of
P_n -1 ...........
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1 primus Miscellaneous Math 14 2015-07-04 15:42
primality of F33 Mini-Geek Math 8 2009-09-24 21:18
Primality searches and primality successes marco_calabresi Information & Answers 3 2009-04-17 19:44
Primality Unregistered Homework Help 4 2007-07-18 08:36
Reshetnikov Criteria HiddenWarrior Miscellaneous Math 5 2005-05-27 00:20

All times are UTC. The time now is 00:48.

Thu Nov 26 00:48:47 UTC 2020 up 76 days, 21:59, 3 users, load averages: 1.03, 1.09, 1.17

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.