mersenneforum.org Looking for an explanation of the primality test
 Register FAQ Search Today's Posts Mark Forums Read

 2023-01-30, 14:58 #1 User140242   Jul 2022 22·19 Posts Looking for an explanation of the primality test I'm looking for an explanation of the primality test for numbers of type 3*2^n+1 From an analysis of the sequence in the Lucas Lehmer test I noticed that for some index i Si+1=5*(S0-1)*...*(S i-1-1) has as factors the numbers of type 3*2^n+1 : 13, 193 and 769 As you can see on factordb for the number: (((((((1416317954^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)+1 and for some index i for the numbers Si-2=3*4*S02*...*Si-22 it has as factors 7,97,12289 As you can see on factordb for the number: (((((((1416317954^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)^2-2)-2 I failed to test for successive primes of the form 3*2^n+1 but I know it's possible to do a test similar to the Lucas Lehmer test for numbers 3*2^n+1 but I can't find an explanation or an example of the algorithm. Can anyone point me to some links? Thank you. Last fiddled with by User140242 on 2023-01-30 at 15:06
 2023-01-30, 20:11 #2 User140242   Jul 2022 22·19 Posts I don't know if I explained well in the previous post. But it can be verified that: S1 = 0 (mod 7) S2 = 0 (mod 97) S8 = 0 (mod 12289) S1 = 1 (mod 13) S2 = 1 (mod 193) S5 = 1 (mod 769) S15 = 1 (mod 786433) I wanted to understand if getting Si=0 (mod 3*2^n+1) or Si=1 (mod 3*2^n+1) for some value of i can be used as a test of primality. I couldn't find the algorithm used to test the primality of numbers 3*2^n+1, can anyone give me some pointers?
 2023-01-31, 17:32 #3 Happy5214     "Alexander" Nov 2008 The Alamo City 32·107 Posts Numbers of the form k*2^n+1 are generally tested using Proth's theorem, which is more like Fermat's little theorem and the associated Fermat probable prime (PRP) test than the Lucas-Lehmer test.
2023-01-31, 17:38   #4
User140242

Jul 2022

22·19 Posts

Quote:
 Originally Posted by Happy5214 Numbers of the form k*2^n+1 are generally tested using Proth's theorem, which is more like Fermat's little theorem and the associated Fermat probable prime (PRP) test than the Lucas-Lehmer test.
Here I read about the existence of the Brillhart-Lehmer-Selfridge test and from the name I thought it was similar to the Lucas-Lehmer test, but I couldn't find any other information.

 2023-02-01, 01:48 #5 Dr Sardonicus     Feb 2017 Nowhere 142768 Posts If my understanding is correct, a Proth number is of the form k*2^n + 1, where k is odd and 0 < k < 2^n. Proth's Theorem says that if P is a Proth number, and a(P-1)/2 == -1 (mod P) then P is prime. It appears to be very simple to prove. If q is a prime factor of P, a(P-1)/2 == -1 (mod P) implies a(P-1)/2 == -1 (mod q). It follows (since k is odd) that 2^n divides the multiplicative order of a (mod q), so that 2^n divides q-1. Thus, q ≥ 2^n + 1, which (since k < 2^n) implies q^2 > P. If P were composite, the least prime factor q of P would violate this inequality. Therefore, P is prime. (I hope my mind hasn't slipped a cog here...) I would assume P is first shown not to have any small factors before trying to prove it prime. Assuming P > 13, we have n > 2, so that P == 1 (mod 8). In order to find a candidate a, we can then test kronecker(P, a) for small odd prime values of a until we find one with kronecker(P, a) = -1. I am not sure how many values would need to be tested, but my guess is, "not many." For k = 3, assuming P > 13 we can skip a = 3. If you compute a^k (mod P) first, the rest of a(P-1)/2 (mod P) is done by repeated squaring (mod P). EDIT: Feeding 2, 5, 6, 8, 12, 18, 30 to OEIS gave one matching sequence - the sequence of n for which 3*2^n + 1 is prime. There were 43 known values of n listed, the largest being 2145353. I determined the least values of a as above for each value of P = 3*2^n + 1. The result was a = 5 for 31 values of n; a = 7 for 2 values of n, and a = 11 for 10 values of n. Last fiddled with by Dr Sardonicus on 2023-02-02 at 15:24
2023-02-01, 16:26   #6
Happy5214

"Alexander"
Nov 2008
The Alamo City

32·107 Posts

Quote:
 Originally Posted by User140242 Here I read about the existence of the Brillhart-Lehmer-Selfridge test and from the name I thought it was similar to the Lucas-Lehmer test, but I couldn't find any other information.
The Brillhart-Lehmer-Selfridge test is a generalization of the Pocklington test, and both are described at https://en.wikipedia.org/wiki/Pockli...primality_test. Neither is similar to the Lucas-Lehmer-Riesel test, other than being attributed in part to D. H. Lehmer.

2023-02-01, 16:43   #7
User140242

Jul 2022

22·19 Posts

Quote:
 Originally Posted by Happy5214 The Brillhart-Lehmer-Selfridge test is a generalization of the Pocklington test, and both are described at https://en.wikipedia.org/wiki/Pockli...primality_test. Neither is similar to the Lucas-Lehmer-Riesel test, other than being attributed in part to D. H. Lehmer.
Thank you. At this point I think the result obtained in post #2 is just a coincidence, in fact I could not find any connection between i and n. One should look for a counter example but I think it's a waste of time.

2023-02-05, 12:14   #8
User140242

Jul 2022

22×19 Posts

Quote:
 Originally Posted by Dr Sardonicus ... EDIT: Feeding 2, 5, 6, 8, 12, 18, 30 to OEIS gave one matching sequence - the sequence of n for which 3*2^n + 1 is prime. There were 43 known values of n listed, the largest being 2145353. I determined the least values of a as above for each value of P = 3*2^n + 1. The result was a = 5 for 31 values of n; a = 7 for 2 values of n, and a = 11 for 10 values of n.

Here I found a list with 48 possible values ​​of n.

Out of curiosity, could you list the values ​​of n for which a=7 and a=11?

2023-02-05, 14:59   #9
Dr Sardonicus

Feb 2017
Nowhere

2×3,167 Posts

Quote:
 Originally Posted by User140242 Here I found a list with 48 possible values ​​of n. Out of curiosity, could you list the values ​​of n for which a=7 and a=11?
The OEIS page for A002253 has a link to a table of the first 50 values of k for which 3*2^k + 1 is prime (which however includes the exponent 1, for which 3 > 2^1).

The largest exponent in that table is k = 16408818. Up to that limit, we have a = 5, except for

a = 7: k = 8, 2816

a = 11: k = 12, 36, 276, 408, 2208, 3168, 3912, 54792, 709968, 1832496

It is not hard to show that, e.g. 3*2^k + 1 == 4 (mod 5) and to 6 (mod 7) when k == 8 (mod 12); and that 3*2^k + 1 == 4 (mod 5) and also to 4 (mod 7) when k is divisible by 12.

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 8 2022-06-11 11:54 sweety439 sweety439 7 2020-02-11 19:49 Trilo Miscellaneous Math 25 2018-03-11 23:20 wildrabbitt Math 1 2015-05-17 12:34 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 21:28.

Tue Mar 28 21:28:29 UTC 2023 up 222 days, 18:57, 1 user, load averages: 0.73, 0.90, 0.95