Quantum Computing, Beyond Qubits – Part 4: Shor’s Algorithm for Factoring Large Numbers

1. Introduction

Shor’s 1994 paper, Algorithms for quantum computation: Discrete logarithms and factoring, presented two groundbreaking quantum algorithms for computing the discrete logarithm and factoring integers, both widely used in cryptography.

Shor’s algorithm is based on the quantum Fourier transform and modular exponentiation, and it finds the period of a periodic function related to the prime factors of an integer. Shor’s algorithm can efficiently determine the integer’s prime factors by finding the period. This algorithm has significant implications for cryptography, as it can break many cryptographic systems that rely on the difficulty of factoring large numbers.

In the world of cryptography, the security of encrypted data is paramount. One of the most widely used cryptographic techniques is public key cryptography, which relies on two assumptions (both valid in classical computing):

1. It is easy to multiply large prime numbers together
2. It is difficult to factorize a large number into its prime factors.

This is the foundation of many widely used cryptographic systems, such as RSA. However, the advent of quantum computing can potentially break many of these cryptographic systems, including RSA. Shor’s quantum algorithm can efficiently factorize large numbers, posing a significant threat to public key cryptography. In this article, we will explore the technical details of Shor’s algorithm and its implications for cryptography.

Shor’s paper presented groundbreaking algorithms that demonstrated the power of quantum computing and opened up new possibilities for solving problems intractable on classical computers.

2. Background

Before diving into the technical details of Shor’s algorithm, we need to understand some basic concepts in quantum computing.

2.1 Quantum Computing

Quantum computing utilizes the principles of quantum mechanics, a branch of physics that studies the behaviour of matter and energy at a small scale. Unlike classical computers, which process information using bits that can be either 0 or 1, quantum computers use quantum bits or qubits, which can be in a state of superposition of 0 and 1 and entangled with other qubits.

The ability of qubits to exist in a superposition of states means that quantum computers can perform many calculations simultaneously, allowing them to solve specific problems much faster than classical computers. This is known as quantum parallelism, and it is one of the key advantages of quantum computing.

Quantum computers leverage the properties of quantum mechanics like superposition and interference to perform parallel computations with efficiencies unattainable on classical computers. Instead of classical bits, quantum computers use quantum bits or qubits.

2.2 Quantum Gates and Circuits

Quantum gates are the basic building blocks of quantum circuits, equivalent to classical circuits in quantum computing. Quantum gates operate on qubits, transforming them from one state to another. Some examples of quantum gates include:

• The Pauli-X gate, which flips the state of a qubit from 0 to 1 or vice versa
• The Hadamard gate, which puts a qubit into a superposition of 0 and 1
• The Controlled-NOT gate, which applies the Pauli-X gate to one qubit if another qubit is in the state 1

By combining different quantum gates into circuits, quantum algorithms can be designed to perform specific calculations.

3. The Problem Shor’s Algorithm Solves

3.1 Integer Factorization

The problem that Shor’s algorithm solves is integer factorization, which can be described as follows: given a large composite number N, the goal is to find its prime factors, p and q, such that N = p * q. This problem is central to many cryptographic systems, including RSA.

The security of RSA relies on the fact that factoring a large composite number into its prime factors is computationally difficult for classical computers. However, Shor’s algorithm can solve this problem much faster than classical algorithms, making it a significant threat to public key cryptography.

3.2 Modular Arithmetic

To understand how Shor’s algorithm works, we first need to introduce the concept of modular arithmetic. Modular arithmetic only considers remainders after division by a fixed integer, called the modulus.

For example, in modulo five arithmetic, we only consider remainders after division by 5. So 7 mod 5 = 2 because seven divided by five leaves a remainder of 2.

3.3 Quantum Fourier Transform

The key to Shor’s algorithm is the quantum Fourier transform (QFT), a quantum version of the classical Fourier transform. The Fourier transform is a mathematical operation that converts a signal from the time domain to the frequency domain, allowing for the analysis of its frequency components.

The QFT is used in Shor’s algorithm to find the period of a function related to the prime factors of the number N. By finding the period of this function, Shor’s algorithm can determine the prime factors of N with high probability.

Let’s see how all this works together, first on a classical version of Shor’s algorithm, which we can implement with Python.

4. A Classical Version of Shor’s Algorithm

4.1 Overview

Shor’s algorithm is a quantum algorithm that requires a quantum computer to perform the modular exponentiation and quantum Fourier transform steps efficiently. While it is possible to simulate Shor’s algorithm on a classical computer, the simulation time grows exponentially with the size of the input number, making it impractical for large numbers.

That said, we can implement Shor’s algorithm in Python that simulates the quantum operations using classical computation. This implementation is suitable for educational purposes and small input numbers and cannot be used for the practical factorization of large numbers.

4.2 Python Implementation — Trial 1

We will start with a simple implementation as follows. Given a composite number N = f1 x f2, where f1 and f2 are two unknown prime numbers, the following steps will help us determine their values.

1. Select a random number g smaller than N
2. If g is not a factor of N
   • Start with p = 2
   • Calculate g₁ = g^p + 1 and g₂ = g^p – 1
   • If neither g₁ nor g₂ is a factor of N, set p = p +1, and try again.

The above algorithm works because of a theorem from number theory that states that for any two integers A and B, the following holds:

In plain English, this theorem says that for any two integers A and B, we can find an integer power p such A to the power p is equal to some multiple of B plus one.

We can rewrite the above equation as follows:

Or, even better still, in the form of two “factors” of some multiple of B:

By iterating through all the values of p between 2 and 10, the following implementation of the above algorithm can determine the factors of N = 43 * 47.

import random
import math

# --------------------------------------------------------------------
# This method finds the GCD (Greatest Common Divisor) of two numbers
# --------------------------------------------------------------------
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# ---------------------------------------------------------------------------------
#
# This method factorizes a large composite number N using an equivalent of Shor's 
# algorithm for classical computers
#
# ---------------------------------------------------------------------------------
def shor_integer_factorisation(N):
 
    # Step 1: Choose a random number g
    g = random.randint(1, N-1)

    # Step 2: Compute the greatest common divisor of g and N
    d = gcd(g, N)
    if d > 1:
        # We have found a non-trivial factor of N
        return d
    
    # Step 3: Knowing that g^p = (aN + 1) Iterate thru the guesses
    p = 2
    while p < 20:
        print('Trying with p = ' + str(p) + '...')

        gp = pow(g, p)
        g1 = gp + 1
        g2 = gp - 1
        print(' ... and g1 = ' + str(g1) + ' and g2 = ' + str(g2))

        # Check if any of the factors new guesses is a factor
        d = gcd(g1, N)
        if d > 1:
            # We have found a non-trivial factor of N
            return d
        
        d = gcd(g2, N)
        if d > 1:
            # We have found a non-trivial factor of N
            return d
        
        # look for another power
        p = p + 1

# TEST method
N = 43 * 47
d = shor_integer_factorisation(N)

if d > 1:
    print ('f1 = ' + str(d))
    print ('f2 = ' + str(N/d))

N was chosen as a composite of two primes, 43 and 47, which we generated using the Sieve of Eratosthenes method. These numbers are small and larger primes will produce an overflow, and the program will abort, but they will do nicely to illustrate how the algorithm works.

4.3 Python Implementation — Trial 2

The algorithm above is notoriously slow and expensive (in terms of memory usage) for factors even moderately larger than those used in the example above. We need a better way of finding the power p, other than brute force. It turns out that a mathematical property of the theorem used above would be very helpful. Let’s see what that is.

Given the below equation for any two integers A and B:

If we choose another power x, we can rewrite the above as:

It turns out that multiplying both equations will produce a formula structurally similar to the second, regardless of the power x.

Rearranging the terms on both sides, we obtain the following:

Or:

Based on the above, we can modify our original algorithm to use a smarter approach for finding p. This improvement will leverage the fact that by varying x and observing c, we obtain a sequence with period p, our desired power. The modified version of the classical part of Shor’s algorithm will now consist of the following:

1. Choose a random number a < N
2. Compute the greatest common divisor of a and N.
   • If the gcd(a, N) is not equal to 1, then we have found a factor of N. Otherwise, proceed to the next step.
3. Use a period-finding algorithm to find the period r of the function f(x) = a^x mod N.
4. If r is odd or a^(r/2) mod N = -1, go back to step 1. Otherwise, the factors of N can be obtained using gcd(a^(r/2) ± 1, N).

Here’s an implementation of the classical part of Shor’s algorithm in Python:

from math import gcd

#---------------------------------------------------------------
# A classical version of Shor's algorithm
#---------------------------------------------------------------
def shors_classical(N):
    # Choose a random number less than N
    a = 2 

    # Is our first guess a factor of N?
    g = gcd(a, N)
    if g > 1:
        return g
    
    for i in range(1, N):
        r = find_period(a, N)

        if r % 2 == 0:
            x = a**(r//2) % N
            
            if x != 1 and x != N-1:
                p = gcd(x+1, N)
                q = gcd(x-1, N)
                
                if p*q == N:
                    return p, q
                
        a = (a+1) % N
    
    return -1, -1
    
#---------------------------------------------------------------
# A period-finding algorithm
#---------------------------------------------------------------
def find_period(a, N):
    i = 1
    while True:
        if a**i % N == 1:
            return i
        i += 1

# TEST method
N = 739 * 743
[f1, f2] = shors_classical(N)

if f1 > 1 or f2 > 1:
    print ('f1 = ' + str(f1))
    print ('f2 = ' + str(f2))

The algorithm, still slow, will at least produce a result and is, therefore, superior to the first.

5. Shor’s Quantum Algorithm

The basic steps of the algorithm will be described next. We will also touch upon the mathematical (mostly from number theory) theorems under the hood.

Step 1: Choose a random number

The first step of Shor’s algorithm is to choose a random number between 1 and N-1 (let’s call it a), where N is the number we want to factorize. This number will most likely be coprime of N, meaning it does not share any factors except 1. Otherwise, we could divide N by a to obtain the other factor.

Step 2: Evaluate a^p mod N

The next step is to evaluate the function f(p) = a^p mod N for a range of values of p.

This is done using a quantum circuit that applies modular exponentiation to the state |p⟩|0⟩, where |p⟩ represents the state of a quantum register containing p and |0⟩ represents the state of another quantum register initialized to 0.

Step 2 of Shor’s algorithm involves the construction of a quantum circuit to perform the modular exponentiation of a randomly chosen base raised to a power that is a multiple of the period r.

The quantum circuit for modular exponentiation in Step 2 can be constructed using a series of controlled-U operations, where U|x⟩ = |a^p mod N⟩ represents the modular multiplication by a, where a is the chosen base, and N is the number to be factored. The controlled-U operation acts on an auxiliary register that is initially in the state |0⟩ and is controlled by the qubits of the input register that encode the exponent.

The circuit for modular exponentiation in Step 2 can be represented graphically as a sequence of gates, where each gate represents a single-qubit or two-qubit operation. The gates used in the circuit depend on the specific implementation of the controlled-U operation, which can be achieved using various techniques, such as the phase estimation algorithm or the quantum Fourier transform.

The circuit for modular exponentiation in Step 2 typically consists of three main components:

1. Initialization: The input register is initialized to the state |1⟩, and the auxiliary register is initialized to the state |0⟩.
2. Modular multiplication: The controlled-U operation is applied to the auxiliary register, controlled by the qubits of the input register that encode the exponent. This operation performs the modular multiplication by a, raising the state |1⟩ to the power of a^p mod N, and storing the result in the auxiliary register.
3. Measurement: The input register is measured in the computational basis to obtain the exponent p, which is then used in Step 3 to estimate the period r using the quantum Fourier transform.

The specific implementation of the circuit for modular exponentiation in Step 2 depends on the choice of the base a and the number to be factored N, as well as the specific implementation of the controlled-U operation. However, the basic structure of the circuit remains the same, consisting of a sequence of gates that perform modular multiplication controlled by the exponent qubits, followed by a measurement in the computational basis.

Step 3: Find the period using the QFT

The third step is to apply the quantum Fourier transform to the output of the previous step. This gives us a set of peaks in the frequency domain, with the period r of the function f(x) corresponding to the distance between the peaks.

Step 4: Calculate the factors

The final step is to use the period r to calculate the factors of N. If r is even or a^r/2 mod N = -1, we can choose a different random number and start over. Otherwise, the factors of N are given by gcd(a^r/2+1, N) and gcd(a^r/2-1, N).

6. How Does Shor’s Algorithm Take Advantage of Quantum Computation?

Shor’s algorithm takes advantage of two key properties of quantum computation: superposition and interference.

Shor’s algorithm uses quantum computation’s inherent parallelism and interference effects to factorise large integers exponentially faster than classical algorithms. The algorithm’s efficient use of superposition and interference properties makes it a powerful tool for solving a specific class of problems intractable for classical computers.

7. Implications for Cryptography

The implications of Shor’s algorithm for cryptography are significant. Since Shor’s algorithm can factorize large numbers much faster than classical algorithms, it can break many cryptographic systems that rely on the difficulty of factoring large numbers.

RSA, widely used for secure communication and digital signatures, is particularly vulnerable to Shor’s algorithm. As a result, there is a growing interest in developing quantum-resistant cryptographic systems that can withstand attacks from quantum computers.

8. Conclusion

Shor’s powerful quantum algorithm can efficiently factorize large numbers, posing a significant threat to public key cryptography. By using the quantum Fourier transform to find the period of a function related to the prime factors of a number, Shor’s algorithm can determine the prime factors with high probability. The implications of Shor’s algorithm for cryptography are significant, and there is a need for quantum-resistant cryptographic systems to be developed.

In conclusion, Shor’s algorithm is a remarkable quantum computing feat with significant implications for cryptography. By using the quantum Fourier transform to find a function’s period related to a number’s prime factors, Shor’s algorithm can factorize large numbers much faster than classical algorithms. This poses a significant threat to public key cryptography, and there is a growing interest in developing quantum-resistant cryptographic systems. While quantum computing is still in its infancy, it is clear that it has the potential to revolutionize many fields, including cryptography and computational complexity theory.

9. References

• Nielsen, M. A., & Chuang, I. L. (2010). Quantum computation and quantum information. Cambridge University Press.
• Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM journal on computing, 26(5), 1484-1509.
• Ekert, A. K., & Jozsa, R. (1996). Quantum algorithms: Entanglement-enhanced information processing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 354(1694), 1891-1908.
• Preskill, J. (2018). Quantum Computing in the NISQ era and beyond. Quantum, 2, 79.
• Boneh, D., & Zhandry, M. (2018). Quantum-resistant public-key cryptography. Advances in Cryptology–CRYPTO 2018, 277-306.