Prime numbers, Shor and the security of our communications

In the context of quantum computing and its potential impact, the security of communications is a key concern. However, how might this new method of computing impact the security of our communications? The answer lies in the use of prime numbers. Prime numbers are essential in cryptography due to their unique properties, particularly their difficulty to factorize when they are large. This characteristic is fundamental to the security of RSA encryption, where two large primes are multiplied to form a public key, while the private key relies on the challenge of factorizing that product. Once a number reaches a certain size, there is currently no known efficient non-quantum prime factorization algorithm. The fundamental principle underlying both classical and quantum algorithms is order finding. The order of an integer a modulo n is defined as the smallest positive integer r such that a^r ≡ 1(mod n). By efficiently determining the order, it becomes possible to discover the factors of n.

What competitive advantage does quantum computing offer in the search for the order? This is where Shor’s algorithm comes into play [1]. Shor employs the phase estimation algorithm [2] in conjunction with a modular exponentiation operator Ua,n |z⟩|1⟩ = |z⟩|a^z (mod n)⟩. It should be noted that when the phase estimation algorithm is employed, the initial step is to apply a Hadamard gate over the z register. This approach allows the algorithm to be conceptualised as a process of raising the base to a superposition of exponents. Once the exponentiation has been completed, the subsequent stage in the phase estimation process is a quantum Fourier transform (QFT) [3]. The application of this transform enables the recovery of periodicity over the z register, thereby facilitating the recovery of r through the assumption of certain classical postprocessing techniques based on the continued fraction algorithm. This concept provides an illustration of how work in superposition enables quantum computers to operate at a significantly faster pace than their classical counterparts, raising potential concerns about the security of our communication systems.

[1] P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, November 1994.

[2] A. Yu Kitaev. Quantum measurements and the Abelian Stabilizer Problem, November 1995. arXiv:quant-ph/9511026.

[3] D. Coppersmith. An approximate Fourier transform useful in quantum factoring, January 2002. arXiv:quant-ph/0201067.