1.Previous
3.Next

a of proving primality, we may make the process slightly more efficient by checking about one-half of all possible a-values smaller than p - we expect half of said values to satisfy the congruence. Once more than p/2 distinct values of a have been tested, compositeness is deterministic. This is because, if p is prime then we expect half of all bases to bears witness; by the pigeonhole principle, once more than half have been checked, we can deduce that none will bear witness, and if no base value

1.Previous
3.Next