Looking for an explanation of the primality test

[User140242]

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₀-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 S_i-2=3*4*S₀²*...*S_i-2² 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.

[User140242]

I don't know if I explained well in the previous post. But it can be verified that:

S₁ = 0 (mod 7)
S₂ = 0 (mod 97)
S₈ = 0 (mod 12289)


S₁ = 1 (mod 13)
S₂ = 1 (mod 193)
S₅ = 1 (mod 769)
S₁₅ = 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?

[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.

[User140242]

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.

[Dr Sardonicus]

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.

[Happy5214]

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.

[User140242]

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.

[User140242]

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?

[Dr Sardonicus]

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.