confirm primality, provided that p is a Proth number. Verifying that p is a Proth number is a triviality.

This is a practical test because, if p is prime, then any chosen a has about a 50 percent chance of working, and if p is not prime, then no chosen a will work. Furthermore, since the calculation is modulo p, only values of a smaller than p have to be considered.

Systematic naïve variant

If p is Proth composite, then no base a will work to bear witness of primality. If any one base a bears witness, then primality

1.Previous
3.Next