Composite Number Factorization Using Modular Exponentiation Period

Introduction

Most of the modern cryptosystems were developed based on the fact that it is extremely inefficient to factoring large composite numbers, usually in exponential complexity. Therefore, breaking these cryptosystems have been extremely hard. With a quantum computer, the quantum Shor’s algorithm is able to factorize large composite numbers in polynomial complexity. However, the Shor’s algorithm does have a fraction that uses classical algorithm to factorize the composite number given a special modular exponential period value found by the quantum circuit.

In this blog post, I would like to discuss the classical part of the Shor’s algorithm, leaving finding out the modular exponential period as a magic remained to be discussed in the future blog posts.

Prerequisites

Modular Algorithmic - Compatibility With Scaling

If for some integer $a$, $b$, and $n$,

$$
a \equiv b \pmod{n}
$$

Then we have the following modular algorithmic.

$$
ka \equiv kb \pmod{n}
$$

for any integer $k$.

Proof

Because $a - b = tn$ for some integer $s$, $k(a - b) = ka - kb = ksn$ for any integer $k$. So, $ks$ is also an integer. This concludes the proof.

Modular Algorithmic - Compatibility With Multiplication

If for some integer $a_1$, $a_2$, $b_1$, $b_2$, and $n$,

$$
\begin{align}
a_1 &\equiv b_1 \pmod{n} \\
a_2 &\equiv b_2 \pmod{n} \\
\end{align}
$$

Then we also have the following modular algorithmic.

$$
a_1 a_2 \equiv b_1 b_2 \pmod{n} \\
$$

Proof

Because we have

$$
\begin{align}
a_1 - b_1 &= k_1 n \\
a_2 - b_2 &= k_2 n \\
\end{align}
$$

Then

$$
\begin{align}
a_1 a_2 - b_1 b_2 &= (b_1 + k_1n) (b_2 + k_2n) - b_1 b_2 \\
&= b_1 b_2 + b_1 k_2 n + k_1 b_2 n + k_1 k_2 n^2 - b_1 b_2 \\
&= b_1 k_2 n + k_1 b_2 n + k_1 k_2 n^2 \\
&= (b_1 k_2 + k_1 b_2 + k_1 k_2 n)n \\
\end{align}
$$

This concludes the proof.

Euler’s Totient Function

In number theory, Euler’s totient function, also called Euler’s phi function, denoted as $\varphi(n)$, counts the positive integers up to a given integer $n$ that are relatively prime to $n$. In other words, it is the number of integers $k$ in the range $1 \leq k \leq n$ for which the greatest common divisor $\gcd(n, k)$ is equal to 1.

Euler’s totient function is a multiplicative function, meaning that if two numbers $m$ and $n$ are relatively prime, then,

$$
\varphi(mn) = \varphi(m)\varphi(n)
$$

If $k$ numbers, $\{m_1, m_2, \cdots, m_k\}$, are pairwise relatively prime, then

$$
\varphi(\prod_{i=1}^{k}m_i) = \prod_{i=1}^{k} \varphi(m_i)
$$

A concrete proof of this property could be found here, which requires to use the Chinese remainder theorem.

When $n$ is prime number, according to the definition of prime, $\varphi(n) = n-1$. If $m$ and $n$ are different prime numbers, because $m$ and $n$ are relatively prime, we have

$$
\begin{aligned}
\varphi(mn) &= \varphi(m)\varphi(n) \\
&= (m-1)(n-1)
\end{aligned}
$$

Euler’s Theorem

If $m$ and $n$ are relatively prime (co-prime), then,

$$
m^{\varphi(n)} \equiv 1 \pmod n
$$

where $\varphi$ is the Euler’s totient function and $0 < \varphi(n) \leq n$ according to the definition of $\varphi$. This theorem is very famous, and there a couple of different proofs to it. I am not going to elaborate the proof in the blog post since it might be sophisticated. One of the proofs could be found here.

Modular Exponentiation Period

Suppose there is a smallest positive integer $r$, for $a$ and $N$ that are relatively prime and $a < N$, we have

$$
a^r \equiv 1 \pmod N
$$

For any non-negative integer $x \geq 0$, we define

$$
b_x = a^x ;\mathrm{mod}; N
$$

Note $0 \leq b_x < N$ and $b_r = 1$.

So we have

$$
\begin{align}
a^0 &\equiv b_0 \pmod N \\
a^1 &\equiv b_1 \pmod N \\
&\vdots \\
a^k &\equiv b_k \pmod N \\
&\vdots \\
\end{align}
$$

For any $k \geq r$, we have

$$
a^k \equiv a^r a^{k-r} \equiv b_r a^{k-r} \pmod N
$$

Because $b_r = 1$,

$$
b_r a^{k-r} \equiv a^{k-r} \equiv b_{k-r} \pmod N
$$

So we have

$$
a^k \equiv b_{k} \equiv b_{k-r} \pmod N
$$

Because $0 \leq b_x < N$, we have $b_{k} = b_{k-r}$. This means that the modular exponentiation remainder sequence $f_{a, N} = \{b_0, b_1, \cdots, b_k, \cdots \}$ is a periodic sequence whose period is some constant value $r$.

Because the Euler’s theorem, $\varphi(N)$ is definitely a period for the sequence $f_{a, N}$ because $a^{\varphi(N)} \equiv 1 \pmod N$. Therefore, such period must exists. In addition, based on the definition of $\varphi(N)$, $\varphi(N) \leq N$. This means the smallest period $r$ must be $r \leq N$.

Generating the Modular Exponentiation Remainder Sequence

To generate the the modular exponentiation remainder sequence $f_{a, N} = \{b_0, b_1, \cdots, b_k, \cdots \}$ in practice, we would not use the definition

$$
b_x = a^x ;\mathrm{mod}; N
$$

Because usually $a^x$ will be a too big number to compute.

Using the modular algorithmic - compatibility with multiplication, we could compute $f_{a, N}$ iteratively.

$$
\begin{align}
a^{x} \equiv (a^{x} ;\mathrm{mod}; N) \pmod N \\
a \equiv (a ;\mathrm{mod}; N) \pmod N \\
\end{align}
$$

Therefore,

$$
\begin{align}
a^{x + 1} \equiv a^{x} a \equiv \big( (a^{x} ;\mathrm{mod}; N) (a ;\mathrm{mod}; N) \big) \pmod N \\
\end{align}
$$

Because $a < N$, we have $a ;\mathrm{mod}; N = a$.

$$
a^{x + 1} \equiv \big( (a^{x} ;\mathrm{mod}; N) a \big) \pmod N \\
$$

Therefore, to compute $a^{x + 1} ;\mathrm{mod}; N$, we could use the result $a^{x} ;\mathrm{mod}; N$ from the previous iteration.

$$
a^{x + 1} ;\mathrm{mod}; N = \big( (a^{x} ;\mathrm{mod}; N) a \big) ;\mathrm{mod}; N\\
$$

Composite Number Factorization

Given an integer $a$ that is relatively prime to $N$, if somehow we know the period $r$ of the modular exponentiation remainder sequence $f_{a, N} = \{b_0, b_1, \cdots, b_k, \cdots \}$, where $b_x = a^x ;\mathrm{mod}; N$, we will be able to factorize a composite integer $N$.

Because of the fact that the period $r = \varphi(N)$, according to the Euler’s theorem, we have

$$
a^r \equiv 1 \pmod N
$$

So $N$ divides $a_r - 1$, i.e.,

$$
N | (a^r - 1)
$$

Because $a^r - 1 = (a^{\frac{r}{2}} + 1) (a^{\frac{r}{2}} - 1)$, if $N$ must have at least one factor that divides either $a^{\frac{r}{2}} + 1$ or $a^{\frac{r}{2}} - 1$ or both.

To find out such factor, we could find out the greatest common divisor $\text{gcd}((a^{\frac{r}{2}} + 1), N)$ and $\text{gcd}((a^{\frac{r}{2}} - 1), N)$ using the algorithm from the Euclidean algorithm family, which is usually fast even for extremely large numbers.

However, it is possible that we would get the trivial factors from $\text{gcd}((a^{\frac{r}{2}} + 1), N)$ and $\text{gcd}((a^{\frac{r}{2}} - 1), N)$, i.e., $1$ and $N$. To prevent $\text{gcd}((a^{\frac{r}{2}} + 1), N)$ and $\text{gcd}((a^{\frac{r}{2}} - 1), N)$ from producing $N$, we have to make sure that $a^{\frac{r}{2}} \not\equiv -1 \pmod N$ and $a^{\frac{r}{2}} \not\equiv 1 \pmod N$. Actually, we don’t have to check $a^{\frac{r}{2}} \not\equiv 1 \pmod N$ because we have claimed that $r$ is the smallest positive number such that $a^{r} \equiv 1 \pmod N$, this means that $a^{\frac{r}{2}} \not\equiv 1 \pmod N$ and $\text{gcd}((a^{\frac{r}{2}} - 1), N) \neq N$. Although $\text{gcd}((a^{\frac{r}{2}} - 1), N) \neq N$, we still don’t like to see $\text{gcd}((a^{\frac{r}{2}} - 1), N) = 1$ and $\text{gcd}((a^{\frac{r}{2}} + 1), N) = N$. But this has been prevented by making sure $a^{\frac{r}{2}} \not\equiv -1 \pmod N$. Therefore, before computing the $\text{gcd}((a^{\frac{r}{2}} + 1), N)$ and $\text{gcd}((a^{\frac{r}{2}} - 1), N)$, we have to make sure $a^{\frac{r}{2}} \not\equiv -1 \pmod N$.

To compute $\text{gcd}((a^{\frac{r}{2}} + 1), N)$ and $\text{gcd}((a^{\frac{r}{2}} - 1), N)$, we have to make sure $\frac{r}{2}$ is an integer, i.e., $r$ is even, otherwise the concept of the greatest common divisor might not hold. Given $a$ and $N$, it is possible to find out that $r$ odd. If this is the case, we could throw away the current $a$, and use a new $a$ that is relatively prime to $N$. Finding such $a$ should be simple and random, because for any $a$ we would first compute $\text{gcd}(a, N)$ to see if $\text{gcd}(a, N) = 1$. If $\text{gcd}(a, N) \neq 1$, we already found one of the factors for $N$ is $\text{gcd}(a, N)$ and we don’t have to do any more work.

Summary

To factorize a composite number, we just have to find an appropriate $a$ which is usually generated randomly, find out the period $r$ for sequence $f_{a, N}$, making sure $r$ is even and $a^{\frac{r}{2}} \not\equiv -1 \pmod N$, the factors could be computed using $\text{gcd}((a^{\frac{r}{2}} + 1), N)$ and $\text{gcd}((a^{\frac{r}{2}} - 1), N)$.

The only mysterious part is how to find out the period $r$ for sequence $f_{a, N}$. It turns out that generating the sequence $f_{a, N}$ until finding out the $r$ might be extremely slow if $N$ is extremely large, since the generation algorithm takes linear time with respect to the number of numbers in the sequence. Fortunately, the quantum Shor’s algorithm is able to generate this $r$ efficiently.

Caveat

One might have already notice that, even if some algorithms, such as the quantum Shor’s algorithm, is able to generate this $r$ efficiently, we might still have to compute $a^{\frac{r}{2}} ;\mathrm{mod}; N$ to make sure $a^{\frac{r}{2}} \not\equiv -1 \pmod N$. If we are using the the modular algorithmic - compatibility with multiplication to generate half of the sequence $f_{a, N}$ to find out $a^{\frac{r}{2}} ;\mathrm{mod}; N$. This will also be infeasible. In practice, we could just directly compute $\text{gcd}((a^{\frac{r}{2}} + 1), N)$ using Euclidean algorithms to see if this equals $N$ or not.

References

• RSA Algorithm
• Euclidean Algorithm