A quantum algorithm for computing multiplicative order of integers modulo a prime
*Maheswara Rao ValluriCorresponding authormaheswara.valluri@fnu.ac.fjSchool of Mathematical and Computing SciencesDerrick Campus, SuvaFiji National UniversityP. O. Box 7222, FijiView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 05 Jul 2021
- Accepted:
- 05 Jan 2022
- Published Online:
- 30 Mar 2023
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-1557
- Pages:
- 573–584
Abstract
Keywords
Subject Classifications
References
[1] Adleman, L. M. and McCurley, K. S., “Open problems in number theoretic complexity II”, Lect. Notes Comput. Sci. 877, 291-322 (1994).
[2] Crandall, R. and Pomerance, C., “Prime numbers: A computational perspective”, Springer-Verlag, New York (2001).
[3] Shor, P. W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Comput. 26, 1484-1509 (1997).
[4] Burton, D. M, “Elementary Number Theory”, McGraw-Hill Higher Education, 6th Edition, (2005).
[5] Nielsen, M. and Chuang, I., “Quantum Computation and Quantum Information”, Cambridge University Press, New York, (2000).
[6] Vandersypen, L.M.K., Steffen, M. and Breyta, G et al., “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance”, Nature 414(6866), 883-887 (2001).
[7] Coppersmith, D., “An approximate Fourier transform useful in quantum factoring”. Technical Report RC19642, IBM, (1994).
[8] Hales, L.and Hallgren, S., “An improved quantum Fourier transform algorithm and applications” , Proceedings 41st Annual Symposium on Foundations of Computer Science: 515-525 (November 12-14, 2000).
[9] Manin, Yu.I., “Vychislimoe i nevychislimoe (computable and noncomputable)”, Soviet Radio, 13-15 (1980).
[10] Feynman, R., “Simulating physics with computers”, International Journal of Theoretical Physics, 21(6/7), 467-488 (1982).
[11] Feynman, R., “Quantum mechanical computers”, Optics News, 11, 11-20 (1985).
[12] Benioff, P.A., “Quantum mechanical Hamiltonian models of Turing machines”, Journal of Statistical Physics, 29(3), 515-546 (1982).
[13] Deutsch, D., “Quantum theory, the Church-Turing principle, and the universal quantum Turing machine”, In Proceedings of the Royal Society of London, Vol. A400, 97-117 (1985).
[14] Deutsch, D., and Jozsa, R., “Rapid solution of problems by quantum computation”, In Proceedings of the Royal Society of London, Vol. A439, 553-558 (1992).
[15] Simon, D., “On the power of quantum computation”, SIAM Journal on Computing, 26(5), 1474- 1483 (1997).
[16] Bernstein,E. and Vazirani, U., “Quantum complexity theory”, SIAM Journal on Computing, 26(5), 1411-1473 (1997).
[17] Childs, A.M. and Ivanyos, G., “Quantum computation of discrete logarithms in semigroups”, Journal of Mathematical Cryptology, 8(4), 405-416 (2014).
[18] Chau, H.F. and Lo, H.K., “Primality test via quantum factorization” , International Journal of Modern Physics C 08, 131-138 (1997).
[19] Vela, A.D. and Escartin, J.C.G., “A quantum primality test with order finding”, Quantum Information and Computation, 18(13/14), (2018).
[20] Proos, J.and Zalka,C., “Shor’s discrete logarithm quantum algorithm for elliptic curves”, Quantum Information and Computation, 3(4), 317-344 (2003).
[21] Maslov,D., Mathew, J., Cheung, D. and Pradhan,D.K., “An O(m2)-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2m )”, Quantum Information and Computation, 9(7), 610-621 (2009).
