6.10. General Functionality of the Algorithm

6.10.1. Objectives and Goals of Shor’s Algorithm

The primary objective of Shor’s algorithm is to factorize a large composite number into its prime factors. The problem of prime factorization is computationally challenging for classical computers, especially for large numbers, and forms the foundation of modern cryptographic systems such as RSA. Shor’s algorithm provides an exponential speed advantage over classical algorithms by solving this problem on quantum computers in polynomial time.

Main Goals:

• Prime Factorization: Decompose large composite numbers into their prime factors.
• Impact on Cryptography: Threaten the security of asymmetric cryptosystems such as RSA.
• Quantum Computing Potential: Demonstrate the superiority of quantum computers over classical ones for certain problems.

6.10.2. Integration of Classical and Quantum Components

Shor’s algorithm operates by combining both classical and quantum computing components. The integration of these two elements is the key to the algorithm’s effectiveness.

Role of Classical Computers:

• Input Preparation: The initial steps of the algorithm are performed on a classical computer, preparing the problem for processing by the quantum computer.
• Result Analysis: Data obtained from the quantum phase is processed by a classical computer to identify the prime factors.

Role of Quantum Computers:

• Period Finding: The core of Shor’s algorithm involves finding the period of a function using the superposition and entanglement properties of quantum mechanics.
• Quantum Fourier Transform (QFT): A critical component of the algorithm, QFT is used in the period-finding process and is executed on the quantum computer.

6.10.3. Step-by-Step General Process of the Algorithm

Shor’s algorithm follows a systematic process composed of specific steps. Each step contributes to the overall functionality of the algorithm and ensures efficient progression.

Step 1: Problem Definition and Input Preparation

Identify the composite number N to be factorized. Select a number a that is coprime with N (1 < a < N).

Step 2: Period Finding

Use quantum computing to find the period r of the selected number a. The period is the smallest positive integer that satisfies the equation: a^r mod N = 1.

Step 3: Determination of Prime Factors

Once the period r is found, use classical methods to factorize the composite number. If r is even and a^r/2 ≠ -1 mod N, the prime factors can be determined as:

gcd(a^r/2 – 1, N) and gcd(a^r/2 + 1, N)

Here, gcd stands for the greatest common divisor.

Step 4: Verification and Repetition

Verify the obtained prime factors. If the correct factors are not found, repeat the algorithm with a different value of a.

6.10.4. Efficiency and Performance

Shor’s algorithm provides significant efficiency and performance advantages over classical algorithms for certain problems. This advantage arises from the algorithm’s effective utilization of the superposition and entanglement properties of quantum computers.

Execution Time and Complexity:

• Classical Algorithms: The best-known classical factorization algorithms (e.g., the general number field sieve) operate in exponential time.
• Shor’s Algorithm: Operates in polynomial time on a quantum computer.

Quantum Advantage:

• Parallel Processing Capability: The superposition state of qubits allows for multiple computations to be performed simultaneously.
• Quantum Fourier Transform (QFT): QFT provides a fast and efficient transformation during the period-finding process, significantly enhancing the overall performance of the algorithm.