A quantum primality test with order finding
| Autor: | Donis-Vela, Alvaro, Garcia-Escartin, Juan Carlos |
|---|---|
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | Quantum Information & Computation, Vol.17 No.13&14, pp. 1143-1151, November 1, 2017 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.26421/QIC17.13-14 |
| Popis: | 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. Comment: 5 pages. Comments welcome |
| Databáze: | arXiv |
| Externí odkaz: |
|