View Single Post
Old 2020-10-23, 11:56   #25
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

104316 Posts

Originally Posted by Viliam Furik View Post
Originally Posted by a1call View Post
Meant 2^p-1
If for any prime p
2*p+1 | 2^p-1
Then 2*p+1 is definitely prime.
The test is deterministic and computationally about as expensive as a PRP test.
This works with only k=1, thus if it divides 2p-1, it is definitely a prime factor.
Actually, it's true for more than just k = 1.

Let p > 2 be prime. The smallest conceivable composite factor of 2p - 1 is (2p+1)2.

So if q = 2*k*p + 1 divides 2p - 1, and k < 2*p + 2, then q is prime.

Alas, it is more than likely that if k < 2*p + 2 and q = 2*k*p + 1 is prime, that q does not divide 2p - 1.

Especially if q is congruent to 3 or 5 (mod 8)
Dr Sardonicus is offline