動機
相鄰章節定義強序列,給出算法並證明質數輸入總會通過。本節以具體輸入運行算法,並分析實現成本。
定理/命題
定理 8.2.1
(每輪的正確性)
對奇質數,每個允許的底數均通過;對任何奇數輸入,未通過的輪次可證明它是合數。相鄰章節證明了這兩點。
定理 8.2.2
(計算成本)
使用教科書式乘法及除法時, 位元輸入的一輪強檢驗使用 位元運算;均勻選底數還需期望 個隨機位元。下方的運算計數給出理由。
例題
在下列追蹤中,「階段數值」是 中的剩餘 。數值 以 表示。
追蹤表中未填寫的後續階段表示該輪已停止,並非相應的冪沒有定義。若底在最大公因數檢查時已被拒絕,就不會再執行模冪運算;若在某階段通過,也不會再計算其後的平方。相反,為了比較強檢驗與費馬(Fermat)檢驗而額外列出的末項,是教學上的補充計算,須與偽代碼實際執行的步驟分開。這個區分也影響成本分析:下文計算的是一輪可能用到的上界,提早停止的輪次可以少做許多運算。
例題 8.2.3
( 的追蹤)
我們有 ,故 ,。該輪檢查 是否為 ,並檢查 、 是否為 。列 並不由該輪計算,列出它是為了解釋失敗的情形。
| 底 | 判定 | |||||
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 通過(第 0 階段) | |||
| 2 | 1 | 2 | 4 | 7 | 4 | 失敗 |
| 3 | 3 | 失敗(gcd) | ||||
| 4 | 1 | 4 | 7 | 4 | 7 | 失敗 |
| 5 | 1 | 5 | 7 | 4 | 7 | 失敗 |
| 6 | 3 | 失敗(gcd) | ||||
| 7 | 1 | 7 | 4 | 7 | 4 | 失敗 |
| 8 | 1 | 8 | 通過(第 0 階段) |
例如,對於 :,,。
每個互質而失敗的底都以 結束,因此每個都是費馬見證者。這並非偶然。模 時 的平方根只有 (相鄰章節關於 的平方根的練習),所以類型 2 的失敗不可能發生。通過的底為 :八個底中有兩個,穩妥地落在 之內。配套章節利用子群界研究此例。
例題 8.2.4
( 的追蹤)
我們有 ,故 ,。迴圈為空,對互質的底,判定僅取決於 是否為 。我們亦列出該輪並不計算的 。
| 底 | 判定 | 解釋 | ||
|---|---|---|---|---|
| 1 | 1 | 1 | 通過 | |
| 2 | 8 | 4 | 失敗 | 費馬見證者 |
| 4 | 4 | 1 | 失敗 | 是 的非平凡根 |
| 7 | 13 | 4 | 失敗 | 費馬見證者 |
| 8 | 2 | 4 | 失敗 | 費馬見證者 |
| 11 | 11 | 1 | 失敗 | 是 的非平凡根 |
| 13 | 7 | 4 | 失敗 | 費馬見證者 |
| 14 | 14 | 1 | 通過 |
六個底 在 gcd 步驟失敗。
一些示範計算:。由於 ,得 。由於 ,得 。
底 與 是費馬說謊者,因為 ,但同時是強見證者。它們各自是 的平方根且不是 ,而相鄰章節關於非平凡平方根的引理由它們分解出 : 與 ,或 與 。只有 與 通過,即 個底中有 個通過。
例題 8.2.5
( 的追蹤)
我們有 ,故 ,。該輪檢查 是否為 ,並檢查 是否為 。
一個結構性的捷徑可簡化計算。我們有 ,且每個單位都滿足 。所以 , 就是 模 的逆元。然後 。
| 底 | 判定 | ||
|---|---|---|---|
| 1 | 1 | 通過(第 0 階段) | |
| 2 | 11 | 16 | 失敗 |
| 4 | 16 | 4 | 失敗 |
| 5 | 17 | 16 | 失敗 |
| 8 | 8 | 1 | 失敗: 是 的非平凡根 |
| 10 | 19 | 4 | 失敗 |
| 11 | 2 | 4 | 失敗 |
| 13 | 13 | 1 | 失敗: 是 的非平凡根 |
| 16 | 4 | 16 | 失敗 |
| 17 | 5 | 4 | 失敗 |
| 19 | 10 | 16 | 失敗 |
| 20 | 20 | 通過(第 0 階段) |
底 在 gcd 步驟失敗。
直接核對幾個項目:,而 。又 ,故 。
對於 ,該輪計算 ,然後 ,第 7 行返回 FAIL,證書為 。此時 ,。底 同樣給出 與 。
沒有任何單位在第 1 階段達到 。模 時,單位的每個偶次冪都是 ,而不是 。所以二十個底中有兩個通過。費馬說謊者為 ,因此強檢驗拒絕了兩個被費馬檢驗接受的底。
例題 8.2.6
(較大的追蹤:,底為 )
我們有 ,故 ,。由於 是卡邁克爾數(Carmichael number)(見相鄰章節),費馬檢驗接受每個互質的底。我們以與 互質的 運行強檢驗的一輪。
分別模 、 與 計算,再以 CRT 合併,會較為有效。
- 模 :,故 ,其後每次平方都是 。
- 模 : 且 ,故 ,其後每次平方都是 。
- 模 : 且 ,故 。平方得 ,再得 ,再得 。
| 階段 | 模 3 | 模 11 | 模 17 | 模 561 |
|---|---|---|---|---|
| 0 | 2 | 10 | 8 | 263 |
| 1 | 1 | 1 | 13 | 166 |
| 2 | 1 | 1 | 16 | 67 |
| 3 | 1 | 1 | 1 | 1 |
合併後的數值可以直接核對:,,。
該輪的進行如下。第 2 行得 ,不是 。第 次迭代得 ,第 次迭代得 ,第 次迭代得 。第 7 行以 返回 FAIL,它是 的非平凡平方根。相鄰章節關於非平凡平方根的引理抽取出因數:
而確實 。
CRT 各列顯示了該非平凡根的來源:模 與模 的分量比模 的分量更早到達 。在第 階段,剩餘的符號並不一致:模 為 ,模 為 。配套章節在其證明中使用這個符號混合的想法。
概念視角代數
通過即同步到達
把各階段的值模每個恰好整除 的質數冪 化約,一輪就分拆成各分量上的獨立序列。由於 是奇數, 恰好當 模每個這樣的 都同號地 。所以一個底數通過,恰好當所有分量都由 開始,或所有分量在同一階段都等於 。各分量在不同階段到達就必然失敗,正如 的追蹤中,模 的分量落後了。
快速檢查
(對 與 執行強檢驗的一輪。它在哪裏停止?停止時揭示了 的哪些因數?)
此時 ,故 。
解答 · 答案
由於 且 ,第 2 行給出 ,它既不是 也不是 。在第 次迭代中,,所以第 7 行以 返回 FAIL,而 是 的平方根且不是 。於是 ,。雖然 容許四次迭代,該輪在一次平方後便停止。
成本:算術運算與位元運算
設 為 的位元數,這就是輸入的大小。
算術運算次數。 以由左至右的平方乘法計算 ,至多使用 次模乘法。之後,迴圈至多執行 次平方。由於 ,一輪中模乘法的總次數至多為
所以一輪使用 次模乘法,而 輪使用 次(見關於一輪成本的練習)。
快速檢查
(計算上面 、 那一輪所用的模乘法次數,並與上界 比較。)
把 寫成二進制。
解答 · 答案
二進制下 。由左至右的平方乘法以 對應首位,其後對其餘五位各平方一次,並對最後兩個為 的位各乘以 一次:共 次乘法,不超過 。迴圈在第 次迭代各平方一次,再多三次乘法。該輪合共用 次。由於 ,有 ,上界為 。
位元運算次數。 把模乘法視為單位成本運算,會掩蓋被相乘的數的大小。每次乘法都是在至多 位元的剩餘之間進行,產生至多 位元的乘積,之後還須模 約化。
- 以教科書式乘法與長除法,每次模乘法的成本為 位元運算。於是一輪的成本為 位元運算, 輪為 。
- 若以 表示用較快算法把兩個 位元整數相乘的成本,並且模 約化採用成本與一次乘法相若的技巧,則一輪的成本為 。
- gcd 步驟使用歐幾里得(Euclid)算法。它對至多 位元的數進行 次除法步驟,在粗略的教科書式計算下為 位元運算。更精細的分析給出 。無論哪一種,它都不會主導冪運算的成本。
- 選取底的預期成本為 個隨機位元。 拒絕抽樣迴圈沒有有限的確定性最壞輪數;計入抽樣後,上述總運行時間是期望界。
與試除法的比較。 對質數 ,以不超過 的所有整數進行試除,約需 次除法,相對輸入大小 是指數級的。米勒–拉賓(Miller–Rabin)則是 的多項式。
常見錯誤
(把乘法次數當作運行時間)
「此檢驗需 步」這類說法,只有當每一步指一次模 乘法時才正確。每一步都要相乘至多 位元的數,所以用教科書式算術,一輪需 次位元運算, 輪需 次。比較運行時間之前,須先說明採用哪種成本模型。
快速檢查
(採用教科書式算術時,若 的位元長度 加倍,一輪位元成本的上界大約增大多少倍?與試除至 比較。)
比較 與 ,以及 與 。
解答 · 答案
上界 變為 ,所以上界增大 倍。試除的次數約為 ,變為約 :它乘以 ,而這個倍數本身隨 指數增長。
概質數不是已證明的質數
兩種判定的邏輯地位截然不同。
- COMPOSITE 是一個證明。 導致失敗的底,連同相鄰章節所分類的失敗類型,就是一份任何人都可以用一次冪運算或一次 gcd 計算來驗證的證書。
- PROBABLE-PRIME 不是證明。 它只表示 個獨立選取的底全部通過。配套章節為合數輸入界定了這一事件的概率,但並不排除該事件,而且檢驗所產生的任何東西都不能讓第三方驗證 是質數。
當必須確實建立質數性時,需要另一種質數證明方法。這類方法產生的證書,其驗證不依賴隨機性。這些方法超出本筆記的範圍。在實際應用中,米勒–拉賓常被用作它們之前的快速篩選,以低成本剔除絕大多數合數候選者。
例題 8.2.7
(迫使算法提早停止的平方根)
取 、,寫 。首項 既不是 也不是 ;下一項 ,所以本輪立即拒絕。實際上 ,,得到兩個質因數。之後的值雖然都是 ,算法卻已停止,不能因此把拒絕改成接受。
這個根有具體的 CRT 解釋:,而 。平方消去不同的符號,因此在兩個因數模下都得到 。混合的符號說明 整體上既不是 ,也不是 ;對於質數模,相應的因式分解論證排除了這種情況。
費馬見證不一定立即給出因數。取 、,則 ,。由於 ,該輪計算出 ,它既不是 也不是 ,於是在第 9 行失敗。未計算的值為 ,所以 是費馬見證者, 被證明為合數。然而 ,且 :這一輪的數值沒有一個能透過這些 gcd 揭示真因數。合數性的證書與一個明確因數是不同類型的輸出。
練習
快速檢查
(一輪的成本:設 為奇數,位元長度為 ,且 ( 為奇數)。)
(a) 證明:由左至右的平方乘法以至多 次模乘法計算 。由此推出一輪至多使用 次模乘法。
(b) 假設採用教科書式乘法與除法,使得一次模 乘法至多花費 次位元運算( 為常數),求 輪的位元成本上界(不計 gcd 與底的生成)。
(c) 對於 位元的奇數 ,給出每輪模乘法次數的明確上界,並與以試除法(試除至 )確認質數性所需的試除次數比較。
(d) 解釋為何「 的多項式」會是錯誤的效率準則。
解答
(a) 設 有 個位元。由左至右的平方乘法由 開始,這已計入最高位元。對其餘 個位元的每一個,先平方一次,若該位元為 ,再乘以 一次。因此至多 次乘法。
由於 ,我們有 ,而因 是整數,。迴圈至多再加 次平方。總數至多為
(b) 一輪至多花費 次位元運算,故 輪少於 次。這是 次位元運算。
(c) 位元的奇數 滿足 。所以 ,且 。由於 ,上界至多為 次模乘法每輪。
對質數 ,試除至 須測試每個不超過 的候選因數。即使只限於奇數候選,也超過 次除法,是個大得多的天文數字。
(d) 輸入以 個位元書寫,所以效率必須以 的函數來衡量。一個關於 為多項式的算法,例如成本約為 的試除法,相對 是指數級的,對密碼學規模的數不可行。米勒–拉賓以教科書式算術的成本 是 的多項式,這正是它切實可行的原因。