# Shor Algorithm (上)

Shor演算法是1994年由數學家Peter Shor提出的量子電腦演算法，用於處理傳統電腦沒辦法快速解決的質因數分解問題，具有潛在解密公鑰密碼系統（如RSA加密）的能力，最常被提到的例子就是他可以威脅到加密產業，比如說大家最常用到的HTTPS協議中就包括RSA加密技術，如果Shor演算法被實現了，那你的個資將會被竊取或竊聽。

---

## 歷史背景
傳統密碼學，如RSA加密，利用質因數很難在有效時間內分解的困難性，當數字很大時，使用經典電腦要分解其因數需要非常長的時間，因此無法在合理時間內破解密碼，也因此成為了常用的加密方式之一。
舉個例子:

然而當數值變得很大的時候，如圖X，此數值要做質因數分解目前需要花費2000年左右。

然而，Peter Shor在1994年提出了一種在量子電腦上運行的因數分解演算法，使得解決該問題在理論上變得可行，並引起了學界和產業的極大關注，尤其是在量子計算發展進展加速的情況下。

## Shor演算法解決的問題
我們可以將質因數分解問題視為多項式時間內求週期的問題，而Shor演算法就是要解決 **周期發現（period finding）** 的複雜問題，利用量子力學中的量子干涉以及量子疊加來實現量子傅立葉變換並確定函數的周期， **利用求解到的週期來分解大整數** ，而所需時間比古典的還要少很多，這項突破有可能徹底改變密碼學領域，而不僅僅是在理論上——研究人員已經使用Shor演算法透過量子電腦對小數進行質因數分解，在 **Shor Algorithm(下)** 中我們會詳細談到如何利用Shor演算法進行質因數方解 。

但暫時不要驚慌——要讓量子電腦強大到足以破解最複雜的加密方法，還有很長的路要走。然而，Shor 的演算法提醒我們，網路安全世界正在不斷發展，如果我們想保證資料和線上交易的安全，我們就必須領先一步。

>在閱讀這篇之前，你需要先了解 **QPE、QFT** 等章節內容。

## 古典電腦的因數分解方法
古典電腦在分解大數字的質因數時，主要依賴於一些傳統演算法。這些算法包括：

* 試除法（Trial Division）：通過測試每一個可能的質數因數，這是最直接的分解方法，但當數字較大時效率很低。

* 費馬分解法（Fermat's Factorization Method）：這種方法適用於接近於平方數的奇數，能夠將數字表示為兩個平方的差來快速找出質因數。

* Pollard’s rho算法：這是一種更有效的分解方法，適合較小到中等大小的整數，基於隨機方法來加快分解過程。

* 數字篩選法（Number Field Sieve, NFS）：NFS是目前最快的經典算法，尤其針對非常大的整數分解，然而計算時間仍隨著數字大小呈指數增長，並不適合直接用於破解現代的RSA加密。

古典算法的性能即便提升，也無法有效應對數千位的大整數，尤其是RSA加密的密鑰長度在2048位元以上時，用傳統方法分解會需要數百萬年的時間。這使得RSA成為當前網路加密的基礎，因為在經典計算的前提下，暴力破解幾乎不可能完成。

## Shor 演算法要解決的問題:週期尋找(Period Finding)

### 週期尋找(Period Finding)
首先我們必須了解週期函數$f(x)$:
$$f(x) = a^x\ mod N$$
a是我們的目標質因數，mod5的功能是除以五後的餘數，例如:
$$ 17\ mod5 = 2$$
而週期尋找的周期是指我們需要乘幾次a會得到和x=1時一樣的值，以上面範例為例:
$$
\begin{aligned}
17^1\ mod5 = 2 \\
17^2\ mod5 = 4 \\
17^3\ mod5 = 3 \\
17^4\ mod5 = 1 \\
17^5\ mod5 = 2
\end{aligned}
$$
這時候我們就可以說週期x=4。
在**Shor Algorithm (下)** 中，你將可以親自操做週期尋找週期。

### Quantum Period Finding
Shor 將會利用量子相位估計（Quantum Phase Estimation, QPE）來實現尋找週期的工作，在這裡我們標作U算符：

$$
U|y\rangle \equiv |ay\ mod N\rangle
$$

讓我們看看這是如何運作的。如果我們從狀態 $|1\rangle$ 開始，每次應用 $U$ 都會將寄存器的狀態乘上 $a \ (\text{mod} \ N)$，在重複 $r$ 次操作後，將會回到狀態 $|1\rangle$。例如，當 $a = 3$ 且 $N = 35$ 時：

$$
\begin{aligned}
U|1\rangle &= |3\rangle \\
U^2|1\rangle &= |9\rangle \\
U^3|1\rangle &= |27\rangle \\
&\vdots \\
U^{(r-1)}|1\rangle &= |12\rangle \\
U^r|1\rangle &= |1\rangle
\end{aligned}
$$

最後我們可以得到r=12，中間的餘數分別為[3、9、27、11、33、29、17、16、13、4、12、1]

---

#### $|u_0\rangle$ - 週期的疊加態
知道了週期以及其對應的狀態之後，我們可以假設這些狀態的疊加會是U的疊加態
的狀態組成。
$$
|u_0\rangle = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} |a^k \\mod N\rangle
$$

並且這個疊加態會是U的特徵態。也就是說U作用在疊加態上，不會改變內部

舉個例，我們假設 $a = 3$ and $N = 35$:

$$
\begin{aligned}
|u_0\rangle &= \frac{1}{\sqrt{12}} (|1\rangle + |3\rangle + |9\rangle + \cdots + |4\rangle + |12\rangle) \\
U|u_0\rangle &= \frac{1}{\sqrt{12}} (U|1\rangle + U|3\rangle + U|9\rangle + \cdots + U|4\rangle + U|12\rangle) \\
&= \frac{1}{\sqrt{12}} (|3\rangle + |9\rangle + |27\rangle + \cdots + |12\rangle + |1\rangle) \\
&= |u_0\rangle
\end{aligned}
$$

---

#### $|u_1\rangle$ - 相位疊加態
在 Shor 演算法中，**相位疊加態**對於找出數的周期非常重要。$|u_1\rangle$是一個包含相位的本徵態，用於在量子相位估計過程中提取周期性資訊。這個狀態的特殊之處在於，它為每一個基態 $|a^k \\mod N\rangle$ 引入了一個相位因子。具體來說，$|u_1\rangle$ 定義如下：

$$
|u_1\rangle = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{\frac{-2\pi i k}{r}} |a^k\\mod N\rangle
$$

其中：
- $r$ 是這個循環的周期。
- 每一項 $e^{\frac{-2\pi i k}{r}}$ 為不同的狀態提供了一個獨特的相位。

使得$|u_1\rangle$ 的本徵值為 $e^{\frac{2\pi i}{r}}$，即：

$$
U|u_1\rangle = e^{\frac{2\pi i}{r}} |u_1\rangle
$$

這個本徵態的特性是：在應用算符 $U$ 之後，疊加態 $|u_1\rangle$ 不會被打亂，只是會整體增加一個相位。這種相位變化能讓量子相位估計過程提取出周期 \( r \) 的信息，從而在 Shor 演算法中發揮關鍵作用。

讓我們重新檢視 $|u_1\rangle$ 的範例，以 $r = 12$ 為例：

$$
|u_1\rangle = \frac{1}{\sqrt{12}} \left( |1\rangle + e^{\frac{-2\pi i}{12}} |3\rangle + e^{\frac{-4\pi i}{12}} |9\rangle + \cdots + e^{\frac{-20\pi i}{12}} |4\rangle + e^{\frac{-22\pi i}{12}} |12\rangle \right)
$$

對這個態應用算符 $U$：

$$
U|u_1\rangle = \frac{1}{\sqrt{12}} \left( |3\rangle + e^{\frac{-2\pi i}{12}} |9\rangle + e^{\frac{-4\pi i}{12}} |27\rangle + \cdots + e^{\frac{-20\pi i}{12}} |12\rangle + e^{\frac{-22\pi i}{12}} |1\rangle \right)
$$

整理得到：

$$
U|u_1\rangle = e^{\frac{2\pi i}{12}} \cdot \frac{1}{\sqrt{12}} \left( |1\rangle + e^{\frac{-2\pi i}{12}} |3\rangle + e^{\frac{-4\pi i}{12}} |9\rangle + \cdots + e^{\frac{-20\pi i}{12}} |4\rangle + e^{\frac{-22\pi i}{12}} |12\rangle \right)
$$

因此，

$$
U|u_1\rangle = e^{\frac{2\pi i}{12}} |u_1\rangle
$$

---

#### $|u_s\rangle$ - 完整的考量相位變化
在$|u_1\rangle$ 的基礎上，我們可以引入一個整數 $s$ 來推廣這個概念，得到 $|u_s\rangle$。這個狀態允許我們在每個基態上施加不同程度的相位變化，使其更靈活地對應到不同的相位資訊。

$|u_s\rangle$ 的定義如下：

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

其中：
- $s$ 是一個整數，用來調整相位變化的速度。
- $e^{\frac{-2\pi i s k}{r}}$ 為每個基態提供一個與 $s$ 成正比的相位因子。

這樣的設計使得$|u_s\rangle$ 成為算符 $U$ 的另一個本徵態，並且本徵值為 $e^{\frac{2\pi i s}{r}}$：

$$
U|u_s\rangle = e^{\frac{2\pi i s}{r}} |u_s\rangle
$$

這表示，在 $U$ 作用之後，整個狀態只是被乘以一個相位因子 \( e^{\frac{2\pi i s}{r}} \)，其結構保持不變。通過調整 \( s \)，我們可以生成多個具有不同相位的本徵態，每個本徵態對應不同的本徵值。這樣的結構在量子相位估計中很有用，因為我們可以測量這些相位，進而提取不同的周期資訊。

## $|u_s\rangle$的範例

讓我們來看 $|u_s\rangle$ 的範例，假設 $r = 12$ 且 $s = 1$：

$$
|u_s\rangle = \frac{1}{\sqrt{12}} \left( |1\rangle + e^{\frac{-2\pi i s}{12}} |3\rangle + e^{\frac{-4\pi i s}{12}} |9\rangle + \cdots + e^{\frac{-20\pi i s}{12}} |4\rangle + e^{\frac{-22\pi i s}{12}} |12\rangle \right)
$$

應用算符 \( U \) 後，得到：

$$
U|u_s\rangle = \frac{1}{\sqrt{12}} \left( |3\rangle + e^{\frac{-2\pi i s}{12}} |9\rangle + e^{\frac{-4\pi i s}{12}} |27\rangle + \cdots + e^{\frac{-20\pi i s}{12}} |12\rangle + e^{\frac{-22\pi i s}{12}} |1\rangle \right)
$$

將這個結果表示為：

$$
U|u_s\rangle = e^{\frac{2\pi i s}{12}} \cdot \frac{1}{\sqrt{12}} \left( e^{\frac{-2\pi i s}{12}} |3\rangle + e^{\frac{-4\pi i s}{12}} |9\rangle + e^{\frac{-6\pi i s}{12}} |27\rangle + \cdots + e^{\frac{-22\pi i s}{12}} |1\rangle \right)
$$

因此，結果為：

$$
U|u_s\rangle = e^{\frac{2\pi i s}{12}} |u_s\rangle
$$

---

知道了怎麼得到$|u_s\rangle$後，我們可以開始利用QPE得到相位，在這裡我們簡單回顧QPE

量子相位估計（QPE）是一種用來測量量子態的相位的技術。假設我們有一個酉算符(Unitary Operator) $U$ 和它的一個本徵態 $|u_s\rangle$，並且這個本徵態對應的本徵值是：

$$
U|u_s\rangle=e^{2\pi i \frac{s}{r}} |u_s\rangle
$$

這裡的相位是 $2\pi \frac{s}{r}$，而 $\frac{s}{r}$ 是我們感興趣的相位值。

## Shor演算法結構

如同我們在上面說的