  We consider a probabilistic quantum implementation of a variable of the
Pocklington-Lehmer $N-1$ primality test using Shor's algorithm. O($\log^3 N
\log\log N \log\log\log N$) elementary q-bit operations are required to
determine the primality of a number $N$, making it (asymptotically) the fastest
known primality test. Thus, the potential power of quantum mechanical computers
is once again revealed.
