動機
數論與密碼學中的許多算法都需要大質數,例如具有數百甚至數千個二進制數字的質數。最直接的質數檢驗是試除法:逐一嘗試所有不超過 n \sqrt{n} n 的可能因數。其成本大致與 n \sqrt{n} n 成正比,而輸入的大小是 n n n 的位元數,約為 log 2 n \log_2 n log 2 n 。因此試除法所需時間相對於輸入長度是指數級的。對於一個 1024 位元的數,n \sqrt{n} n 約為 2 512 2^{512} 2 512 ,如此規模的計算是不可行的。
費馬(Fermat)小定理提供了一個快速的必要條件:若 n n n 為質數且 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ,則 a n − 1 ≡ 1 ( m o d n ) a^{n-1}\equiv 1 \pmod n a n − 1 ≡ 1 ( mod n ) 。此條件可藉模冪運算在 log n \log n log n 的多項式時間內驗證。然而,該條件並非充分條件,而且有些合數對於與其互質的每個底都滿足它。本筆記研究費馬條件的一個加強形式,即強概質數條件 ,以及建基於其上的隨機化檢驗,即米勒–拉賓檢驗 (Miller–Rabin test)。
此加強形式利用了費馬檢驗所忽略的一項關於質數的事實:在質數模下,1 1 1 的平方根只有 1 1 1 與 − 1 -1 − 1 。米勒–拉賓檢驗並不止於 a n − 1 a^{n-1} a n − 1 ,而是考察通向 a n − 1 a^{n-1} a n − 1 的一連串逐次平方根,並檢查這條鏈的行為是否符合質數模下必然出現的行為。
本章證明質數輸入必定通過檢驗;配套章節則證明合數的錯誤界:
若 n n n 為質數,則 { 1 , … , n − 1 } \{1,\dots,n-1\} { 1 , … , n − 1 } 中每個底都通過。
若 n n n 為奇合數,則 { 1 , 2 , … , n − 1 } \{1,2,\dots,n-1\} { 1 , 2 , … , n − 1 } 中至多一半的底通過。
配合獨立隨機地選取底,這些結果給出一個有清晰保證的檢驗:合數判定必定正確;對任何固定的合數輸入,經 k k k 輪後得出概質數判定的概率小於 2 − k 2^{-k} 2 − k 。我們亦會小心說明此保證不意味著甚麼。
全文假設讀者熟悉中國剩餘定理(CRT)、費馬小定理、平方乘法求冪、群同態與拉格朗日(Lagrange)定理,以及關於質數冪的基本整除性。
由費馬檢驗到 1 的平方根
費馬說謊者
設 n ≥ 3 n \ge 3 n ≥ 3 為奇數。若 n n n 為合數而仍有 a n − 1 ≡ 1 ( m o d n ) a^{n-1}\equiv 1 \pmod n a n − 1 ≡ 1 ( mod n ) ,則稱滿足 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 的整數 a a a 為 n n n 的費馬說謊者 (Fermat liar)。費馬說謊者就是令費馬檢驗給出錯誤印象的底。
例題 8.1.2
(為何 n = 561 n=561 n = 561 的每個單位都能欺騙費馬檢驗)
有些合數在其單位中只有 費馬說謊者。一個標準例子是 n = 561 = 3 ⋅ 11 ⋅ 17 n = 561 = 3\cdot 11\cdot 17 n = 561 = 3 ⋅ 11 ⋅ 17 。我們可以直接驗證。設 gcd ( a , 561 ) = 1 \gcd(a,561)=1 g cd( a , 561 ) = 1 ,則:
模 3 3 3 :a 2 ≡ 1 a^2\equiv 1 a 2 ≡ 1 ,且 2 ∣ 560 2 \mid 560 2 ∣ 560 ,故 a 560 ≡ 1 ( m o d 3 ) a^{560}\equiv 1 \pmod 3 a 560 ≡ 1 ( mod 3 ) ;
模 11 11 11 :a 10 ≡ 1 a^{10}\equiv 1 a 10 ≡ 1 ,且 10 ∣ 560 10\mid 560 10 ∣ 560 ,故 a 560 ≡ 1 ( m o d 11 ) a^{560}\equiv 1 \pmod{11} a 560 ≡ 1 ( mod 11 ) ;
模 17 17 17 :a 16 ≡ 1 a^{16}\equiv 1 a 16 ≡ 1 ,且 16 ∣ 560 16 \mid 560 16 ∣ 560 (因為 560 = 16 ⋅ 35 560 = 16\cdot 35 560 = 16 ⋅ 35 ),故 a 560 ≡ 1 ( m o d 17 ) a^{560}\equiv 1\pmod{17} a 560 ≡ 1 ( mod 17 ) 。
由 CRT,對每個單位 a a a 都有 a 560 ≡ 1 ( m o d 561 ) a^{560}\equiv 1 \pmod{561} a 560 ≡ 1 ( mod 561 ) 。具有此性質的合數稱為卡邁克爾數 (Carmichael number)。對這樣的 n n n ,費馬檢驗只有在碰上與 n n n 有公因數的底時才能偵測到合數性。抽到非單位的概率至多為不同質因數上的和 ∑ p ∣ n 1 / p \sum\limits_{p\mid n}1/p p ∣ n ∑ 1/ p ;質因數的個數也有影響。
因此,我們需要從底 a a a 取得比單一數值 a n − 1 a^{n-1} a n − 1 更多的資訊。
1 的平方根
額外的資訊來自以下引理。
設 p p p 為奇質數,x x x 為滿足 x 2 ≡ 1 ( m o d p ) x^2\equiv 1 \pmod p x 2 ≡ 1 ( mod p ) 的整數。則 x ≡ 1 x\equiv 1 x ≡ 1 或 x ≡ − 1 ( m o d p ) x \equiv -1 \pmod p x ≡ − 1 ( mod p ) 。
我們有 p ∣ x 2 − 1 = ( x − 1 ) ( x + 1 ) p \mid x^2-1 = (x-1)(x+1) p ∣ x 2 − 1 = ( x − 1 ) ( x + 1 ) 。由於 p p p 為質數,p ∣ x − 1 p\mid x-1 p ∣ x − 1 或 p ∣ x + 1 p \mid x+1 p ∣ x + 1 。
此證明只用到 p p p 的一個性質:若質數整除一個乘積,則它整除其中一個因子。對於合數模,這個性質不成立,而引理的失效便會揭示 n n n 的一個因數。
引理 8.1.4
(1 1 1 的非平凡平方根揭示一個因數)
設 n ≥ 3 n\ge 3 n ≥ 3 ,且 x 2 ≡ 1 ( m o d n ) x^2\equiv 1 \pmod n x 2 ≡ 1 ( mod n ) 但 x ≢ ± 1 ( m o d n ) x\not\equiv \pm 1 \pmod n x ≡ ± 1 ( mod n ) 。則 gcd ( x − 1 , n ) \gcd(x-1,n) g cd( x − 1 , n ) 與 gcd ( x + 1 , n ) \gcd(x+1,n) g cd( x + 1 , n ) 都是 n n n 的真因數,即兩者都嚴格介乎 1 1 1 與 n n n 之間。
由於 n ∣ ( x − 1 ) ( x + 1 ) n \mid (x-1)(x+1) n ∣ ( x − 1 ) ( x + 1 ) 且 n ∤ x − 1 n\nmid x-1 n ∤ x − 1 ,故 gcd ( x − 1 , n ) ≠ n \gcd(x-1,n)\neq n g cd( x − 1 , n ) = n 。若 gcd ( x − 1 , n ) = 1 \gcd(x-1,n)=1 g cd( x − 1 , n ) = 1 ,則由 n ∣ ( x − 1 ) ( x + 1 ) n \mid (x-1)(x+1) n ∣ ( x − 1 ) ( x + 1 ) 可得 n ∣ x + 1 n\mid x+1 n ∣ x + 1 ,這與 x ≢ − 1 x\not\equiv -1 x ≡ − 1 矛盾。因此 1 < gcd ( x − 1 , n ) < n 1 < \gcd(x-1,n) < n 1 < g cd( x − 1 , n ) < n 。把 x − 1 x-1 x − 1 與 x + 1 x+1 x + 1 的角色對調,同樣的論證給出 1 < gcd ( x + 1 , n ) < n 1<\gcd(x+1,n)<n 1 < g cd( x + 1 , n ) < n 。
我們稱這樣的 x x x 為模 n n n 下 1 1 1 的非平凡平方根 。由質數模下 1 1 1 的平方根的引理,在質數模下不存在這樣的根。而在至少有兩個不同質因數的奇合數模下,則必定存在,如下文關於 1 1 1 的平方根的練習所示。
定義
設 n ≥ 3 n\ge 3 n ≥ 3 為奇數。則 n − 1 n-1 n − 1 為偶數,因此可唯一地寫成
n − 1 = 2 s d , s ≥ 1 , d 為奇數 . n - 1 = 2^s d, \qquad s \ge 1,\quad d \text{ 為奇數}. n − 1 = 2 s d , s ≥ 1 , d 為奇數 .
對於整數 a a a ,a a a 模 n n n 的強序列 為
x r ≡ a 2 r d ( m o d n ) , r = 0 , 1 , … , s . x_r \equiv a^{2^r d} \pmod n, \qquad r = 0,1,\dots,s. x r ≡ a 2 r d ( mod n ) , r = 0 , 1 , … , s . 每一項都是前一項的平方:x r + 1 ≡ x r 2 x_{r+1}\equiv x_r^2 x r + 1 ≡ x r 2 。最後一項是費馬值 x s ≡ a n − 1 x_s \equiv a^{n-1} x s ≡ a n − 1 。我們把指標 r r r 稱為階段 。
若 n n n 為質數且 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ,則序列以 x s ≡ 1 x_s \equiv 1 x s ≡ 1 結束。考慮數值 1 1 1 首次出現的階段。它若不是出現在第 0 0 0 階段,就是前一個數值平方後得 1 1 1 而自身不是 1 1 1 ,於是由質數模下 1 1 1 的平方根的引理,前一個數值為 − 1 -1 − 1 。這便引出以下定義。
設 n ≥ 3 n\ge 3 n ≥ 3 為奇數,n − 1 = 2 s d n-1=2^s d n − 1 = 2 s d ,其中 d d d 為奇數,底數 a ∈ { 1 , … , n − 1 } a\in\{1,\dots,n-1\} a ∈ { 1 , … , n − 1 } 。若 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 且
a d ≡ 1 ( m o d n ) 或 a 2 r d ≡ − 1 ( m o d n ) 對某個滿足 0 ≤ r ≤ s − 1 的 r , a^{d}\equiv 1 \pmod n \qquad\text{或}\qquad a^{2^r d}\equiv -1 \pmod n \ \text{ 對某個滿足 } 0\le r\le s-1 \text{ 的 } r, a d ≡ 1 ( mod n ) 或 a 2 r d ≡ − 1 ( mod n ) 對某個滿足 0 ≤ r ≤ s − 1 的 r , 則稱整數 a a a 使 n n n 成為以 a a a 為底的強概質數 。此時我們亦稱 a a a 通過 檢驗。若 n n n 為合數而 a a a 通過,則 a a a 為 n n n 的強說謊者 。若 a a a 不通過,則 a a a 為 n n n 合數性的強見證者 。
此定義有三點值得說明。
檢查哪些階段。 在第 0 0 0 階段,我們接受數值 1 1 1 或 − 1 -1 − 1 。在第 1 , … , s − 1 1,\dots,s-1 1 , … , s − 1 階段,我們只接受數值 − 1 -1 − 1 。在第 r ≥ 1 r\ge 1 r ≥ 1 階段出現的數值 1 1 1 本身並不足以支持接受,因為重要的是數值 1 1 1 是如何得到的。若 1 1 1 在階段 r r r 首次出現且本輪尚未停止,前一項既不是 1 1 1 也不是 − 1 -1 − 1 ,所以它是 1 1 1 的非平凡平方根,n n n 是合數。若 1 1 1 已在更早階段出現,本輪則早已接受或拒絕。
第 s s s 階段永遠不是接受階段。 第 s s s 階段出現 − 1 -1 − 1 意味著 a n − 1 ≡ − 1 a^{n-1}\equiv -1 a n − 1 ≡ − 1 。對於質數 n n n ,這與費馬定理不相容,因為 n ≥ 3 n\ge 3 n ≥ 3 時 − 1 ≢ 1 -1\not\equiv 1 − 1 ≡ 1 。所以定義只取 r ≤ s − 1 r\le s-1 r ≤ s − 1 。
此條件只與 a a a 模 n n n 的值有關。 因此我們把底視為剩餘類,並從 { 1 , 2 , … , n − 1 } \{1,2,\dots,n-1\} { 1 , 2 , … , n − 1 } 中選取。剩餘類 0 0 0 被排除,因為它永不與 n n n 互質。
底 1 1 1 與 n − 1 n-1 n − 1 必定通過:1 d = 1 1^d = 1 1 d = 1 ,而由於 d d d 為奇數,( n − 1 ) d ≡ ( − 1 ) d = − 1 (n-1)^d\equiv(-1)^d = -1 ( n − 1 ) d ≡ ( − 1 ) d = − 1 。它們是不帶任何資訊的通過底。配套章節在這些底存在的情況下仍證明了一個錯誤界。
快速檢查
(證明:對 n = 2047 = 23 ⋅ 89 n=2047=23\cdot89 n = 2047 = 23 ⋅ 89 ,底 2 2 2 通過,所以 2 2 2 是 2047 2047 2047 的強說謊者。)
留意 2 11 = 2048 2^{11}=2048 2 11 = 2048 。
解答 · 答案 此時 n − 1 = 2046 = 2 ⋅ 1023 n-1=2046=2\cdot1023 n − 1 = 2046 = 2 ⋅ 1023 ,故 s = 1 s=1 s = 1 ,d = 1023 = 11 ⋅ 93 d=1023=11\cdot93 d = 1023 = 11 ⋅ 93 。由於 2 11 = 2048 ≡ 1 ( m o d 2047 ) 2^{11}=2048\equiv1\pmod{2047} 2 11 = 2048 ≡ 1 ( mod 2047 ) ,得 2 1023 = ( 2 11 ) 93 ≡ 1 2^{1023}=(2^{11})^{93}\equiv1 2 1023 = ( 2 11 ) 93 ≡ 1 。因此 a d ≡ 1 a^d\equiv1 a d ≡ 1 ,儘管 2047 2047 2047 是合數,2 2 2 仍在第 0 0 0 階段通過。
算法
偽代碼
此檢驗接受整數 n ≥ 2 n\ge 2 n ≥ 2 與輪數 k ≥ 1 k\ge 1 k ≥ 1 ,並返回三種判定之一。
PRIME 只在 n = 2 n=2 n = 2 時返回,且為確定結果。
COMPOSITE 必定正確。
PROBABLE-PRIME 是我們須分析其可靠性的判定。
MILLER-RABIN(n, k): # n ≥ 2, k ≥ 1
1 if n = 2: return PRIME
2 if n is even: return COMPOSITE # n ≥ 4 為偶數,故 2 是真因數
3 d ← n − 1; s ← 0
4 while d is even:
5 d ← d / 2; s ← s + 1
# 此時 n − 1 = 2^s · d,其中 d 為奇數且 s ≥ 1
6 repeat k times:
7 draw a uniformly at random from 1, 2, ..., n − 1,
independently of all previous draws
8 if STRONG-ROUND(n, s, d, a) = FAIL: return COMPOSITE
9 return PROBABLE-PRIME
STRONG-ROUND(n, s, d, a):
1 if gcd(a, n) > 1: return FAIL # gcd(a, n) 是 n 的真因數
2 x ← a^d mod n # 平方乘法;此即 x_0
3 if x = 1 or x = n − 1: return PASS # 第 0 階段
4 for r ← 1 to s − 1:
5 y ← x^2 mod n # y = x_r
6 if y = n − 1: return PASS # 第 r 階段
7 if y = 1: return FAIL # x 是 1 的平方根,且不是 ±1
8 x ← y
9 return FAIL
若干細節值得說明。
n = 2 n=2 n = 2 與偶數 n n n 的情形。 分解 n − 1 = 2 s d n-1=2^s d n − 1 = 2 s d (s ≥ 1 s\ge 1 s ≥ 1 )要求 n n n 為奇數。對於偶數 n n n ,n − 1 n-1 n − 1 為奇數,故 s = 0 s=0 s = 0 ,強條件沒有任何可接受 − 1 -1 − 1 的階段。定義原本並非為此情形而設,我們直接處理:2 2 2 是質數,而每個偶數 n ≥ 4 n\ge 4 n ≥ 4 都是合數,因為 2 2 2 是其真因數。
n = 3 n=3 n = 3 的情形。 此時 n − 1 = 2 n-1=2 n − 1 = 2 ,故 s = 1 s=1 s = 1 ,d = 1 d=1 d = 1 。該輪第 4–8 行的迴圈中 r r r 由 1 1 1 到 0 0 0 ,因此完全不會執行。底為 1 1 1 與 2 2 2 ,兩者都在第 0 0 0 階段通過。這是正確的,因為 3 3 3 是質數。
選取底。 從 { 1 , … , n − 1 } \{1,\dots,n-1\} { 1 , … , n − 1 } 中均勻選取 a a a 的一種方法是拒絕抽樣:抽取 β \beta β 個全新的隨機位元,其中 β \beta β 為 n n n 的位元長度,把它們解讀為整數 t t t ,0 ≤ t ≤ 2 β − 1 0\le t\le 2^\beta-1 0 ≤ t ≤ 2 β − 1 。若 1 ≤ t ≤ n − 1 1\le t\le n-1 1 ≤ t ≤ n − 1 則接受 a = t a=t a = t ,否則重新抽取。由於奇數 n ≥ 3 n\ge3 n ≥ 3 滿足 n − 1 ≥ 2 β − 1 n-1\ge2^{\beta-1} n − 1 ≥ 2 β − 1 ,每次嘗試成功的概率至少為 1 / 2 1/2 1/2 ,預期嘗試次數至多為 2 2 2 。對分析而言,重要的是底在 { 1 , … , n − 1 } \{1,\dots,n-1\} { 1 , … , n − 1 } 上嚴格均勻,且每一輪都使用新的隨機位元。
gcd 步驟。 該輪的第 1 行對正確性並非必要,因為與 n n n 不互質的底,其任何冪都不可能模 n n n 同餘於 1 1 1 或 − 1 -1 − 1 。加入它是因為當它觸發時,能以低成本產生 n n n 的一個明確因數。它並不是令檢驗成為「強」檢驗的原因。抽到非單位的概率至多為不同質因數上的和 ∑ p ∣ n 1 / p \sum\limits_{p\mid n}1/p p ∣ n ∑ 1/ p 。當此和很小時,偵測合數性主要依靠強條件。
該輪恰好計算強條件
該輪的第 7 行會提前停止,因此我們應當驗證該輪所判定的恰是強條件。
設 n ≥ 3 n\ge 3 n ≥ 3 為奇數,n − 1 = 2 s d n-1=2^sd n − 1 = 2 s d (d d d 為奇數),且 a ∈ { 1 , … , n − 1 } a\in\{1,\dots,n-1\} a ∈ { 1 , … , n − 1 } 。則 STRONG-ROUND( n , s , d , a ) (n,s,d,a) ( n , s , d , a ) 返回 PASS,當且僅當 a a a 使 n n n 成為以 a a a 為底的強概質數。
若 gcd ( a , n ) > 1 \gcd(a,n)>1 g cd( a , n ) > 1 ,該輪返回 FAIL,而定義中的條件同樣不成立。因此假設 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 。
第 2 行令 x = x 0 x = x_0 x = x 0 。若 x 0 ∈ { 1 , n − 1 } x_0\in\{1,n-1\} x 0 ∈ { 1 , n − 1 } ,則該輪與定義都接受。
否則,我們證明以下迴圈不變式:在第 r r r 次迭代開始時,變量 x x x 的值為 x r − 1 x_{r-1} x r − 1 ,且 x 0 , … , x r − 1 x_0,\dots,x_{r-1} x 0 , … , x r − 1 都不同餘於 1 1 1 或 − 1 -1 − 1 。 由上一段,此不變式在 r = 1 r=1 r = 1 時成立。在第 r r r 次迭代中,變量 y y y 成為 x r x_r x r ,並有三種情形。
若 x r ≡ − 1 x_r\equiv -1 x r ≡ − 1 ,該輪返回 PASS,而定義在階段 r ≤ s − 1 r\le s-1 r ≤ s − 1 接受。
若 x r ≡ 1 x_r\equiv 1 x r ≡ 1 ,該輪返回 FAIL。我們驗證定義同樣拒絕。我們知道 x 0 ≢ 1 x_0\not\equiv 1 x 0 ≡ 1 且 x 0 , … , x r − 1 ≢ − 1 x_0,\dots,x_{r-1}\not\equiv -1 x 0 , … , x r − 1 ≡ − 1 。由於 x r ≡ 1 x_r\equiv 1 x r ≡ 1 ,對所有 t ≥ r t\ge r t ≥ r 都有 x t ≡ 1 x_t\equiv 1 x t ≡ 1 ,而因 n ≥ 3 n\ge 3 n ≥ 3 ,1 ≢ − 1 1\not\equiv -1 1 ≡ − 1 。所以在階段 0 , … , s − 1 0,\dots,s-1 0 , … , s − 1 沒有任何一項等於 − 1 -1 − 1 ,定義拒絕。
否則 x r ≢ ± 1 x_r\not\equiv\pm1 x r ≡ ± 1 。該輪令 x ← x r x\leftarrow x_r x ← x r ,不變式對 r + 1 r+1 r + 1 成立。
若迴圈結束,不變式表明 x 0 , … , x s − 1 x_0,\dots,x_{s-1} x 0 , … , x s − 1 都不同於 ± 1 \pm1 ± 1 ,故定義拒絕。該輪亦在第 9 行拒絕。
解讀失敗的一輪
FAIL 不僅是一個否定的判定,它總是附帶著 n n n 為合數的證據,且屬於以下三種之一。
公因數。 gcd 步驟觸發,且 g = gcd ( a , n ) g=\gcd(a,n) g = g cd( a , n ) 滿足 1 < g ≤ a < n 1<g\le a<n 1 < g ≤ a < n 。因此 g g g 是 n n n 的真因數。
1 的非平凡平方根。 第 7 行觸發。此時 x ≡ x r − 1 x\equiv x_{r-1} x ≡ x r − 1 滿足 x 2 ≡ 1 x^2\equiv 1 x 2 ≡ 1 且 x ≢ ± 1 x\not\equiv\pm 1 x ≡ ± 1 。由非平凡平方根的引理,gcd ( x − 1 , n ) \gcd(x-1,n) g cd( x − 1 , n ) 是真因數。
在第 9 行耗盡。 我們知道 x s − 1 ≢ ± 1 x_{s-1}\not\equiv \pm 1 x s − 1 ≡ ± 1 。考慮該輪從未計算的項 x s ≡ x s − 1 2 ≡ a n − 1 x_s\equiv x_{s-1}^2\equiv a^{n-1} x s ≡ x s − 1 2 ≡ a n − 1 。要麼 x s ≢ 1 x_s\not\equiv 1 x s ≡ 1 ,此時 a a a 是費馬見證者,由費馬定理 n n n 為合數;要麼 x s ≡ 1 x_s\equiv 1 x s ≡ 1 ,此時 x s − 1 x_{s-1} x s − 1 是 1 1 1 的非平凡平方根。
在情形 1 與 2,以及情形 3 中 x s ≡ 1 x_s\equiv 1 x s ≡ 1 的情況下,我們甚至可得到 n n n 的一個真因數。當 s = 1 s=1 s = 1 時,迴圈為空,而對互質的底,每個 FAIL 都屬類型 3,完全由數值 x 0 x_0 x 0 決定。
任何人都可以用一次模冪運算或一次 gcd 重新核對這些證書。因此,COMPOSITE 判定不僅僅是概率性的,而是已被證明的,其證明就是那個導致失敗的底。
快速檢查
(對 n = 21 n=21 n = 21 與 a = 8 a=8 a = 8 執行強檢驗的一輪。出現哪一種失敗?它揭示了 21 21 21 的哪些因數?)
寫 20 = 2 2 ⋅ 5 20=2^2\cdot5 20 = 2 2 ⋅ 5 ,並先計算 8 2 8^2 8 2 。
解答 · 答案 此時 s = 2 s=2 s = 2 ,d = 5 d=5 d = 5 ,且 gcd ( 8 , 21 ) = 1 \gcd(8,21)=1 g cd( 8 , 21 ) = 1 。由於 8 2 = 64 = 3 ⋅ 21 + 1 ≡ 1 8^2=64=3\cdot21+1\equiv1 8 2 = 64 = 3 ⋅ 21 + 1 ≡ 1 ,得 x 0 = 8 5 = 8 ( 8 2 ) 2 ≡ 8 x_0=8^5=8\,(8^2)^2\equiv8 x 0 = 8 5 = 8 ( 8 2 ) 2 ≡ 8 ,它既不是 1 1 1 也不是 20 20 20 。在第 r = 1 r=1 r = 1 次迭代中 y = 8 2 ≡ 1 y=8^2\equiv1 y = 8 2 ≡ 1 ,所以第 7 行返回 FAIL。這是類型 2 的失敗:x = 8 x=8 x = 8 是 1 1 1 的平方根且不是 ± 1 \pm1 ± 1 ,而 gcd ( 8 − 1 , 21 ) = 7 \gcd(8-1,21)=7 g cd( 8 − 1 , 21 ) = 7 ,gcd ( 8 + 1 , 21 ) = 3 \gcd(8+1,21)=3 g cd( 8 + 1 , 21 ) = 3 。
用盡檢查階段後的兩種解釋
追蹤兩個簡短輪次中的變量,就能看清上述失敗類型 3 的兩種可能。兩例中的最大公因數都是 1 1 1 ,因此拒絕來自強條件,而非開頭找到了公因數。
例題 8.1.8
(用盡檢查階段:n = 9 n=9 n = 9 ,底為 2 2 2 )
寫 9 − 1 = 8 = 2 3 ⋅ 1 9-1=8=2^3\cdot1 9 − 1 = 8 = 2 3 ⋅ 1 ,故 s = 3 s=3 s = 3 ,d = 1 d=1 d = 1 。由於 gcd ( 2 , 9 ) = 1 \gcd(2,9)=1 g cd( 2 , 9 ) = 1 ,第 2 行給出 x 0 = 2 x_0=2 x 0 = 2 。它既不是 1 1 1 也不是 8 8 8 ,第 3 行不接受。在 r = 1 r=1 r = 1 時,計算 x 1 = 2 2 m o d 9 = 4 x_1=2^2\bmod9=4 x 1 = 2 2 mod 9 = 4 ;它既不是 8 8 8 也不是 1 1 1 ,所以迴圈以 x = 4 x=4 x = 4 繼續。在 r = 2 r=2 r = 2 時得到 x 2 = 4 2 m o d 9 = 7 x_2=4^2\bmod9=7 x 2 = 4 2 mod 9 = 7 ,仍既不是 8 8 8 也不是 1 1 1 。已無更多待檢查的階段,第 9 行返回 FAIL。
為了解釋失敗,再計算額外的值 x 3 = 7 2 m o d 9 = 4 x_3=7^2\bmod9=4 x 3 = 7 2 mod 9 = 4 。該輪本身並不執行這最後一次平方。它說明 2 8 ≢ 1 ( m o d 9 ) 2^8\not\equiv1\pmod9 2 8 ≡ 1 ( mod 9 ) ,所以底 2 2 2 已經是費馬見證者。這條追蹤中沒有出現 1 1 1 的非平凡平方根:該輪因用盡允許檢查的階段而拒絕,並非第 7 行偵測到了這樣的根。
例題 8.1.9
(空迴圈仍能偵測費馬說謊者:n = 15 n=15 n = 15 ,底為 4 4 4 )
此時 15 − 1 = 14 = 2 ⋅ 7 15-1=14=2\cdot7 15 − 1 = 14 = 2 ⋅ 7 ,故 s = 1 s=1 s = 1 ,d = 7 d=7 d = 7 。由於 gcd ( 4 , 15 ) = 1 \gcd(4,15)=1 g cd( 4 , 15 ) = 1 ,底是一個單位。又因 4 2 = 16 ≡ 1 ( m o d 15 ) 4^2=16\equiv1\pmod{15} 4 2 = 16 ≡ 1 ( mod 15 ) ,
x 0 = 4 7 = 4 ( 4 2 ) 3 ≡ 4 ( m o d 15 ) . x_0=4^7=4(4^2)^3\equiv4\pmod{15}. x 0 = 4 7 = 4 ( 4 2 ) 3 ≡ 4 ( mod 15 ) . 初始值既不是 1 1 1 也不是 14 14 14 。迴圈的範圍由 r = 1 r=1 r = 1 到 s − 1 = 0 s-1=0 s − 1 = 0 ,因此不執行任何迭代,第 9 行返回 FAIL。然而,費馬值為 4 14 = ( 4 2 ) 7 ≡ 1 ( m o d 15 ) 4^{14}=(4^2)^7\equiv1\pmod{15} 4 14 = ( 4 2 ) 7 ≡ 1 ( mod 15 ) 。因此,末項為 1 1 1 並不足以滿足強條件:它的前一項 4 4 4 是 1 1 1 的非平凡平方根。非平凡平方根的引理把證書具體化為
gcd ( 4 − 1 , 15 ) = 3 , gcd ( 4 + 1 , 15 ) = 5. \gcd(4-1,15)=3,\qquad \gcd(4+1,15)=5. g cd( 4 − 1 , 15 ) = 3 , g cd( 4 + 1 , 15 ) = 5. 這是失敗類型 3 中的第二種可能。儘管第 7 行完全未執行,變量 x x x 已保存的值仍給出了平方根,進而給出因數分解。相比之下,底 14 14 14 因 14 7 ≡ − 1 ( m o d 15 ) 14^7\equiv-1\pmod{15} 1 4 7 ≡ − 1 ( mod 15 ) 而立即通過;這一個通過的底並不能證明 15 15 15 為質數。
定理/命題
設 n n n 為奇質數,a ∈ { 1 , … , n − 1 } a\in\{1,\dots,n-1\} a ∈ { 1 , … , n − 1 } 。則 a a a 通過。因此,對每個奇質數 n n n 及隨機抽取的每個結果,MILLER-RABIN( n , k ) (n,k) ( n , k ) 都返回 PROBABLE-PRIME。對 n = 2 n=2 n = 2 ,它返回 PRIME。
由於 1 ≤ a ≤ n − 1 1\le a\le n-1 1 ≤ a ≤ n − 1 且 n n n 為質數,故 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 。由費馬小定理,x s ≡ a n − 1 ≡ 1 ( m o d n ) x_s\equiv a^{n-1}\equiv 1 \pmod n x s ≡ a n − 1 ≡ 1 ( mod n ) 。所以滿足 x r ≡ 1 x_r\equiv 1 x r ≡ 1 的階段 r r r 所成的集合非空。設 r 0 r_0 r 0 為其最小元。
若 r 0 = 0 r_0 = 0 r 0 = 0 ,則 a d ≡ 1 a^d\equiv 1 a d ≡ 1 ,a a a 通過。
若 r 0 ≥ 1 r_0\ge 1 r 0 ≥ 1 ,則 x r 0 − 1 2 ≡ x r 0 ≡ 1 x_{r_0-1}^2\equiv x_{r_0}\equiv 1 x r 0 − 1 2 ≡ x r 0 ≡ 1 ,且由最小性 x r 0 − 1 ≢ 1 x_{r_0-1}\not\equiv 1 x r 0 − 1 ≡ 1 。由質數模下 1 1 1 的平方根的引理,x r 0 − 1 ≡ − 1 x_{r_0-1}\equiv -1 x r 0 − 1 ≡ − 1 。階段 r 0 − 1 r_0-1 r 0 − 1 介乎 0 0 0 與 s − 1 s-1 s − 1 之間,故 a a a 通過。
由於該輪判定的正是強條件,每一輪都返回 PASS,因此算法到達第 9 行並返回 PROBABLE-PRIME。n = 2 n=2 n = 2 的情形在第 1 行處理。
證明透視
質數必定通過的證明中各要素的作用 證明用到三個事實,每個恰好用一次。費馬小定理保證數值 1 1 1 出現在強序列中,最遲在第 s s s 階段;它需要 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ,而對質數 n n n ,這由 1 ≤ a ≤ n − 1 1\le a\le n-1 1 ≤ a ≤ n − 1 得出。若沒有這次出現,最小階段 r 0 r_0 r 0 便不存在。
關鍵一步是取 r 0 r_0 r 0 為最小。最小性提供一個前一項 x r 0 − 1 x_{r_0-1} x r 0 − 1 ,它平方後為 1 1 1 而自身不是 1 1 1 。質數性只在這裏介入:質數模下 1 1 1 的平方根的引理迫使這個前一項等於 − 1 -1 − 1 。由於 r 0 ≤ s r_0\le s r 0 ≤ s ,接受階段 r 0 − 1 r_0-1 r 0 − 1 落在 { 0 , … , s − 1 } \{0,\dots,s-1\} { 0 , … , s − 1 } 之內,這就是第 s s s 階段從不需要檢查的原因。
對合數模,論證恰好在該引理處失效。對 n = 15 n=15 n = 15 與 a = 4 a=4 a = 4 ,首個 1 1 1 出現在 r 0 = 1 r_0=1 r 0 = 1 ,但它的前一項 x 0 = 4 x_0=4 x 0 = 4 是 1 1 1 的平方根而不是 ± 1 \pm1 ± 1 ;儘管 4 14 ≡ 1 4^{14}\equiv1 4 14 ≡ 1 ,這個底仍不通過。證明既沒有用到 gcd 步驟,也沒有用到隨機抽取:結論對每個底都成立。
因此,此檢驗具有單邊錯誤 :它從不把質數判為合數,所有可能的錯誤都是把合數報告為概質數。配套章節證明這種情況發生的頻率。
常見錯誤
反例模式
卡邁克爾數的費馬說謊者不一定是強說謊者 一個看似合理的說法是:強檢驗只是重新安排 a n − 1 a^{n-1} a n − 1 的計算,所以對卡邁克爾數,每個單位既然都是費馬說謊者,也就都是強說謊者。取 n = 561 n=561 n = 561 ,故 s = 4 s=4 s = 4 ,d = 35 d=35 d = 35 ,並取底 a = 5 a=5 a = 5 。逐次平方得
x 0 ≡ 23 , x 1 ≡ 529 , x 2 ≡ 463 , x 3 ≡ 67 , x 4 ≡ 1 ( m o d 561 ) . x_0\equiv23,\quad x_1\equiv529,\quad x_2\equiv463,\quad x_3\equiv67,\quad x_4\equiv1 \pmod{561}. x 0 ≡ 23 , x 1 ≡ 529 , x 2 ≡ 463 , x 3 ≡ 67 , x 4 ≡ 1 ( mod 561 ) . 確實 67 2 = 4489 = 8 ⋅ 561 + 1 67^2=4489=8\cdot561+1 6 7 2 = 4489 = 8 ⋅ 561 + 1 。所以 5 5 5 是費馬說謊者,但被檢查的數值 x 0 , … , x 3 x_0,\dots,x_3 x 0 , … , x 3 沒有一個是 1 1 1 或 560 560 560 ,該輪在第 9 行失敗。這是 x s ≡ 1 x_s\equiv1 x s ≡ 1 的失敗類型 3:67 67 67 是 1 1 1 的非平凡平方根,且 gcd ( 66 , 561 ) = 33 \gcd(66,561)=33 g cd( 66 , 561 ) = 33 ,gcd ( 68 , 561 ) = 17 \gcd(68,561)=17 g cd( 68 , 561 ) = 17 。正確的說法是:強條件嚴格強於費馬條件,它考察通向 a n − 1 a^{n-1} a n − 1 的路徑,而不只是終點。
低於 2 − k 2^{-k} 2 − k 的界要求底對給定輸入獨立且均勻地抽取。固定的一組底對某個特定合數並沒有這樣的保證。對 n = 2047 = 23 ⋅ 89 n=2047=23\cdot89 n = 2047 = 23 ⋅ 89 ,如上面的快速檢查所示,底 2 2 2 通過,所以無論重複底 2 2 2 多少次,每次都返回 PROBABLE-PRIME。換一個底仍可揭穿 2047 2047 2047 :3 1023 ≡ 1565 ( m o d 2047 ) 3^{1023}\equiv1565\pmod{2047} 3 1023 ≡ 1565 ( mod 2047 ) ,既不是 1 1 1 也不是 2046 2046 2046 ,而 s = 1 s=1 s = 1 ,所以以 3 3 3 為底的一輪失敗。
練習
快速檢查
(1 的平方根與兩種失敗:設 n n n 為奇數,n ≥ 3 n\ge3 n ≥ 3 。)
(a) 證明:若 n = p e n=p^e n = p e ,其中 p p p 為奇質數且 e ≥ 1 e\ge 1 e ≥ 1 ,則 x 2 ≡ 1 ( m o d p e ) x^2\equiv1\pmod{p^e} x 2 ≡ 1 ( mod p e ) 的解只有 x ≡ ± 1 x\equiv\pm1 x ≡ ± 1 。
(b) 證明:若 n n n 恰有 ω \omega ω 個不同的質因數,則 x 2 ≡ 1 ( m o d n ) x^2\equiv1\pmod n x 2 ≡ 1 ( mod n ) 在模 n n n 下恰有 2 ω 2^\omega 2 ω 個解。由此斷定 1 1 1 的非平凡平方根存在,當且僅當 ω ≥ 2 \omega\ge2 ω ≥ 2 。
(c) 證明:若 n n n 為奇質數冪,而互質的底 a a a 令強檢驗一輪失敗,則 a a a 是費馬見證者:a n − 1 ≢ 1 a^{n-1}\not\equiv1 a n − 1 ≡ 1 。就 n = 9 n=9 n = 9 ,a = 2 a=2 a = 2 驗證此結論。
(d) 證明:若 x x x 是奇合數 n n n 模下 1 1 1 的非平凡平方根,則 x x x 是費馬說謊者但為強見證者。指出它屬於「解讀失敗的一輪」中的哪一種失敗類型。
解答 (a) 設 p e ∣ ( x − 1 ) ( x + 1 ) p^e\mid(x-1)(x+1) p e ∣ ( x − 1 ) ( x + 1 ) 。若 p p p 同時整除兩個因子,則它整除兩者之差 2 2 2 ,這對奇數 p p p 是不可能的。所以 p p p 只整除其中一個因子,於是整個冪 p e p^e p e 必須整除該因子。因此 x ≡ 1 x\equiv1 x ≡ 1 或 x ≡ − 1 ( m o d p e ) x\equiv-1\pmod{p^e} x ≡ − 1 ( mod p e ) ,且由於 p e ≥ 3 p^e\ge3 p e ≥ 3 ,這兩者相異。
(b) 寫 n = ∏ i = 1 ω p i e i n=\prod\limits_{i=1}^{\omega}p_i^{e_i} n = i = 1 ∏ ω p i e i 。由 CRT,x 2 ≡ 1 ( m o d n ) x^2\equiv1\pmod n x 2 ≡ 1 ( mod n ) 當且僅當對每個 i i i 都有 x 2 ≡ 1 ( m o d p i e i ) x^2\equiv1\pmod{p_i^{e_i}} x 2 ≡ 1 ( mod p i e i ) 。由 (a),每個分量恰有 2 2 2 個解,而 CRT 給出解的元組與模 n n n 的解之間的雙射。因此共有 2 ω 2^\omega 2 ω 個解。由於 ± 1 \pm1 ± 1 是其中兩個,非平凡的解存在,當且僅當 2 ω > 2 2^\omega>2 2 ω > 2 ,即 ω ≥ 2 \omega\ge2 ω ≥ 2 。
(c) 由失敗輪次的分類,失敗的互質底,要麼有 a n − 1 ≢ 1 a^{n-1}\not\equiv1 a n − 1 ≡ 1 ,要麼產生模 n n n 下 1 1 1 的非平凡平方根。對 n = p e n=p^e n = p e ,(a) 排除了第二種可能。對 n = 9 n=9 n = 9 與 a = 2 a=2 a = 2 ,強序列為 2 , 4 , 7 2,4,7 2 , 4 , 7 ,然後 a 8 ≡ 7 2 = 49 ≡ 4 ≠ 1 a^8\equiv7^2=49\equiv4\ne1 a 8 ≡ 7 2 = 49 ≡ 4 = 1 ,所以 2 2 2 是費馬見證者。
(d) 由於 x 2 ≡ 1 x^2\equiv1 x 2 ≡ 1 且 n − 1 n-1 n − 1 為偶數,x n − 1 = ( x 2 ) ( n − 1 ) / 2 ≡ 1 x^{n-1}=(x^2)^{(n-1)/2}\equiv1 x n − 1 = ( x 2 ) ( n − 1 ) /2 ≡ 1 ,所以 x x x 是費馬說謊者。由於 d d d 為奇數,x d = x ⋅ ( x 2 ) ( d − 1 ) / 2 ≡ x x^d=x\cdot(x^2)^{(d-1)/2}\equiv x x d = x ⋅ ( x 2 ) ( d − 1 ) /2 ≡ x ,它不是 ± 1 \pm1 ± 1 ,所以 x x x 在第 0 0 0 階段不通過。然後 x 1 ≡ x 2 ≡ 1 x_1\equiv x^2\equiv1 x 1 ≡ x 2 ≡ 1 ,故對所有 r ≥ 1 r\ge1 r ≥ 1 都有 x r ≡ 1 x_r\equiv 1 x r ≡ 1 ,− 1 -1 − 1 永不出現。
若 s ≥ 2 s\ge2 s ≥ 2 ,該輪在第 r = 1 r=1 r = 1 次迭代的第 7 行失敗。這是類型 2,證書為 x x x 本身。
若 s = 1 s=1 s = 1 ,該輪在第 9 行失敗。這是 x s ≡ 1 x_s\equiv1 x s ≡ 1 的類型 3,所以 x s − 1 = x x_{s-1}=x x s − 1 = x 同樣是那個非平凡根。
n = 15 n=15 n = 15 的底 4 4 4 與 11 11 11 ,以及 n = 21 n=21 n = 21 的底 8 8 8 與 13 13 13 ,都是實例。