Quote:
Originally Posted by Viliam Furik
Quote:
Originally Posted by a1call
Meant 2^p1
If for any prime p
2*p+1  2^p1
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)