Factoring to Period-Finding Reduction

Hello! Welcome to the next lesson in our series on foundational quantum algorithms.

In the previous lesson, we delved into the Quantum Phase Estimation (QPE) algorithm. We saw how it brilliantly uses the Inverse Quantum Fourier Transform to estimate the phase $ϕ$ of an eigenvalue $e^{2 πi ϕ}$ of a unitary operator. We concluded by noting that QPE's most famous application is Shor's algorithm, and that the first step is to connect the problem of factoring to a problem that QPE can solve.

Today, we will build that connection. Our goal is to derive the reduction of integer factoring to period-finding by proving that the order of a mod N yields a factor of N with high probability. This is the crucial, purely classical, number-theoretic foundation upon which Shor's quantum algorithm is built. We will see that the classically hard problem of factoring an integer N can be transformed into another classically hard problem: finding the period (or order) of a specific function. This reduction perfectly motivates the need for a quantum subroutine to solve the period-finding part efficiently.

1. The Overall Strategy

The core idea of Shor's algorithm is to transform the factoring problem into a period-finding problem. Let's first get a high-level overview of the classical steps involved in this reduction.

The following video provides a clear, step-by-step walkthrough of the classical protocol. It outlines how choosing a random number, finding its order, and checking a few simple conditions can lead to the factors of N.

Shor's Factoring Algorithm, Reducing Prime Factorization to an Order-Finding Problem

This video from the Elucyda channel explains the classical part of Shor's algorithm. It breaks down the process into manageable steps and provides the mathematical reasoning for why the method works.

Please watch the following segments: Step 1 (04:28 - 07:19): Understand the initial step of picking a random integer a and the 'lucky' case where the GCD check immediately yields a factor. Step 2 (07:19 - 09:11): Focus on the definition of the order-finding problem, which is the heart of the algorithm. Step 3 (09:11 - 12:22): Pay close attention to the two crucial conditions the order r must satisfy (r is even, and a^(r/2) ≠ -1 mod N). Derivation (19:26 - 25:05): This part explains why these conditions allow us to find the factors, using the difference of squares factorization.

To summarize the strategy from the video:

Given a composite number $N$ to factor, pick a random integer $a$ such that $1 < a < N$ .
Compute $d = gcd (a, N)$ . If $d > 1$ , you have found a non-trivial factor of $N$ , and you are done.
If $d = 1$ (i.e., $a$ and $N$ are coprime), find the order $r$ of $a$ modulo $N$ . The order is the smallest positive integer such that $a^{r} \equiv 1 (mod N)$ . This is the computationally hard step that will later be handled by a quantum computer.
If $r$ is odd, or if $a^{r /2} \equiv - 1 (mod N)$ , the method fails for this choice of $a$ . Go back to step 1 and pick a new $a$ .
If $r$ is even and $a^{r /2} \neq \equiv - 1 (mod N)$ , then you can find the factors of $N$ by computing $gcd (a^{r /2} - 1, N)$ and $gcd (a^{r /2} + 1, N)$ . At least one of these will be a non-trivial factor of $N$ .

Now, let's formalize this and prove why it works with high probability.

2. The Key Insight: Non-Trivial Square Roots of Unity

The entire reduction hinges on a clever piece of number theory. If we can find a number $x$ that is a "non-trivial" square root of 1 modulo $N$ , we can efficiently factor $N$ .

A non-trivial square root of 1 modulo N is an integer $x$ such that:

$x^{2} \equiv 1 (mod N)$
$x \neq \equiv 1 (mod N)$ and $x \neq \equiv - 1 (mod N)$

The following lemma establishes the connection between such an $x$ and the factors of $N$ .

Shor’s Factoring Algorithm Lecture 9

This excerpt from lecture notes by Prof. Umesh Vazirani at UC Berkeley provides a concise and formal proof of how a non-trivial square root of 1 modulo N can be used to find a factor of N.

Please read 'Lemma 9.1' and its short proof on page 2. It's a very direct argument that you should be able to follow easily.

Let's walk through the proof from the notes.
The condition $x^{2} \equiv 1 (mod N)$ means that $x^{2} - 1$ is a multiple of $N$ . We can write this as:

x^{2} - 1 = k N for some integer k

Factoring the left side gives us the difference of squares:

(x - 1) (x + 1) = k N

This equation tells us that $N$ divides the product $(x - 1) (x + 1)$ .

Now, we use the "non-trivial" conditions:

Since $x \neq \equiv 1 (mod N)$ , $x - 1$ is not a multiple of $N$ .
Since $x \neq \equiv - 1 (mod N)$ , $x + 1$ is not a multiple of $N$ .

Since $N$ divides the product $(x - 1) (x + 1)$ but does not divide either term individually, $N$ must share a non-trivial factor with both $x - 1$ and $x + 1$ . We can find these factors efficiently using the Euclidean algorithm:

factor_1 = gcd(x - 1, N)
factor_2 = gcd(x + 1, N)

At least one of these factors will be a non-trivial factor of $N$ .

3. Finding the Non-Trivial Root via Order-Finding

The question now is: how do we find such a non-trivial root $x$ ? This is where the order-finding procedure comes in.

If we pick a random $a$ coprime to $N$ and find its order $r$ , we have $a^{r} \equiv 1 (mod N)$ . If $r$ happens to be even, we can define $x = a^{r /2}$ . This $x$ is a natural candidate for a square root of 1, since:

x^{2} = (a^{r /2})^{2} = a^{r} \equiv 1 (mod N)

Now we must check if it's non-trivial:

Is $x \equiv 1 (mod N)$ ? No, because if $a^{r /2} \equiv 1 (mod N)$ , then the order of $a$ would be $r /2$ or smaller, which contradicts the definition of $r$ as the smallest such positive integer.
Is $x \equiv - 1 (mod N)$ ? This is possible, and it represents a failure case for our method.

So, the reduction is successful if, for a randomly chosen $a$ , its order $r$ is even and $a^{r /2} \neq \equiv - 1 (mod N)$ . The final step is to prove that this happens with a reasonably high probability.

4. The High-Probability Guarantee

We now arrive at the core of today's learning outcome: proving that the conditions for success are met with high probability. We will assume $N = pq$ is the product of two distinct odd primes, which is the most relevant case for cryptography.

The proof relies on the Chinese Remainder Theorem (CRT). The CRT implies that choosing an integer $a$ modulo $N = pq$ is equivalent to independently choosing an integer $a_{p} \equiv a (mod p)$ and an integer $a_{q} \equiv a (mod q)$ . The order of $a$ modulo $N$ , which we call $r$ , is then related to the orders of $a_{p}$ modulo $p$ ( $r_{p}$ ) and $a_{q}$ modulo $q$ ( $r_{q}$ ) by $r = lcm (r_{p}, r_{q})$ .

The following reading provides the proof that our desired conditions hold with high probability.

Shor’s Factoring Algorithm Lecture 9

This final section from Vazirani's notes proves that for a random x (our a), its order r is even and x^(r/2) is non-trivial with a good probability.

Read 'Lemma 9.2' and 'Lemma 9.3' on page 2. The proofs are very dense, so focus on grasping the main line of argument, which I will break down for you below.

Let's dissect the argument in Lemma 9.3. We need to show that with high probability, (1) $r$ is even, and (2) $a^{r /2} \neq \equiv - 1 (mod N)$ .

1. Probability that $r$ is even

The order $r = lcm (r_{p}, r_{q})$ is odd if and only if both $r_{p}$ and $r_{q}$ are odd.
The probability that the order of a random element modulo a prime $p$ is odd can be shown to be at most $1/2$ . (This is related to the structure of the multiplicative group $Z_{p}^{*}$ , which is cyclic).
Since $a_{p}$ and $a_{q}$ are chosen independently, the probability that both $r_{p}$ and $r_{q}$ are odd is $P (r_{p} is odd) \times P (r_{q} is odd) \leq \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$ .
Therefore, the probability that $r$ is odd is at most $1/4$ . This means the probability that $r$ is even is at least $1 - 1/4 = 3/4$ .

2. Probability that $a^{r /2} \neq \equiv - 1 (mod N)$

Let's assume $r$ is even. We have found a square root of unity, $x = a^{r /2}$ .
We know $x \neq \equiv 1 (mod N)$ . We fail if $x \equiv - 1 (mod N)$ .
Using the CRT, $x \equiv - 1 (mod N)$ is equivalent to the system of congruences:
- $x \equiv - 1 (mod p)$
- $x \equiv - 1 (mod q)$
The successful cases are when $x$ is a non-trivial root, which corresponds to:
- Case A: $x \equiv 1 (mod p)$ and $x \equiv - 1 (mod q)$
- Case B: $x \equiv - 1 (mod p)$ and $x \equiv 1 (mod q)$
A more detailed analysis (as found in standard texts like Nielsen & Chuang) shows that at least two of the four possible combinations for $(x (mod p), x (mod q))$ are "good" cases. This leads to the conclusion that given $r$ is even, the probability of success (i.e., $a^{r /2} \neq \equiv - 1 (mod N)$ ) is at least $1/2$ .

Combining the probabilities:

The probability of success is $P (r is even) \times P (a^{r /2} \neq \equiv - 1 (mod N) ∣ r is even)$ .
Using the bounds we just discussed, this is at least $\frac{3}{4} \times \frac{1}{2} = \frac{3}{8}$ .
(Note: Most sources, including Nielsen & Chuang, arrive at a tighter lower bound of $1/2$ for the total success probability when $N$ has two prime factors. The logic is slightly different but the conclusion is stronger. For our purposes, showing the probability is a constant significantly greater than zero is sufficient.)

This proves that by picking a random $a$ and finding its order $r$ , we have a constant, high probability of finding a non-trivial factor of $N$ . If we fail, we simply pick another $a$ and try again. A few attempts are very likely to succeed.

Conclusion

In this lesson, we have established the classical number-theoretic backbone of Shor's algorithm.

Key Takeaways:

Factoring via Non-Trivial Roots: The problem of factoring $N$ can be solved if we can find a non-trivial square root of 1 modulo $N$ , i.e., an $x$ such that $x^{2} \equiv 1 (mod N)$ but $x \neq \equiv \pm 1 (mod N)$ . The factors are then given by $gcd (x \pm 1, N)$ .
Reduction to Order-Finding: Such a non-trivial root $x$ can be found by picking a random integer $a$ , computing its order $r$ modulo $N$ , and setting $x = a^{r /2}$ .
Conditions for Success: This procedure works provided that (1) the order $r$ is even, and (2) $a^{r /2} \neq \equiv - 1 (mod N)$ .
High-Probability Guarantee: For a composite number $N = pq$ , these conditions are met for a randomly chosen $a$ with a probability of at least $1/2$ . This ensures that the reduction from factoring to order-finding is not just a theoretical curiosity but a practical and efficient classical reduction.

We have successfully reduced the problem of factoring to the problem of finding the order of an element. The order-finding problem is still computationally hard for classical computers. In our next lessons, we will see how to construct the specific unitary operator for modular exponentiation and then use the Quantum Phase Estimation algorithm to solve the order-finding problem efficiently, completing our construction of Shor's algorithm.