因式分解問題（factoring problem）就是：給定一個大數 N = p × q，找出質數 p 與 q。

廣泛使用的 RSA 演算法正是建立在「因式分解一個數很困難」這個事實上。因式分解問題的困難性，正是 RSA 加密與簽章方案安全的原因。

一點基礎數學#

質數是除了自己與 1 之外不被任何其他數整除的數。3、7、11 是質數；4 = 2×2、6 = 2×3、12 = 2×2×3 不是。

數論的一個基本定理說：任何整數都能被唯一地寫成質數的乘積，這個表示法稱為該數的因式分解：

123456  = 2⁶ × 3 × 643
1234567 = 127 × 9721

那我們怎麼知道某個因式分解裡只含質數、或某個數是質數？答案來自多項式時間的質數測試演算法，它讓我們能有效率地測試一個數是否為質數。

但從一個數走到它的質因數，則完全是另一回事。

實務上分解大數#

天真做法#

最基本的做法是把 N 除以所有比它小的數，直到找到能整除 N 的數 x，接著試 x + 1，依此類推。

複雜度分析：N 的位元長度是 n = log₂ N，也就是 N = 2ⁿ。由於所有小於 N/2 的數都是可能因數的合理猜測，大約有 N/2 = 2ⁿ/2 個值要試。

天真因式分解演算法的複雜度因此是 O(2ⁿ)（忽略 O() 記法中的 1/2 係數）。

聰明一點#

我們不需要測試所有小於 N/2 的數，而只需要測試質數，而且可以只從小於 √N 的開始。

為什麼？若 N 不是質數，它必定至少有一個小於 √N 的因數。

因為若 N 的兩個因數 p 與 q 都大於 √N，它們的乘積就會大於 √N × √N = N，這不可能。

例如 N = 100，p 與 q 不可能都大於 10，否則乘積會大於 100。

質數定理指出小於 N 的質數大約有 N / log N 個，因此小於 √N 的質數約有 √N / log √N 個，也就是約 2^(n/2) / n 個可能質因數。

複雜度因此是 O(2^(n/2) / n)。這比測試所有質數快，但仍然慢得令人痛苦——對一個 256 位元的數而言是 2^120 量級的運算，計算量相當不切實際。

最快的演算法：GNFS#

最快的因式分解演算法是一般數域篩法（GNFS，general number field sieve）。它的複雜度粗略估計為：

exp(1.91 × n^(1/3) × (log n)^(2/3))

然而要對給定的數字大小取得 GNFS 的準確複雜度估計很困難，因此我們必須依賴啟發式的複雜度估計。

各長度的估計成本#

這些數值應該保留一點懷疑，研究者對這些估計並不總是意見一致。

實際的分解記錄#

• 2005 年：一組研究者用 80 顆處理器的叢集運算了約 18 個月（總計相當於單處理器 75 年的計算量），分解了一個 663 位元（200 個十進位數字）的數。
• 2009 年：另一組研究者用數百顆處理器花了約兩年（總計相當於單處理器約 2,000 年），分解了一個 768 位元（232 個十進位數字）的數。

學術研究者實際分解過的數，比真實應用中所用的（至少 1024 位元，往往超過 2048 位元）更短。

本書寫作時，尚無人回報分解出 1024 位元的數，但許多人推測 NSA 這類資金充裕的組織辦得到。

結論：1024 位元 RSA 應被視為不安全。RSA 應該搭配至少 2048 位元的值使用，最好是 4096 位元以確保更高的安全性。

因式分解是 NP-complete 嗎#

我們不知道如何有效率地分解大數，這暗示因式分解問題不屬於 P。

但因式分解顯然在 NP 中：給定一個因式分解，我們可以驗證所有因數都是質數（靠前述的質數測試演算法），並驗證它們相乘確實得到預期的數。例如要檢查 3 × 5 是 15 的因式分解，就檢查 3 與 5 都是質數、且 3 乘 5 等於 15。

那麼因式分解是否與 NP 中最難的問題一樣難？劇透：大概不是。

沒有數學證明說因式分解不是 NP-complete，但我們有幾條軟性證據：

• 解的數量：所有已知的 NP-complete 問題可以有一個解、也可以有多個解或完全沒有解。相對地，因式分解永遠恰好有一個解。
• 數學結構：因式分解具有讓 GNFS 演算法能顯著勝過天真演算法的數學結構，而 NP-complete 問題沒有這種結構。
• 量子電腦：若我們有量子電腦，因式分解就會變得容易——不是因為它跑演算法比較快，而是因為它能跑一個專門用於分解大數的量子演算法。但量子電腦還不存在，或許永遠不會存在。而且量子電腦對付 NP-complete 問題毫無用處，它不會比古典電腦更快（見第 14 章）。

因式分解在理論上或許比 NP-complete 稍微容易，但就密碼學而言它已經夠難了，而且比 NP-complete 問題更可靠。

事實上，在因式分解問題之上建構密碼系統比在 NP-complete 問題之上更容易——因為對基於 NP-complete 問題的密碼系統，我們很難確知破解它到底有多難，也就是你能得到幾位元的安全性。

因式分解問題只是密碼學中被當作困難性假設（hardness assumption）的數個問題之一。這個假設用於證明「破解某密碼系統的安全性，至少與解決該問題一樣難」。

另一個被當作困難性假設的是離散對數問題（DLP），它其實是一整個問題家族。