Primality Test Via Quantum Factorization

H. F. Chau () and H.-K. Lo ()
Additional contact information
H. F. Chau: School of Natural Sciences, Institute for Advanced Study, Olden Lane, Princeton, NJ 08540, USA
H.-K. Lo: School of Natural Sciences, Institute for Advanced Study, Olden Lane, Princeton, NJ 08540, USA

International Journal of Modern Physics C (IJMPC), 1997, vol. 08, issue 02, 131-138

Abstract: We consider a probabilistic quantum implementation of a variation of the Pocklington–LehmerN - 1primality test using Shor's algorithm.O (log3NloglogNlogloglogN)elementaryq-bit operations are required to determine the primality of a numberN, making it (asymptotically) the fastest known primality test. Thus, the potential power of quantum mechanical computers is once again revealed.

Keywords: Computational Complexity; Pocklington–LehmerN - 1Primality Test; Quantum Computation; Quantum Factorization; Shor's Algorithm (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183197000138
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:08:y:1997:i:02:n:s0129183197000138

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183197000138

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().