PRIMALITY TEST VIA QUANTUM FACTORIZATION

Authors
CHAU HF LO HK
Citation
Hf. Chau et Hk. Lo, PRIMALITY TEST VIA QUANTUM FACTORIZATION, International journal of modern physics C, 8(2), 1997, pp. 131-138
Citations number
29
Categorie Soggetti
Mathematical Method, Physical Science","Physycs, Mathematical","Computer Science Interdisciplinary Applications
Journal title
International journal of modern physics C → ACNP
ISSN journal
01291831
Volume
8
Issue
2
Year of publication
1997
Pages
131 - 138
Database
ISI
SICI code
0129-1831(1997)8:2<131:PTVQF>2.0.ZU;2-B
Abstract
We consider a probabilistic quantum implementation of a variation of t he Pocklington-Lehmer N - 1 primality test using Shor's algorithm. O(l og(3) N log log N log log log N) elementary q-bit operations are requi red to determine the primality of a number N, making it (asymptoticall y) the fastest known primality test. Thus, the potential power of quan tum mechanical computers is once again revealed.