Fundamental Structure of Shor's Quantum Algorithm for Factoring Integers

Abstract

One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we  mention about the fundamentals of  Shor's quantum algorithm illustrating a concrete example.

Keywords

• Factorization,Measurement,Superposition Principle,Qubit

References

1. Bach, E., {\em Toward a theory of Pollard's rho method}, Information and Computation, \textbf{90}(1991), 139--155.
2. Dash, A., Sarmah, D., Behera, B.K., Panigrahi, P.K., \textit{Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer}, 2018.
3. Dattani, N.S., Bryans, N., {\em Quantum factorization of 56153 with only 4 qubits}. arXiv:1411.6758 [quant-ph], 2014.
4. Diffie, W., Hellman, M., {\em New Directions in Cryptography}, IEEE Transactions on Information Theory, \textbf{22(6)}(1976), 644--654.
5. Gerver, J., {\em Factoring large numbers with a quadratic sieve}, Mathematics of Computation, \textbf{41}(1983), 287--294.
6. Jiang, S., Britt, K.A., McCaskey, A.J., Humble, T.S., Kais, S, {\em Quantum annealing for prime factorization}, Scientific Reports, \textbf{8}(2018).
7. Kute S., Desai C.G., \textit{Quantum Cryptography: A Review}, Indian Jour. of Scien. and Techn., \textbf{10(3)}(2017).
8. Li, Z., Dattani, N.S., Chen, X., Liu, X., Wang, H., Tanburn, R., Chen, H., Peng, X., Du, J., {\em High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311}, (2017).

9. Martin-Lopez, E., Laing, A., Lawson, T., Alvarez, R., Zhou, X., O'Brien, J.L., {\em Experimental realization of Shor's quantum factoring algorithm using qubit recycling}, Nature Photonics, 6 \textbf{11}(2012), 773--776.
10. Pal, S., Moitra, S., Anjusha, V.S., Kumar, A., Mahesh, T.S., {\em Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor}, (2016).
11. Pollard, J.M., {\em Theorems on factorization and primality testing}, Proceedings of the Cambridge Philosophical Society, \textbf{76}(1974), 521--528.
12. Pomerance, C., \textit{A tale of two sieves}, The Notices of the Amer. Math. Soc., \textbf{43}(1996), 1473--1485.
13. Rabin, M., \textit{Digitalized signatures and public-key functions as intractable as factorization}, MIT Laboratory for Computer Science, January 1979.
14. Rivest, R., Shamir, A., Adleman, L., {\em A method for obtaining digital signatures and public-key cryptosystems}, Communications of the ACM 21, \textbf{2}(1978), 120--126.
15. Shor, P.W., {\em Algorithms for quantum computation: discrete logarithms and factoring}, Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc., 1994.
16. Silverman, R.D., Wagstaff JR., S.S., {\em A practical analysis of the elliptic curve factoring algorithm}, Mathematics of Computation, \textbf{61}(1993), 445--462.
17. Strubell, E., An Introduction to Quantum Algorithms, COS498, Chawathe, 2011.
18. Valle, C., Shor's Algorithm and Grover's Algorithm in Quantum Computing, Master's thesis, University of Kansas, 2011.
19. Vandersypen, L.M., Steffen, M., Breyta, G., Yannoni, C.S., Sherwood, M.H. , Chuang, I.L., {\em Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance}, Nature, \textbf{414}(2001), 883--887.
20. Xu, N., Zhu, J., Lu, D., Zhou, X., Peng, X., Du, J., {\em Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system}, Physical Review Letters, 108 \textbf{13}(2012).