6.11. Mathematical Foundations

This section is likely to be the longest and most significant part of the study. Shor’s algorithm utilizes advanced mathematical concepts to solve the problem of integer factorization. In this section, the mathematical principles underlying the algorithm will be examined in detail. The following subtopics will be addressed:

• Integer Factorization Problem
• Modular Arithmetic
• Euler’s Function and Euler’s Theorem
• Period Finding Problem
• Exploration of Mathematical Concepts Through Examples

6.11.1. Integer Factorization Problem

Integer factorization is the process of expressing a composite number (i.e., a number that has divisors other than 1 and itself) as a product of prime numbers. For example, the factorization of 15 into its prime factors is:

15 = 3 × 5

Here, 3 and 5 are prime numbers.

Significance:

• The factorization of large composite numbers forms the foundation of security in cryptography, particularly in systems such as the RSA algorithm. For classical computers, this process can be extremely time-consuming for large numbers, whereas Shor’s algorithm can perform this task on quantum computers in polynomial time.

6.11.2. Modular Arithmetic

Modular arithmetic, similar to the concept used in daily life for clock calculations, is a branch of mathematics that studies numbers under a certain modulus (division). It is one of the fundamental components of Shor’s algorithm.

Definition:

Modular arithmetic examines the remainder of a number when divided by another number. Mathematically, the expression a ≡ b mod m indicates that a and b have the same remainder when divided by m. For example:

7 ≡ 3 mod 4 because 7 ÷ 4 = 1 with a remainder of 3.

Role in Shor’s Algorithm:

In Shor’s algorithm, modular arithmetic plays a critical role in the period-finding step. The efficient computation of modular exponentiation for large numbers ensures the algorithm’s performance.