Order-finding algorithm – Zhian Jia

The order-finding problem is a fundamental problem that plays a central role in several quantum algorithms; in particular, it underlies Shor’s celebrated factoring algorithm. Classically, order-finding is hard—no efficient classical algorithm is known—but quantum computers can solve it efficiently. Efficiently determining the order of an integer modulo $N$ allows integers to be factored in polynomial time, which would compromise RSA encryption, as we will discuss in the subsequent sections.

The order-finding problem is defined rigorously as follows:

Definition (Order-Finding Problem) Let $N \in \mathbf{Z}_+$ be a positive integer, and let $a \in \mathbf{Z}_N^{\times}$ be an integer coprime to $N$ (that is, the greatest common divisor $\gcd(a,N)$ of $a$ and $N$ equals one, $\gcd(a,N) = 1$ ). The notation $\mathbf{Z}_N^\times$ denotes the set of invertible elements in $\mathbf{Z}_N$ under multiplication—those integers that are coprime to $N$ . The order of $a$ modulo $N$ , denoted $\mathrm{ord}_N(a)$ or simply $r$ , is the smallest positive integer $r$ such that
$a^r \equiv 1 (\mathrm{mod}\, N)$
The order-finding problem is: given $a$ and $N$ , compute $r = \mathrm{ord}_N(a)$ .

At first glance, this definition may appear somewhat abstract.
Do not worry—shortly, we will unpack each of the mathematical ingredients and illustrate their meaning with concrete examples.

The quantum algorithm for order-finding exploits the periodic structure of the function

$f_{a,N}(x) \equiv a^x (\mathrm{mod}\, N) \ \ \ \ \ (1)$

which is periodic with period exactly $r$ . By preparing a quantum superposition over all possible exponents and applying the quantum phase estimation algorithm to the unitary operator

$U |y\rangle = |a y (\mathrm{mod}\, N)\rangle,$

we obtain an efficient quantum procedure that succeeds with high probability.

Preliminaries of Modular Arithmetic

Before presenting the complete quantum algorithm, let us first review a few essential results from number theory. This section may appear somewhat technical compared to others; if you prefer not to delve into the details, simply remember that for coprime integers $a$ and $N$ , there exists a positive order $r$ , and the function in Eq.(1) is periodic and turn to the next section.

An integer $N > 1$ is called a prime number if it has no nontrivial divisors; for example, $N = 2, 3, 5, 7, 11, \dots$ are prime numbers. Otherwise, $N$ is called a composite number. We use $a \mid b$ to denote that $b$ is divisible by $a$ , for instance $3 \mid 12$ , $2 \mid 6$ . Similarly, $a \nmid b$ means that $a$ does not divide $b$ , for example $3 \nmid 14$ .

Every integer $N > 1$ can be uniquely expressed as a product of prime powers:

$N = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_m^{e_m},$

where $p_1, \ldots, p_m$ are distinct prime numbers and $e_1, \ldots, e_m$ are positive integers. This result is known as the Fundamental Theorem of Arithmetic.

To obtain the prime factorization of a given number $N$ , one typically follows these steps:

Divide $N$ by $2$ repeatedly until the quotient is no longer divisible by $2$ .
Let $e_2$ be the number of times we divide by $2$ , and denote the resulting quotient by $N_2 = N / 2^{e_2}$ , for which $2 \nmid N_2$ .
For the quotient $N_2$ , proceed with the next prime, $3$ , and divide repeatedly until the quotient is no longer divisible by $3$ .
Let $e_3$ be the number of divisions, and denote the resulting quotient by $N_3 = N_2 / 3^{e_3}$ .
Continue in this manner with successive primes $5, 7, 11, \dots$ until the quotient becomes $1$ .

Exercise. Decompose $N = 84$ into its prime factors: $84 = 2^2 \times 3 \times 7$ .

The key operation we will use is modular arithmetic.
In everyday life we count linearly: 1, 2, 3, …, but in modular arithmetic we count on a circle.
Take a clock that shows only 12 hours. When the hand reaches 12, it jumps back to 0.
Mathematically, we say time is measured modulo 12.
This simple idea—wrapping around after a fixed modulus $N$ —is crucial in number theory and its applications in modern public-key cryptography.

Definition (Congruence) Fix an integer $N \ge 2$ , called the modulus.
Two integers $a$ and $b$ are congruent modulo $N$ if their difference is a multiple of $N$ :

$a \equiv b (\mathrm{mod}\, N) \quad \Longleftrightarrow \quad N \mid (a - b) \quad \Longleftrightarrow \quad \exists\, k \in \mathbf{Z} \text{ such that } a = b + kN.$

We read $a \equiv b (\mathrm{mod}\, N)$ as “ $a$ is congruent to $b$ modulo $N$ ”.

The congruence class of $a$ is usually represented by its smallest non-negative residue:

$a (\mathrm{mod}\, N) \in \mathbf{Z}_N := \{0, 1, 2, \dots, N-1\}$

It is also convenient to use $[a]$ to denote the congruence class whenever there is no ambiguity about the modulus.

Example. Let $N = 7$ . We have $\mathbf{Z}_7 :=\{0, 1, 2, \dots, 6\}$ . Then $1 \equiv 8 (\mathrm{mod}\, 7)$ and $2 \equiv 9 (\mathrm{mod}\, 7)$ . The congruence class $[0]$ consists of $\{0, 7, 14, 21, \dots\}$ , the congruence class $[1]$ consists of $\{1, 8, 15, 22, \dots\}$ , and $[2]$ consists of $\{2, 9, 16, 23, \dots\}$ , etc.

The order-finding problem considers the modular exponentiation for given integers $a$ and $N$ :

$a^x \equiv b (\mathrm{mod}\, N)$

The remainder $b$ can take values in $0, 1, \dots, N-1$ :

$a \equiv 0 (\mathrm{mod}\, N)$
$a \equiv 1 (\mathrm{mod}\, N)$
$\vdots$
$a \equiv N-1 (\mathrm{mod}\, N)$

However, not all values of $b = 0, 1, \dots, N-1$ are necessarily attainable.

For example, let $a = 2$ and $N = 6$ . We find that

$2^0 \equiv 1 (\mathrm{mod}\, 6)$
$2^1 \equiv 2 (\mathrm{mod}\, 6)$
$2^2 \equiv 4 (\mathrm{mod}\, 6)$
$2^3 \equiv 2 (\mathrm{mod}\, 6)$
$2^4 \equiv 4 (\mathrm{mod}\, 6)$
$2^5 \equiv 2 (\mathrm{mod}\, 6)$
$\vdots$

We observe a repeating pattern. In this case, the residues $0$ , $3$ , and $5$ never appear.

Note also that $a^0 \equiv 1 (\mathrm{mod}\, N)$ for any integers $a$ and $N$ . Hence, the order of $a$ modulo $N$ is defined as the smallest positive integer $r$ such that $a^r \equiv 1 (\mathrm{mod}\, N)$ . However, we must still ensure that such an order actually exists. In fact, if $\gcd(a, N) = d > 1$ , then no positive integer $r$ satisfies $a^r \equiv 1 (\mathrm{mod}\, N)$ . This can be seen in the previous example with $a = 2$ and $N = 6$ , where the sequence never returns to $1$ modulo $6$ .

Exercise. Let $N > 1$ and $\gcd(a, N) = d > 1$ . Then the only integer $r$ satisfying

$a^r \equiv 1 (\mathrm{mod}\, N)$

is $r = 0$ .

Proof. Suppose there exists an integer $r$ such that $a^r \equiv 1 (\mathrm{mod}\, N)$ .
Then $N$ divides $a^r - 1$ , so in particular

$d \mid (a^r - 1)$ .

Since $d \mid a$ , we also have $d \mid a^r$ , and therefore

$d \mid (a^r - 1) \implies d \mid 1$ ,

which contradicts $d > 1$ . Hence no such $r \neq 0$ exists.

For $r = 0$ , the convention $a^0 = 1$ gives

$a^0 = 1 \equiv 1 (\mathrm{mod}\, N)$

trivially. Thus $r = 0$ is the only solution ∎.

In Shor’s algorithm, we either assume $\gcd(a, N) = 1$ , or first compute the greatest common divisor classically, which already yields a nontrivial factor of $N$ if $d > 1$ .

Another useful concept we will use is Euler’s Totient function: $\varphi(N)$ counts the number of integers $k \in {1, 2, \dots, N-1}$ coprime to $N$ .
For example, $\varphi(1) = 1$ , $\varphi(2) = 1$ , $\varphi(3) = 2$ , $\varphi(4) = 2$ , etc.

For fixed $N$ , consider $\mathbf{Z}_N$ .
We call $a \in \mathbf{Z}_N$ invertible if there exists an integer $c$ such that $a c \equiv 1 (\mathrm{mod}\, N)$ .

Proposition (Bézout’s Identity). Let $a$ and $b$ be integers with greatest common divisor $d = \gcd(a,b)$ . Then there exist integers $x$ and $y$ such that

$a x + b y = d$ .

Moreover, the integers of the form $a z + b t$ are exactly the multiples of $d$ .

The set $\mathbf{Z}_N$ is not a group under multiplication modulo $N$ in general. We denote by $(\mathbf{Z}_N^{\times}, \times)$ the set of invertible elements, which indeed forms a group. By Bézout’s identity, $\mathbf{Z}_N^{\times}$ consists of all integers coprime to $N$ , and this group has order $\phi(N)$ , where $\phi$ denotes Euler’s totient function.

From a group-theoretic perspective, for any $a \in \mathbf{Z}_N^{\times}$ , there exists a positive integer $r$ such that

$a^r \equiv 1 (\mathrm{mod}\, N)$ .

Since $a$ must be invertible, it follows that $\gcd(a, N) = 1$ . In the multiplicative group $\mathbf{Z}_N^{\times}$ , the order of any element divides the order of the group, that is,

$r \mid |\mathbf{Z}_N^{\times}| = \phi(N)$ .

Theorem (Euler’s Theorem). If $\gcd(a, N) = 1$ , then

$a^{\phi(N)} \equiv 1 (\mathrm{mod}\, N)$

and hence the order of $a$ modulo $N$ divides $\phi(N)$ .

By Euler’s theorem, for integers $a$ and $N$ with $\gcd(a, N) = 1$ , there always exists a positive integer $r$ such that

$a^r \equiv 1 (\mathrm{mod}\, N).$

The order $r = \mathrm{ord}_N(a)$ always satisfies $1 \le r \le \phi(N)$ .

Since in the cyclic subgroup generated by $[a] \in \mathbf{Z}_N^{\times}$ we have

${[a^0], [a^1], [a^2], \dots, [a^{r-1}]}, \quad \text{with } [a^r] = [a^0] = [1],$

the sequence $a^n (\mathrm{mod}\, N)$ is periodic with period equal to the order $r$ :

$a^0 \equiv 1 (\mathrm{mod}\, N)$
$a^1 \equiv a (\mathrm{mod}\, N)$
$\dots$
$a^{r-1} \not\equiv 1 (\mathrm{mod}\, N)$
$a^r \equiv 1 (\mathrm{mod}\, N)$
$a^{r+1} \equiv a (\mathrm{mod}\, N)$
$a^{r+2} \equiv a^2 (\mathrm{mod}\, N)$
$a^{r+3} \equiv a^3 (\mathrm{mod}\, N)$

Thus, the sequence repeats with period $r$ .

Example. Set $a = 2$ and $N = 7$ . We have $f_{a,N}(x) = 2^x (\mathrm{mod}\, 7)$ as:

$2^0 \equiv 1 (\mathrm{mod}\, 7)$
$2^1 \equiv 2 (\mathrm{mod}\, 7)$
$2^2 \equiv 4 (\mathrm{mod}\, 7)$
$2^3 \equiv 8 \equiv 1 (\mathrm{mod}\, 7)$
$2^4 \equiv 16 \equiv 2 (\mathrm{mod}\, 7)$
$2^5 \equiv 32 \equiv 4 (\mathrm{mod}\, 7)$
$2^6 \equiv 64 \equiv 1 (\mathrm{mod}\, 7)$
$2^7 \equiv 128 \equiv 2 (\mathrm{mod}\, 7)$
$2^8 \equiv 256 \equiv 4 (\mathrm{mod}\, 7)$

We see that the order is $r = \mathrm{ord}_7(2) = 3$ .

Quantum Order-Finding Algorithm

The quantum order-finding algorithm can be divided into two main steps:

Encode the order into the phase of an eigenvalue of a suitable unitary operator, thereby reducing the order-finding problem to a quantum phase estimation problem.
Recover the order $r$ from the estimated phase $\varphi$ using the method of continued fractions.

Let us first examine how to encode the order into the phase of a unitary operator.

Fix integers $a$ and $N$ such that $\gcd(a, N) = 1$ .
Define the unitary operator $U_{a,N}$ acting on computational basis states $|y\rangle$ by

$U_{a,N} |y\rangle = | a y (\mathrm{mod}\, N) \rangle, \quad y = 0, 1, \dots, N-1$

We will see that the order can be mapped to the phase of an eigenvalue of $U_{a,N}$ .

Proposition. Let $N \ge 2$ and let $a$ be an integer coprime to $N$ .
The operator $U_{a,N}$ on $\mathbf{C}^N$ defined by

$U_{a,N} |y\rangle = | a y (\mathrm{mod}\, N) \rangle, \quad y = 0, 1, \dots, N-1$

is unitary.

Proof. Since $\gcd(a, N) = 1$ , multiplication by $a$ modulo $N$ defines a bijection on the set ${0, 1, \dots, N-1}$ .
Thus $U_{a,N}$ merely permutes the computational basis ${ |0\rangle, |1\rangle, \dots, |N-1\rangle }$ . Any permutation of an orthonormal basis extends to a unitary operator, so $U_{a,N}$ is unitary.

Alternatively, suppose $U_{a,N} |y\rangle = U_{a,N} |y'\rangle$ . Then

$a y \equiv a y' (\mathrm{mod}\, N) \implies a (y - y') \equiv 0 (\mathrm{mod}\, N) \implies N \mid a (y - y')$ .

Because $\gcd(a, N) = 1$ , we may cancel $a$ (more precisely, multiply both sides by the modular inverse of $a$ modulo $N$ ) to obtain

$N \mid (y - y')$ .

Since $0 \le y, y' < N$ , the only possibility is $y - y' = 0$ , so $y = y'$ .
Thus $U_{a,N}$ is injective on a basis of $\mathbf{C}^N$ .
Being an isometry that maps a basis to a basis, it is unitary ∎.

Proposition. Let $r$ be the order of $a$ modulo $N$ , i.e., the smallest positive integer such that

$a^r \equiv 1 (\mathrm{mod}\, N)$ .

For each $s = 0, 1, \dots, r-1$ , define the state

$|u_s\rangle := \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{-2\pi i s k / r} \, | a^k (\mathrm{mod}\, N) \rangle.$

Then, for each $s = 0, 1, \dots, r-1$ , $|u_s\rangle$ is an eigenstate of $U_{a,N}$ with eigenvalue

$e^{2\pi i s / r}$ .

Proof. Apply $U_{a,N}$ to $|u_s\rangle$ :

$U_{a,N} |u_s\rangle = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{-2\pi i s k / r} \, U_{a,N} | a^k (\mathrm{mod}\, N) \rangle$

$\quad\; = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{-2\pi i s k / r} \, | a^{k+1} (\mathrm{mod}\, N) \rangle$

Reindex the sum by letting $k \mapsto k+1$ :

$\quad\; = \frac{1}{\sqrt{r}} \sum_{k=1}^{r} e^{-2\pi i s (k-1) / r} \, | a^k (\mathrm{mod}\, N) \rangle$

$\quad\; = \frac{1}{\sqrt{r}} \sum_{k=1}^{r} e^{-2\pi i s k / r} \, e^{2\pi i s / r} \, | a^k (\mathrm{mod}\, N) \rangle$

$\quad\; = e^{2\pi i s / r} \frac{1}{\sqrt{r}} \sum_{k=1}^{r} e^{-2\pi i s k / r} \, | a^k (\mathrm{mod}\, N) \rangle$

The sum now runs from $k = 1$ to $r$ , but the $k = r$ term is

$e^{-2\pi i s r / r} \, | a^r (\mathrm{mod}\, N) \rangle = e^{-2\pi i s} \, | 1 (\mathrm{mod}\, N) \rangle = | 1 (\mathrm{mod}\, N) \rangle,$

while the $k = 0$ term in the original definition of $|u_s\rangle$ is

$e^0 \, | a^0 (\mathrm{mod}\, N) \rangle = | 1 (\mathrm{mod}\, N) \rangle.$

Thus the missing $k = 0$ term is exactly replaced by the $k = r$ term, and we obtain

$U_{a,N} |u_s\rangle = e^{2\pi i s / r} \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{-2\pi i s k / r} \, | a^k (\mathrm{mod}\, N) \rangle = e^{2\pi i s / r} |u_s\rangle.$

This holds for every $s = 0, 1, \dots, r-1$ ∎.

Now the procedure becomes “straightforward”. We apply quantum phase estimation (see this post) to the operators $U_a^{2^j}$ with the eigenstate $|u_s\rangle$ , which yields the phases

$\theta_s = \frac{s}{r}, \quad s = 0, 1, \dots, r-1$

The output of the phase estimation algorithm is thus

$0.\theta_0 \theta_1 \dots \theta_{n}$

represented as binary numbers. A classical algorithm called continued fractions can be applied to obtain the order $r$ .