因數分解 = 尋找週期
分解一個大數——比如把 15 拆成 3 x 5——感覺像是一個搜尋問題，而對於巨大的數，普通電腦做起來極其緩慢，於是我們把密碼學建立在它的困難之上。Shor 的關鍵洞見是：你根本不必去搜尋。因數分解可以被重新表述為另一個問題：尋找一個重複序列的*週期*。而尋找週期，恰恰是量子電腦能做得很好的那類有結構的任務。
這裡是連接的橋梁。挑一個你想分解的數，叫它 N，再挑一個更小的數 a。現在看看 a^1, a^2, a^3, ... 這些數除以 N 之後所得餘數構成的序列。這個序列最終總會重複，一個循環的長度就叫作週期 r。數論裡一個了不起的事實是：一旦你知道了 r，再做一點普通的算術，就能把它變成 N 的因數。於是整個困難問題就收縮成一個問題：週期 r 是多少？
a^1 a^2 a^3 a^4 a^5 a^6 a^7 a^8 ...
mod N: 7 4 13 1 7 4 13 1 ...
\___________/\___________/
period r = 4 (it repeats)量子傅立葉轉換
怎麼找出一個週期呢？想想音樂 App 是怎麼辨識一個音的音高的：它拿到一段抖動的訊號，然後問*它由哪些頻率組成*。一個重複的模式會在它對應的頻率處呈現為一根尖銳的峰。量子傅立葉轉換（QFT）做的是同一件事，只不過作用在一組量子位元暫存器的狀態上：它把『每 r 步重複一次』轉換成一個狀態，對它測量時很可能落在與該週期相關的數值上。
它之所以強大，靠的是干涉，而不是並行猜測。這些量子位元被製備在一個疊加態裡，悄悄地把這個週期性模式同時編碼在許多數值上。隨後 QFT 讓錯誤的答案彼此抵消、讓正確的答案彼此增強——就像池塘裡的漣漪相遇，多數波峰被抹平，少數幾個疊加得更高。只有在這番精心的相消之後，你才去測量。
___ ___
|0>--| |--[ QFT ]--| |==> measure
|0>--| U | | |==> measure
|0>--| a | |QFT|==> measure
|0>--|___|--........-|___|==> (read out a value
related to the period r)把它們拼到一起
- 挑選 N（要分解的數）和一個比 N 小的隨機數 a。先做一次快速的經典檢查；有時你會走運，根本不用任何量子計算就找到一個因數。
- 在量子電腦上構建一個疊加態，並施加模冪運算這一步，使暫存器編碼出 a 的各次冪對 N 取模後那個重複的餘數模式。
- 施加 QFT，讓干涉把振幅集中到與週期 r 相關的那些結果上。
- 測量一次。你得到一個單一的數值；經典的後處理（一步連分數計算）把它變成週期 r 的一個候選值。
- 用 r 做普通的算術，算出 N 的因數。如果這一次嘗試失敗了——這有時會發生——就換一個新的 a 再來一遍。試幾次幾乎總能成功。
留意這個節奏：經典的準備、一個專注的量子子任務、經典的收尾，再加上一個重試迴圈。量子那一步是唯一沒有任何經典方法能高效完成的部分，而它之所以奏效，是因為週期是*QFT 能加以利用的結構*——並不是因為機器把每一種可能性都暴力試了一遍。
為什麼 RSA 處於危險之中
RSA 以及相關的公開金鑰系統建立在一個賭注上：分解一個大數（或者橢圓曲線密碼學背後那個密切相關的問題）實在太慢，沒有人能在一輩子之內做到。最好的經典分解方法所需的時間，幾乎是隨數的大小呈指數增長的，這正是為什麼今天人們認為夠長的金鑰是安全的。
Shor 打破了這個賭注。對於這個有結構的問題，它把近乎指數的經典開銷變成只隨數的大小多項式增長的開銷——這是專門針對因數分解的一種貨真價實的指數級加速。一台執行 Shor 的大型、可靠的量子電腦，原則上可以從公開金鑰反推出私密金鑰，這就是人們說它『攻破 RSA』的原因。應對之策是後量子密碼學：建立在某些數學難題（比如某些格問題）之上的新型經典演算法，而 Shor 的尋週期訣竅*破解不了*這些難題。
前提條件：你需要一台大型的容錯機器
以上這些都是理論。現實中的實際情況則要讓人清醒得多。今天的機器仍處在 NISQ 時代——充滿雜訊、只有不多的量子位元、相干時間也很短——它們犯的錯誤太多了，根本無法在一個具有密碼學意義的數上執行 Shor。一台真實量子電腦老老實實執行 Shor 所分解過的最大的數，都小得可憐，遠遠談不上接近一個真正的 RSA 金鑰。
擋路的不是聰明才智，而是可靠性。在一個 2048 位元的金鑰上執行 Shor，需要數以百萬計、行為規規矩矩的物理量子位元，因為你必須把脆弱的物理量子位元裹進糾錯之中，才能造出區區幾個穩定的邏輯量子位元。像表面碼這樣的方案，只有當物理錯誤率降到大約 1% 以下時才能達到容錯，而那時每一個邏輯量子位元又要耗費上千個物理量子位元。我們還遠沒到那一步——攻破 RSA 的時間估計要落在幾年到幾十年之後。