Primality Test Via Quantum Factorization
H. F. Chau, Hoi‐Kwong Lo · International Journal of Modern Physics C · 1997
We consider a probabilistic quantum implementation of a variation 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.