  Determining whether a given integer is prime or composite is a basic task in
number theory. We present a primality test based on quantum order finding and
the converse of Fermat's theorem. For an integer $N$, the test tries to find an
element of the multiplicative group of integers modulo $N$ with order $N-1$. If
one is found, the number is known to be prime. During the test, we can also
show most of the times $N$ is composite with certainty (and a witness) or,
after $\log\log N$ unsuccessful attempts to find an element of order $N-1$,
declare it composite with high probability. The algorithm requires $O((\log
n)^2 n^3)$ operations for a number $N$ with $n$ bits, which can be reduced to
$O(\log\log n (\log n)^3 n^2)$ operations in the asymptotic limit if we use
fast multiplication.
