20230130, 14:58  #1 
Jul 2022
2^{2}·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 S_{i}+1=5*(S_{0}1)*...*(S _{i1}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^22)^22)^22)^22)^22)^22)^22)+1 and for some index i for the numbers S_{i}2=3*4*S_{0}^{2}*...*S_{i2}^{2} it has as factors 7,97,12289 As you can see on factordb for the number: (((((((1416317954^22)^22)^22)^22)^22)^22)^22)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 20230130 at 15:06 
20230130, 20:11  #2 
Jul 2022
2^{2}·19 Posts 
I don't know if I explained well in the previous post. But it can be verified that:
S_{1} = 0 (mod 7) S_{2} = 0 (mod 97) S_{8} = 0 (mod 12289) S_{1} = 1 (mod 13) S_{2} = 1 (mod 193) S_{5} = 1 (mod 769) S_{15} = 1 (mod 786433) I wanted to understand if getting S_{i}=0 (mod 3*2^n+1) or S_{i}=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? 
20230131, 17:32  #3 
"Alexander"
Nov 2008
The Alamo City
3^{2}·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 LucasLehmer test.

20230131, 17:38  #4  
Jul 2022
2^{2}·19 Posts 
Quote:


20230201, 01:48  #5 
Feb 2017
Nowhere
14276_{8} 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^{(P1)/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^{(P1)/2} == 1 (mod P) implies a^{(P1)/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 q1. 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^{(P1)/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 20230202 at 15:24 
20230201, 16:26  #6  
"Alexander"
Nov 2008
The Alamo City
3^{2}·107 Posts 
Quote:


20230201, 16:43  #7  
Jul 2022
2^{2}·19 Posts 
Quote:


20230205, 12:14  #8  
Jul 2022
2^{2}×19 Posts 
Quote:
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? 

20230205, 14:59  #9  
Feb 2017
Nowhere
2×3,167 Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A test for primality?  paulunderwood  Miscellaneous Math  8  20220611 11:54 
I found the primality test, there seems to be no composite numbers that pass the test  sweety439  sweety439  7  20200211 19:49 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
understanding the group G in an explanation of the LucasLehmer test  wildrabbitt  Math  1  20150517 12:34 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 