Primality Test Via Quantum Factorization

Abstract

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.

Using REVTEX 3.0, AMS fonts required. Typos corrected. To appear in Int.J.Mod.Phys.C