A quantum primality test with order finding
A quantum primality test with order finding
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 …