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.