Quote:
Originally Posted by Viliam Furik
Quote:
Originally Posted by a1call
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 2 p-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 2
p - 1 is (2p+1)
2.
So if q = 2*k*p + 1 divides 2
p - 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 2
p - 1.
Especially if q is congruent to 3 or 5 (mod 8)
