乘大數的代價
用你在學校學的方式把兩個 n 位數相乘——把一個數的每一位乘上另一個數的每一位、再把錯位的各列加起來——要花 Theta(n^2) 次單位數運算。對於 CPU 一條指令就能處理的小數，這代價是看不見的；但密碼學經常要乘上千位的數，那時 n^2 就開始咬人了。前一篇導覽把 快速模冪 建立在乘法之上；這裡我們追問更深的問題：單一次乘法本身能有多快。
n^2 這道牆上的第一道裂縫，來自 卡拉楚巴乘法，這是你在遞迴那一輪遇過的一個分治法想法。把每個數切成高半與低半；天真的切法需要四次半大小的乘法，給出 T(n) = 4 T(n/2) + O(n)，主定理把它解回 Theta(n^2)——毫無收穫。卡拉楚巴的巧思是一個代數恆等式，只用「三」次半大小的乘法就算出同一個乘積，把遞迴式變成 T(n) = 3 T(n/2) + O(n)、執行時間變成 Theta(n^(log2 3))，約 Theta(n^1.585)。這是貨真價實的勝利，也乾淨地提醒我們：彎折遞迴式的，是更少的子問題，而不只是更小的子問題。
乘法其實就是摺積
為了抵達最快的方法，我們改變看待一個數的方式。把一個數的各位數寫成一個多項式的係數：十進位的 1234 就是多項式 A(x) = 4 + 3x + 2x^2 + 1x^3 在 x = 10 處的值。於是把兩個數相乘，就是把兩個多項式相乘、最後再代入底數求值（並按需進位）。而多項式相乘，正是那個叫做 摺積 的運算：乘積中 x^k 的係數，是所有滿足 i + j = k 的 a_i * b_j 之和。直接做，那個雙重和又是 Theta(n^2)——一個多項式的每個係數，都得碰上另一個多項式的每個係數。
這裡是解開一切的樞紐。一個次數低於 n 的多項式，由它在 n 個相異點的值來釘定，和由它的 n 個係數來釘定一樣忠實——這是描述同一個對象的兩種方式。而在「值的形式」下，乘法是平凡的：若你知道 A 與 B 在同一批點上的值，乘積 C = A*B 在每個點上的值，就只是單一個數 A(點) * B(點)。所以把兩個以「在 2n 個點上的值」給定的多項式相乘，只花 O(n) 次乘法，而非 O(n^2)。當然，難處在於要廉價地進入和離開值的形式。那個轉換，就是整場遊戲。
FFT：以 O(n log n) 求值
天真地把一個 (n-1) 次多項式在 n 個任意點求值要花 O(n^2)。快速傅立葉轉換 之所以致勝，在於它以外科手術般的講究來選點：n 個複數 單位根，也就是均勻分布在單位圓上、方程式 x^n = 1 的那些解。這些點有一種神奇的自相似結構。把 A(x) 拆成偶數索引與奇數索引的係數，A(x) = E(x^2) + x*O(x^2)。因為把 n 個單位根平方，恰好得到半大小問題的 n/2 個單位根，所以把 A 在全部 n 個點求值，就化約成把兩個半大小的多項式在 n/2 個點求值、再以 O(n) 合併——這正是分治遞迴式的形狀。
T(n) = 2 T(n/2) + O(n) ==> T(n) = O(n log n) (master theorem, case 2)
回程——從值還原係數，稱為逆 FFT——幾乎是同一套計算，只是把單位根取共軛、最後再除以 n，所以它也是 O(n log n)。現在把完整的乘法組裝起來：對兩個多項式各做 FFT 化成值的形式，以 O(n) 逐點相乘那些值，再做逆 FFT 還原成係數。總計是 O(n log n) + O(n) + O(n log n) = O(n log n)，對於夠大的輸入，決定性地勝過 Theta(n^2) 與卡拉楚巴的 Theta(n^1.585)。
不靠因數分解來測質數
現在輪到本篇的第二位主角。給定一個有數百位的數 n，它是質數嗎？顯而易見的方法——用每個直到 sqrt(n) 的整數去試除——需要約 sqrt(n) 次除法，這在位數上是指數級的，對密碼學等級的大小完全沒救。我們需要一個成本隨「位數」而非隨 n 本身成長的 質數測試。令人驚訝的事實是：我們能比做因數分解快得多地判定質數性——證明 n 是合數，從來不需要拿出一個因數。
基礎是費馬小定理：若 n 是質數，則對每個不被 n 整除的底數 a，a^(n-1) 模 n 同餘於 1。把它讀成一個測試。挑一個底數 a，用 快速模冪 以 O(log n) 次乘法算出 a^(n-1) mod n，再檢查結果是不是 1。若它「不是」1，定理的逆否命題就發動了：n 必定是合數，而 a 是這個事實的一個 見證。這和 蒙地卡羅 指紋檢查是同一套邏輯——一個便宜的必要條件，當它被違反時，給出一個確定的否決。
但逆命題不成立，而誠實要求我們說清楚是怎麼不成立的。有些合數在某個特定底數下通過費馬檢查——而且有一類稀少又討厭、叫做卡邁克爾數的數，對「每個」與 n 互質的底數都通過它，所以無論怎麼挑底數，純粹的費馬測試都揭不穿它們。米勒-拉賓正是補上這個漏洞，靠的是檢查一個更強的條件。
米勒-拉賓，以及它的答案真正的意思
米勒-拉賓用一個關於平方根的事實把測試磨利。在一個質數的模下，1 的平方根只有 +1 與 -1；一個合數模可能有額外的「流氓」平方根，而找到一個，就是合數性的鐵證。把 n - 1 寫成 d * 2^s，其中 d 是奇數。那麼測試不直接跳到 a^(n-1)，而是算出 a^d、再反覆平方它，盯著序列 a^d, a^(2d), a^(4d), ..., a^(n-1) 看有沒有出現一個禁忌的樣式——某個值變成了 1，但它前一步卻不是 -1。
- 把 2 提出來：把 n - 1 寫成 d * 2^s（d 為奇數），再在 2 到 n - 2 的範圍內隨機挑一個底數 a。
- 用快速模冪算出 x = a^d mod n。若 x 是 1 或 n - 1，這個底數回報「可能是質數」，這一輪到此為止。
- 否則就把 x 平方至多 s - 1 次。若它在過程中變成 n - 1，這個底數回報「可能是質數」。若它在還沒碰到 n - 1 之前就到達了 1，我們就找到了一個流氓平方根：a 是見證，而 n「必定」是合數。
- 用數個獨立的隨機底數重複。若每個底數都回報「可能是質數」，就宣告 n 大概是質數；任何一處出現一個見證，就宣告它是合數。
要不對稱地讀這兩種結果，因為它們本就不對稱。「合數」的判決永遠正確：一個貨真價實的見證就是一個數學證明，不涉任何運氣。帶有風險的是「可能是質數」的判決——一個合數可能騙過單一個隨機底數，但米勒-拉賓背後的定理保證：對任何合數（含卡邁克爾數），1 到 n-1 之間至少有四分之三的底數是見證。所以一個合數在一輪隨機中存活的機率至多 1/4，在 k 個獨立輪次中存活的機率至多 (1/4)^k。跑 30 輪，把一個合數誤判為質數的機會就低於 4^(-30)，比硬體故障的機率還小。
這是一個帶單側誤差的 蒙地卡羅演算法：時間上快速且確定，但它的答案只可能在「質數」的方向上出錯，而且只以一個你想壓多低就壓多低、只需多花輪次的機率出錯。每一輪是 O(log n) 次模乘法，所以連數百位的數也是一眨眼就驗完——這正是各種系統生成 RSA 所倚賴的大質數的方式。值得加一句但書：一個確定性的多項式時間測試（AKS）確實存在，這敲定了質數性屬於 P 類，但米勒-拉賓的速度讓它在所有真正要緊的地方仍是務實的主力。