動機
配套小節定義了強序列,給出了精確的算法,並證明了質數輸入必定通過。本節固定一個奇合數,證明它所能欺騙的底數個數的上界。關鍵在於把每一個通過的底數都包含在同一個真子群內;通過的底數本身不必構成子群。對於具有相異質因子的模數,以中國剩餘定理(CRT)處理;對於質數冪,則以一個小的主單位處理。與配套小節一樣,記 ,其中 且 為奇數;第 階段指餘數 。
定理/命題
不與 互質的底數
引理 8.3.1
(不互質的底數必定不通過)
設 為奇數,且 。則對每個 ,均有 。特別地,即使省略最大公因數的步驟, 也會不通過。
證明
(模公因數約化)
假設 ,其中 。由於 ,同一同餘式在模 下亦成立。但 ,故左邊 ,而 迫使 ,矛盾。
因此每個通過的底數都是模 的單位。我們記 ,它是階為 的阿貝爾(Abel)群,並記
一半上界
定理 8.3.2
(一半上界)
設 為奇合數。則 中通過的底數個數滿足
因此,從 中均勻抽取的底數通過的概率至多為 ,而這個值嚴格小於 。
快速檢查
(對 ,直接求出通過的底數集合 ,並把 與 比較。)
此時 ,故 、;先列出各單位的平方。
解答 · 答案
單位為 ,它們的平方只有 。階段 恰好讓 通過,即 。階段 需要 ,但 不是平方數。階段 需要 ,但 的平方分別是 。因此 ,。通過概率為 ,正如定理所要求,低於一半。
證明思路或證明
證明
(包含每個通過底數的真子群)
固定奇合數 ,其中 , 為奇數,。由於 ,殘基 與 在模 下相異,且 是 的一個 階子群。
步驟 1:選取階段 。 令
集合 含有 ,因為取 時,對奇數 有 。所以 非空且有限,令 ,並記
按構造,存在單位 使得 。此外,在任何被檢查的階段 (),都沒有單位取值為 。
我們不需要另外處理「 為空」的情形。集合 必定包含 與 ,而且下面的論證從不使用 非空這一點。階段 是透過單位 來定義的,無論是否有其他單位達到 。
步驟 2: 是子群。 定義 ,。由於 是阿貝爾群,,故 是群同態。於是
是子群在同態下的原像,因此是 的子群。
步驟 3:每個通過的底數都屬於 。 設 。 可以透過兩種方式通過。
- 情形 。 此時 ,故 。
- 情形:對某個階段 ,有 。 此時 ,由 見證,故由最大性得 。寫 。若 ,此值為 。若 ,則指數 為偶數,此值為 。無論哪種情況,。
這正是把 選為最後一個階段的關鍵所在。通過的底數在階段 或更早時達到 ,絕不會更晚。一旦底數達到 ,之後每次平方都得到 。因此在階段 ,所有在較早階段通過的底數都處於 ,而恰好在階段 通過的底數則處於 。滿足 的底數則始終處於 。單一個子群 就把它們全部涵蓋了。
步驟 4: 是真子群。 我們必須給出一個單位 ,使得 。由於 是合數,以下兩種情形恰有一種成立。
情形 A: 至少有兩個相異質因子。 取質數 ,並令 為恰好整除 的 的冪。置 ,。則 ,且 與 均為大於 的奇數,故兩者皆至少為 。設 為步驟 1 中滿足 的單位。由 CRT,存在整數 使得
於是 與 互質(因為 與 互質),也與 互質,所以 。它的 次冪滿足
若 ,則模 約化得 ,即 。由於 ,這是不可能的。若 ,則模 約化得 ,這同樣不可能。因此 ,即 。
像 具有混合符號:在一個互質分量上為 ,在另一個分量上為 。這樣的元素是模 下 的一個異於 的平方根,而這正是質數模數所不可能擁有的對象。
情形 B:,其中 為奇質數且 。 令 。由於 , 是單位。對每個整數 ,二項式定理給出
因為每個 的項都可被 整除,而 恰在 時成立。因此 當且僅當 ,即當且僅當 。所以 的階恰為 。
現在 。事實上, 為奇數,故 。又 且 ,所以若 則 。因此 。此外,,而由於 為奇數,。所以 亦成立。於是 。
在情形 B 中,我們沒有用到 的具體數值,只用到 與 互質。就這一點而言,質數冪的情形較為容易。
步驟 5:計數。 是有限群 的真子群。由拉格朗日(Lagrange)定理, 整除 ,且 ,故 。由步驟 3,。
其次,對合數 有 。在 之中, 的每個質因子 都滿足 且 ,所以 中至少有一個元素不是單位。由上述不互質底數的引理,非單位不會產生通過的底數。因此
除以 個等可能的底數,得到通過概率至多為 ,而這個值嚴格小於 。
證明透視
各個假設在一半上界中的位置
每個假設都只在一個可以指明的地方使用。 為奇數給出 ,使 非空;它亦使情形 A 中兩個 CRT 分量都至少為 ,所以具有混合符號的元素不可能是 。 為合數只在步驟 4 用到。若 是質數,兩種情形都不存在,而結論也確實不成立:此時 、,由歐拉(Euler)判別法,每個單位都屬於 ,故 。 的交換性只用來保證 是同態。
唯一不顯然的一步是選取 ,它要同時滿足兩個方向相反的要求。步驟 3 需要 不小於任何通過底數達到 的階段;步驟 4 的情形 A 則需要在階段 本身有單位 使 。較小的指標違反第一個要求: 的見證 是通過的,而若 且 ,平方後會得到 ,所以 不在較小指標所定的子群內。較大的被檢查指標不屬於 ,因此情形 A 沒有見證可用。
論證以計數收結,而不是刻劃 。步驟 3 只給出 ,再由拉格朗日定理控制 。情形 B 完全不看 :它的障礙是一個階為 的元素,而 ,因為 而 。
檢驗邊界情形
一個含有情形分割及精心選取指標的證明,應以小例子加以檢驗。以下是各個要素在若干奇合數上的表現。
例題 8.3.3
( 時的質數冪障礙)
。 此時 ,故 ,。模 的單位的平方為 。由於 不是平方數,沒有單位會在階段 或 達到 。所以 ,,。情形 B 適用,取 ,而 。
例題 8.3.4
( 時 CRT 的混合符號)
。 此時 ,故被檢查的階段只有 ,必然 ,。情形 A 適用,取 ,,。CRT 給出 ,因為 且 。於是 ,故 ,它不是 。
。 此時 ,,且有些單位在階段 達到 。所以 ,步驟 3 中「較早階段映為 」的部分便派上用場。見關於 的質數冪的練習。
例題 8.3.5
(包含通過底數但比它更大的子群)
。 此時 ,故 ,。單位要在階段 達到 ,必須同時在模 與模 下都達到。 與 的 部分皆為 ,所以 可以在階段 出現,但不會在階段 或之後出現。事實上 ,故 ,。
- 模 下 的根為 。例如 。所以 。
- 的根為 ,其中 。所以 ,且 。
- 步驟 4 的 CRT 構造,取 ,,,給出 ,因為 且 。於是 ,故 。它具有混合符號,即模 為 、模 為 ,並且不是 。
- 注意 。底數 與 屬於 但不通過:對於 , 且 ,所以 是 的一個非平凡平方根。子群 是 的容器,而不是對 的刻劃。
。 這是配套小節中的卡邁克爾數(Carmichael number)。模 下,單位的任何偶數次冪都是 ,所以沒有單位會在階段 於模 下達到 。因此 ,。情形 A 適用,例如取 與 。見關於卡邁克爾數的強說謊者的練習。
另有兩點補充。
- 若 ,則 ,且 中每個元素都在階段 通過。所以 恰好成立。嚴格包含只可能在 時出現,例如 。
- 情形 A 並不要求 無平方因子。例如 屬於情形 A,取 ,。情形 B 只在 為單一質數的冪時使用。
定理控制的是一輪。完整的測試會以新的底數重複這一輪,上界便隨之相乘。
快速檢查
(以 個從 中獨立、均勻抽取的底數測試奇合數 。求全部 輪都通過的概率的上界。)
一輪用定理,乘積用獨立性。
解答 · 答案
由定理,每一輪通過的概率至多為 ,而這個數小於 。各輪互相獨立,所以全部 輪都通過的概率是乘積,至多為 。獨立性不可缺少:把同一個底數重複用 次,並不比只做一輪更好。
常見錯誤
常見錯誤
(取最後一個被檢查的階段,而不是最後一個達到 的階段)
直接取 似乎很自然。集合 仍然包含每個通過的底數,但不一定是真子群。對 ,有 ,故 。由於 是 、 與 的倍數,每個單位在模 、、 下都滿足 ,因此模 亦然。這個子群就是整個群,甚麼也控制不了。證明用的是某個單位真正達到 的最後階段;情形 A 需要的正是這個見證。
反例模式
強說謊者不一定構成子群
一個看似合理的說法是:合數 的通過底數構成 的子群,就像費馬(Fermat)說謊者一樣(它們是 的核)。對 ,上面的例題已求得 。 與 都通過,但 ,乘積為 。對 ,有 及 ,所以該輪從未遇到 , 不通過。因此 對乘法不封閉。正確的說法正是證明所用的: 包含於子群 ,而拉格朗日定理計算的只是 。
常見錯誤
(把上界讀成「通過的數是合數」的概率)
定理控制的是一個固定合數通過的概率:經過 輪獨立測試後,。它並沒有說通過了 輪的數是合數的概率低於 。這個反向概率取決於輸入是怎樣選出的,例如候選數中質數所佔的比例,須用貝氏(Bayes)定理計算。
練習
快速檢查
(具有 的質數冪:設 。你可以使用以下事實: 是 階循環群,並由 生成。)
(a) 求 與 。然後透過以生成元的指數來求解配套小節中強條件定義的各項條件,精確地確定通過的底數集合 。
(b) 追蹤底數 的一輪。
(c) 如同一半上界的證明,確定 、 與 。分別透過直接計算及二項式公式 ,驗證 位於 之外。
(d) 解釋在階段 通過的兩個底數在階段 時的表現。
解答
(a) 我們有 ,故 ,。該輪檢查 是否為 ,以及 、 是否為 。寫 ,其中 取模 。由於 ,有 。又因 ,有 。
- 表示 ,故 。這給出 。
- 表示 ,故 。這給出 。
- 表示 ,即 。所以 ,得 ,。事實上 ,且 。
- 表示 。模 約化得 ,所以無解。
因此 。底數 在最大公因數步驟即不通過。所以 個底數中有 個通過,在 之內。
(b) 對於 :,故 ,它不是 。在迴圈中, 給出 。所以 ,該輪在階段 通過。
(c) 有些單位,例如 ,在階段 達到 ,而在階段 沒有單位達到。所以 ,。我們計算 。
- 表示 ,即 ,故 ,。
- 已在 (a) 中解出,得 。
所以 ,,是指數為 的子群。對於 :,,且 。二項式公式給出 ,結果一致。由於 ,有 。這用到 ,而這成立是因為 且 為奇數。
(d) 底數 始終保持為 。底數 在階段 為 ,到階段 時變為 。所以在階段 ,階段 的底數處於 ,而階段 的底數 與 處於 。四者都屬於 ,與證明的步驟 3 所預測的完全一致。
快速檢查
(卡邁克爾數的強說謊者:設 ,故 ,。)
(a) 證明沒有模 的單位滿足對 有 。由此推出 且 。
(b) 利用 CRT 以及 是 階循環群這一事實,精確計算 的元素個數。
(c) 將 與上界 以及費馬說謊者的個數作比較。
(d) 如同證明中的情形 A,取 與 ,構造一個明確的單位 ,並計算 。
解答
(a) 模 的單位 也是模 的單位,故 。對 ,指數 為偶數,所以 。若值 ,則約化後會得到模 下的 ,而因 ,這是不可能的。所以 ,,。通過要求 ,而每個這樣的 都在階段 通過。因此 。
(b) 當且僅當該同餘式在模 、 與 下都成立。我們逐個分量計數,並利用以下事實:在 階循環群中,方程 恰有 個解。
- 模 :,因為 為奇數且 。每個符號各有 個解。
- 模 :,因為 。方程 有 個解。對於 ,以生成元 寫 。則 ,而 恰在 為奇數時成立,故有 個解。
- 模 :,因為 。由於 ,立方映射是該群上的雙射,所以 各恰有 個原像。
由 CRT, 有 個解,而 同樣有 個解。這兩個集合不相交,所以 。
(c) ,故上界為 ,而 。通過概率為 。由配套小節的卡邁克爾數例子,全部 個單位都是費馬說謊者。強檢驗因此把說謊者從 個減少到 個。
(d) 使用 ,它滿足 。我們需要 且 。寫 ,並利用 ,需要 。所以 ,。
於是 且 。整數 滿足同樣的兩個同餘式,所以 。這既不是 也不是 ,故 。此外 :它模 及模 皆為 。所以 是 的非平凡平方根,且 。