Shor’s Algorithm: Breaking RSA and ECC Encryption

The Crypto Breaker

Shor’s algorithm is a groundbreaking quantum algorithm designed to solve the period finding problem, all within polynomial time.

The period finding problem seeks the smallest $r$ such that:

\[f(x) = f(x + r),\]

and it can be generalized to multivariate functions (functions with multiple inputs). In such cases, the goal is to find periods $r_1, r_2, \ldots, r_n$ such that:

\[f(x_1, x_2, \ldots, x_n) = f(x_1 + r_1, x_2 + r_2, \ldots, x_n + r_n).\]

Why is this problem a big deal? It turns out that the period-finding problem is the key to breaking widely-used encryption schemes like RSA and ECC(elliptic curve cryptography). These encryption schemes rely on problems considered computationally infeasible for classical computers:

• RSA: integer factorization problem
• ECC: elliptic curve discrete logarithm problem

By using Shor’s algorithm efficiently solve the period-finding problem, we can reduce these “hard” problems to ones that quantum computers can solve in polynomial time.

Before We Begin

In this article, we’ll explore how Shor’s algorithm can be applied to break RSA and ECC encryption schemes. While the algorithm shares some similarities with the simpler Deutsch-Jozsa algorithm, Shor’s algorithm is significantly more complex and operates on a much grander scale.

To help navigate this complexity, we’ll take a top-down approach:

• Start with the top-level goal (or problem)
  • Breaking encryption schemes is the top-level goal
• Gradually break down the goal into smaller, more manageable sub-goals:
  • Assume the sub-goals are already achieved: imagine we have access to oracle that can solve these sub-problems
  • Demonstrate how the goal can be achieved: show that if these sub-goals are solved, the higher-level goal can be achieved as well
• Finally, explore how quantum circuits solve the core sub-problems

This approach will help us understand the algorithm’s inner workings and how it fundamentally disrupts classical cryptographic assumptions.

Goal 0: Breaking Encryption Schemes

The ultimate goal is to solve two foundational problems in cryptography:

• Integer factorization problem (IFP), breaking RSA encryption
• Elliptic curve discrete logarithm problem (ECDLP), breaking ECC encryption

These problems are critical to the security of RSA and ECC, respectively. We’ll skip the detailed cryptographic implications and focus on how both problems can be reduced to the period-finding problem, the core challenge Shor’s algorithm addresses. Here’s how these reductions work:

Reducing IFP to the Period-Finding Problem

Goal: Given an integer $N$, find its prime factors.

We assume access to an oracle that can solve the period-finding problem.

1. Pick a random integer $a$ such that $1 < a < N$ and $\gcd(a, N) = 1$. If $\gcd(a, N) \neq 1$, then we have already found a factor of $N$. (Efficient classical algorithms exist for computing the greatest common divisor.)

2. Define the function as $f(x) = a^x \mod N$. This function is periodic with period $r$ such that:

   \[a^{x} \equiv a^{x + r} \mod N,\]

   and we know what $r$ by assumption. The period $r$ is the smallest integer satisfying $a^r \equiv 1 \mod N$.

3. If $r$ is odd, repeat with a different $a$ (proven to succeed with high probability). If $r$ is even, proceed to the next step.

4. Compute:

   \[x = a^{r/2} \mod N.\]

   If $x = \pm 1 \mod N$, choose another random $a$ and repeat the process. Otherwise, proceed to the next step.

5. Compute $\gcd(x \pm 1, N)$ which yields the factors of $N$. This follows from:

   \[x^2 \equiv 1 \mod N \implies (x - 1)(x + 1) \equiv 0 \mod N.\]

The above steps show that the integer factorization problem reduces to the period-finding problem.

Reducing ECDLP to Period-Finding Problem

Goal: Given an elliptic curve $E$ defined over a finite field $\mathbb{F}_p$ and a point $P$ on the curve, find the integer $k$ such that $Q=kP$.

1. Define the function $f(a,b)=aP + bQ$, where $a$ and $b$ are integers. This function maps pairs of integers to points on the curve.

2. The function $f(a,b)$ is periodic due to the finite number of points on the curve. It has periods $r_a$ and $r_b$ such that:

   \[f(a,b) = f(a + r_a, y + r_b).\]

   The periods $r_a$ and $r_b$ can be determined using a period-finding oracle.

3. Solve for $k$ using $k=-r_a r_b^{-1} \mod n$, where $n$ is the order of the curve. This follows from:

   \[\begin{aligned} & aP + bQ = (a + r_a)P + (b + r_b)Q \\ \implies & r_a P + r_b Q = 0 \\ \implies & Q = -r_a r_b^{-1} P. \end{aligned}\]

These steps show that the ECDLP reduces to the period-finding problem.

The Hidden Subgroup Problem

FYI, Both the IFP, ECDLP, and the period-finding problem are instances of a more broad class of problems called the hidden subgroup problem (HSP). The power of Shor’s algorithm lies in its ability to solve these HSPs.

Goal 1: Period-Finding Problem

Having reduced the IFP and ECDLP to the period-finding problem, let’s now focus on solving this key problem. For simplicity, we’ll work with univariate functions, though the algorithm generlizes to multivariate cases.

Goal: Given a function $f(x)$, find the smallest integer $r$ such that $f(x) = f(x + r)$.

Function as a Unitary Operator

To leverage quantum computing, we represent the function $f(x)$ as a quantum circuit, which implements a unitary operator $U_f$. The operator acts on a register of qubits encoding the function’s input and outputs:

\[U_f \ket{f(x)} = \ket{f(x+1)}.\]

Here, $\ket{f(x)}$ is a quantum state encoding the value of $f(x)$. For example, if $f(x)$ outputs integers from 0 to 7, $\ket{f(x)}$ would be a state of 3 qubits: $\ket{0}$ would be $\ket{000}$, and $\ket{7}$ would be $\ket{111}$.

The challenge is to extract information about the period $r$ from the unitary operator $U_f$. This is where eigenstates and eigenvalues play a crucial role.

Eigenvectors and Eigenvalues

For those unfamiliar with these terms, here’s a quick explanation: in linear algebra, eigenvectors (or eigenstates) are special vectors associated with a matrix. When a matrix $U$ acts on its eigenvector $\ket{\psi}$, the result is simply the eigenvector scaled by a constant factor, called the eigenvalue. Mathematically:

\[U \ket{\psi} = \lambda \ket{\psi},\]

where $\ket{\psi}$ is an eigenvector, and $\lambda$ is its corresponding eigenvalue. This relationship makes eigenvectors and eigenvalues crucial in understanding the behavior of matrix operators like $U$.

Eigenstates of $U_f$

The key insight is that the eigenstates and eigenvalues of $U_f$ encode information about the period of the function $f$. By leveraging the periodicity in $f$, we can construct eigenstates related to this periodicity. Even though we don’t know the period $r$, we know it exists. Let’s build an eigenstate $\ket{u_0}$:

\[\ket{u_0} = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \ket{f(k)} = \frac{1}{\sqrt{r}} \prths{\ket{f(0)} + \ket{f(1)} + \ldots + \ket{f(r-1)}}.\]

Why is this an eigenstate? To verify, let’s apply $U_f$ to $\ket{u_0}$:

\[\begin{aligned} U_f \ket{u_0} &= \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} U_f \ket{f(k)} \\ &= \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \ket{f(k+1)} \\ &= \frac{1}{\sqrt{r}} \prths{\ket{f(1)} + \ket{f(2)} + \ldots + \ket{f(r)}} \\ &= \frac{1}{\sqrt{r}} \prths{\ket{f(1)} + \ket{f(2)} + \ldots + \ket{f(0)}} \\ &= \ket{u_0}, \end{aligned}\]

where the periodicity ensures $\ket{f(r)} = \ket{f(0)}$. This confirms that $\ket{u_0}$ is an eigenstate of $U_f$ with eigenvalue 1.

We can generalize $\ket{u_0}$ to a family of eigenstates $\ket{u_s}$ for $0 \leq s \leq r-1$:

\[\ket{u_s} = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp{\prths{-\frac{2\pi isk}{r}}} \ket{f(k)},\]

The eigenvalue for $\ket{u_s}$ can be calculated by applying $U_f$:

\[\begin{aligned} U_f \ket{u_s} &= \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp{\prths{-\frac{2\pi isk}{r}}} \ket{f(k+1)} \\ &= \exp{\prths{\frac{2\pi is}{r}}} \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp{\prths{-\frac{2\pi isk}{r}}} \ket{f(k)} \\ &= \exp{\prths{\frac{2\pi is}{r}}} \ket{u_s}. \end{aligned}\]

Thus, $\ket{u_s}$ is an eigenstate of $U_f$ with eigenvalue $\exp{\prths{\frac{2\pi is}{r}}}$. This eigenvalue contains information about the period $r$, specifically the value of $\frac{s}{r}$.

Preparing Eigenstates Without Knowing $r$

To solve the period-finding problem, we need to find the eigenvalue $\exp{\prths{\frac{2\pi is}{r}}}$ associated with the eigenstate $\ket{u_s}$, which encodes $\frac{s}{r}$, the information about the period $r$.

The quantum phase estimation (QPE) algorithm can estimate the eigenvalue $\exp{\prths{\frac{2\pi is}{r}}}$ for a given unitary operator (like $U_f$) and its corresponding eigenstate $\ket{u_s}$. However, there’s a challenge: QPE requires the eigenstate $\ket{u_s}$ as input, but we don’t know the period $r$, so we cannot prepare $\ket{u_s}$ directly.

Fortunately, we can exploit the structure of the eigenstates and superposition to overcome this challenge.

Recall the eigenstates of $U_f$:

\[\ket{u_s} = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp{\prths{-\frac{2\pi isk}{r}}} \ket{f(k)},\]

where $0 \leq s \leq r-1$. Consider a superposition of all eigenstates $\ket{u_s}$ weighted by a complex phase factor $\exp{\prths{\frac{2\pi isk^\prime}{r}}}$ for some $k^\prime$:

\[\frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \exp{\prths{\frac{2\pi isk^\prime}{r}}} \ket{u_s}.\]

Expanding $\ket{u_s}$, this becomes:

\[\begin{aligned} \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \exp{\prths{\frac{2\pi isk^\prime}{r}}} \ket{u_s} &= \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \exp{\prths{\frac{2\pi isk^\prime}{r}}} \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} \exp{\prths{-\frac{2\pi isk}{r}}} \ket{f(k)} \\ &= \frac{1}{r} \sum_{s=0}^{r-1} \sum_{k=0}^{r-1} \exp{\prths{\frac{2\pi is(k^\prime-k)}{r}}} \ket{f(k)} \\ &= \frac{1}{r} \sum_{k=0}^{r-1} \prths{ \sum_{s=0}^{r-1} \exp{\prths{\frac{2\pi is(k^\prime-k)}{r}}} } \ket{f(k)}. \end{aligned}\]

The inner sum over $s$,

\[\sum_{s=0}^{r-1} \exp{\prths{\frac{2\pi is(k^\prime-k)}{r}}},\]

is nonzero only when $k^\prime = k$, due to the properties of complex exponentials (they sum to zero for $k^\prime \neq k$). When $k^\prime = k$, the sum becomes $r$, leading to:

\[\begin{aligned} \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \exp{\prths{\frac{2\pi isk^\prime}{r}}} \ket{u_s} &= \frac{1}{r} \prths{ 0 \ket{f(0)} + 0 \ket{f(1)} + \ldots + r \ket{f(k^\prime)} + \ldots + 0 \ket{f(r-1)} } \\ &= \ket{f(k^\prime)}. \end{aligned}\]

If we set $k^\prime$ to $0$, we get:

\[\frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \exp{\prths{\frac{2\pi is \cdot 0}{r}}} \ket{u_s} = \frac{1}{\sqrt{r}} \sum_{s=0}^{r-1} \ket{u_s} = \ket{f(0)}.\]

This result shows that the state $\ket{f(0)}$, which we can prepare without knowing the period $r$, is a uniform superposition of all eigenstates $\ket{u_s}$! Therefore, $\ket{f(0)}$ can serve as an input to QPE to estimate the eigenvalues of $U_f$.

Extracting the Period $r$

Applying QPE to $\ket{f(0)}$ produces a random fraction $\frac{s}{r}$ since $\ket{f(0)}$ is a superposition of all $\ket{u_s}$. Repeating QPE multiple times gives a set of fractions $\frac{s_1}{r}$, $\frac{s_2}{r}$, $\ldots$, $\frac{s_n}{r}$, with the common denominator $r$. It is proven that we can efficiently deduce the period $r$ from these fractions.

For example, suppose QPE yields the following fractions:

\[\frac{1}{6}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{5}{6}.\]

The common denominator of these fractions is 6, revealing the period $r$ of $f$.

Reduction to Eigenvalue-Finding Problem

By recognizing the fact that $\ket{f(0)}$ is a superposition of all $\ket{u_s}$, we can effectively use the quantum phase estimation (QPE) algorithm—an oracle for finding eigenvalues—to find the eigenvalues of $U_f$, and, consequently, the period $r$.

This reduction shows that solving the period-finding problem reduces to solving the eigenvalue-finding problem via QPE. Through multiple runs of QPE, we can effectively determine the period $r$.

Goal 2: Eigenvalue-Finding Problem (QPE)

Goal: Given a unitary operator $U$ and an eigenstate $\ket{u}$, find $\varphi$ such that $e^{2\pi i\varphi}$ is the eigenvalue of $U$

The quantum phase estimation (QPE) algorithm is a quantum computing algorithm designed to solve this problem. It determines the phase $\varphi$, which encodes information about the eigenvalue $e^{2\pi i\varphi}$ of a unitary operator $U$, acting on an eigenstate $\ket{u}$.

QPE Algorithm: First Half

The diagram above illustrates the first half of the QPE algorithm. It uses two qubit registers:

1. First Register: Contains $t$ qubits initialized to $\ket{0}$.
2. Second Register: Prepared in the eigenstate $\ket{u}$.

The algorithm proceeds as follows:

1. Apply a Hadamard gate to each qubit in the first register. This creates a uniform superposition.

2. Apply controlled-$U^{2^0}$ gate to the second register, controlled by the first qubit (the bottom-most qubit) of the first register.

   The operator $U^{2^0}$ applies unitary operator $U$ $2^0$ times. This operator is controlled by the first qubit of the first register:

   • If the control qubit is in state $\ket{1}$, $U^{2^0}$ is applied to the second register.
   • If the control qubit is in state $\ket{0}$, $U^{2^0}$ is not applied.

   Since the control qubit is in superposition, $U$ is applied to only the part of the second register that corresponds to the $\ket{1}$ component of the first register’s superposition.

   Given that $\ket{u}$ is an eigenstate of $U$, the application of $U^{2^0}$ leaves $\ket{u}$ unchanged, but introduces a phase factor $e^{2\pi i (2^0 \varphi)}$ (the eigenvalue of $U$) to the $\ket{1}$ component of the control qubit.

3. Sequentially apply controlled-$U^{2^j}$ gate to the second register, controlled by the $j$-th qubit of the first register, for $j = 0, 1, \ldots, t-1$ (we’ve already applied the $j=0$ case in the previous step).

   Each controlled-$U^{2^j}$ applies $U$ $2^j$ times, when the corresponding control qubit is in state $\ket{1}$.

   For each controlled operation, the phase factor $e^{2\pi i(2^j \varphi)}$ is introduced to the $\ket{1}$ part of the control qubit, encoding the eigenvalue’s phase information in the first register.

Now the first register is in a superposition of states, each encoding a phase factor related to $\varphi$:

\[\frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i(2^0 \varphi)}\ket{1}} \otimes \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i(2^1 \varphi)}\ket{1}} \otimes \ldots \otimes \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i(2^{t-1} \varphi)}\ket{1}}\]

To simplify, let’s represent the phase factor $\varphi$, the yet-to-be-determined phase factor, as a binary fraction:

\[\varphi = 0.\varphi_1\varphi_2\ldots\varphi_t,\]

where $\varphi_j$ represents the $j$-th bit of $\varphi$. The integer part of $\varphi$ can be ignored, as it does not contribute to the phase $e^{2\pi i\varphi}$. Now the phase factors can be expressed using the binary fraction (observe the placement of the dot):

\[e^{2\pi i(2^j \varphi)} = e^{2\pi i(2^j \cdot 0.\varphi_1\varphi_2\ldots\varphi_t)} = e^{2\pi i(\varphi_1\ldots\varphi_j.\varphi_{j+1}\ldots\varphi_t)} = e^{2\pi i(0.\varphi_{j+1}\ldots\varphi_t)}.\]

Substituting this into the state of the first register, the superposition becomes:

\[\begin{aligned} & \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i(2^0 \varphi)}\ket{1}} \otimes \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i(2^1 \varphi)}\ket{1}} \otimes \ldots \otimes \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i(2^{t-1} \varphi)}\ket{1}} \\ = & \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2\ldots\varphi_t}\ket{1}} \otimes \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i0.\varphi_2\ldots\varphi_t}\ket{1}} \otimes \ldots \otimes \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i0.\varphi_t}\ket{1}} \\ = & \frac{1}{\sqrt{2^t}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2\ldots\varphi_t}\ket{1}} \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_2\ldots\varphi_t}\ket{1}} \otimes \ldots \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_t}\ket{1}}. \end{aligned}\]

QPE Algorithm: Second Half

After the first half of the QPE algorithm, the first register is in the state:

\[\frac{1}{\sqrt{2^t}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2\ldots\varphi_t}\ket{1}} \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_2\ldots\varphi_t}\ket{1}} \otimes \ldots \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_t}\ket{1}}.\]

The goal is to extract the binary representation of the phase:

\[\varphi = 0.\varphi_1\varphi_2\ldots\varphi_t,\]

by transforming this complicated superposition into a simple state of

\[\ket{\varphi_1\varphi_2\ldots\varphi_t}\]

so that we can measure the first register to obtain the binary fraction $\varphi$.

Fortunately, this transformation is achieved by the inverse quantum Fourier transform (QFT$^{-1}$), which effectively “decodes” the phase information encoded in the relative phases of the superposition.

By assuming we have the QFT$^{-1}$ as an oracle, the eigenvalue-finding problem is solved! The process concludes with measuring the first register to directly obtain the binary fraction $\varphi$.

This reduces the eigenvalue-finding problem to the problem of transforming the quantum state:

\[\frac{1}{\sqrt{2^t}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2\ldots\varphi_t}\ket{1}} \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_2\ldots\varphi_t}\ket{1}} \otimes \ldots \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_t}\ket{1}}.\]

into the clean state:

\[\ket{\varphi_1\varphi_2\ldots\varphi_t}.\]

Goal 3: Transforming the Superposition into Clean State (QFT$^{-1}$)

Goal: Given a superposition of states:

\[\frac{1}{\sqrt{2^t}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2\ldots\varphi_t}\ket{1}} \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_2\ldots\varphi_t}\ket{1}} \otimes \ldots \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_t}\ket{1}},\]

transform it into the clean state $\ket{\varphi_1\varphi_2\ldots\varphi_t}$.

This goal is achieved by the inverse quantum Fourier transform (QFT$^{-1}$), which reverses the transformation performed by the quantum Fourier transform (QFT). Since the QFT is a unitary operator, its inverse is simply the conjugate transpose. To better understand how to achieve this goal, it helps to examine the forward transformation performed by the QFT, as solving one naturally solves the other:

Goal (inverse): Given the clean state $\ket{\varphi_1\varphi_2\ldots\varphi_t}$, transform it into the superposition of states:

\[\frac{1}{\sqrt{2^t}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2\ldots\varphi_t}\ket{1}} \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_2\ldots\varphi_t}\ket{1}} \otimes \ldots \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_t}\ket{1}}.\]

Quantum Fourier Transform (QFT)

The diagram above illustrates the quantum Fourier transform (QFT) circuit. The clean state $\ket{\varphi_1\varphi_2\ldots\varphi_t}$ is input to the QFT, which transforms it into the superposition of states:

\[\frac{1}{\sqrt{2^t}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2\ldots\varphi_t}\ket{1}} \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_2\ldots\varphi_t}\ket{1}} \otimes \ldots \otimes \prths{\ket{0} + e^{2\pi i0.\varphi_t}\ket{1}}.\]

The unitary operator $R_k$ is a gate that modifies the phase of the state $\ket{1}$ by $2\pi/2^k$, and defined as:

\[R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^k} \end{pmatrix}, \quad R_k \ket{0} = \ket{0}, \quad R_k \ket{1} = e^{2\pi i/2^k} \ket{1}.\]

Then, the operation of the QFT circuit becomes intuitive. Consider the first qubit of the state $\ket{\varphi_1}$. The Hadamard gate acts on this qubit to create a superposition of $\ket{0}$ and $\ket{1}$, determined by whether $\varphi_1$ is 0 or 1:

\[H\ket{\varphi_1} = \frac{1}{\sqrt{2}}\prths{\ket{0} + (-1)^{\varphi_1}\ket{1}} = \frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i0.\varphi_1}\ket{1}}.\]

Next, the controlled-$R_2$ gate applies a phase factor $e^{2\pi i\;0.01}$, controlled by the second qubit $\varphi_2$. This is equivalent to applying a phase factor $e^{2\pi i0.0\varphi_2}$ to the $\ket{1}$ component of the first qubit. After this step, the state of the first qubit becomes:

\[\frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2}\ket{1}}.\]

Continuing this process, each subsequent controlled-$R_k$ gate introduces a phase factor determined by the corresponding qubit $\varphi_k$. By the time the process reaches the $t$-th qubit, the state of the first qubit becomes:

\[\frac{1}{\sqrt{2}}\prths{\ket{0} + e^{2\pi i0.\varphi_1\varphi_2\ldots\varphi_t}\ket{1}},\]

which represents the first qubit of the desired superposition state. Similarly, the second, third, and all subsequent qubits undergo analogous transformations, leading to the desired superposition state shown on the right side of the QFT circuit diagram.

This sequence of operations completes the transformation of the clean input state $\ket{\varphi_1\varphi_2\ldots\varphi_t}$ into the desired superposition of states. Applying the QFT$^{-1}$ then reverses this transformation, recovering the clean state from the superposition, as required.

QED!

I’m afraid we’re out of goals! We’ve successfully broken down the core problems of Shor’s algorithm into manageable sub-goals, and demonstrated how each sub-goal can be achieved.

Complexity Analysis

Space Complexity

The space complexity of Shor’s algorithm is minimal, as the quantum circuit only requires enough qubits to encode the output of the function $f$. Since the size of the output is logarithmic in the problem size $N$ (e.g., for factoring $N$ or solving discrete logarithm problems over a field of size $p$), the space complexity is $O(\log N)$.

Time Complexity

The time complexity depends on the specific encryption scheme being targeted, as the quantum implementation of the function $f$ varies.

1. RSA (IFP): For RSA, the most computationally expensive step is modular exponentiation, which is implemented in the quantum circuit with a time complexity of $O(\log^3 N)$, where $N$ is the number to be factored.

2. ECC (ECDLP): For ECC, according to Martin et al., the complexity depends on the arithmetic operations over the finite field and is estimated to be $O(\log^3 p \log\log p)$, where $p$ is the order of the finite field.