動機
一個模運算,在若干個較小的模下進行,可能比在一個大模下進行更容易。只有當各局部答案恰好確定唯一一個整體剩餘類時,重構才有意義。中國剩餘定理提供了這個保證,並把貝祖(Bézout)係數轉化為合併部分資訊的算法。
質數檢驗提出的是另一個問題:一個模數是否具備許多模論證所需要的域性質?模恆等式不成立可以證明合數性;恆等式成立則可能只是說明這個特定的底沒有暴露問題。我們會精確地證明兩種檢驗究竟確立了甚麼,而不是把一個必要條件倒轉成沒有依據的質數證書。
上一章的算術內容提供了歐幾里得(Euclid)算法、模逆元與重複平方。
定義
定義 9.1.1
(同餘數據與合數見證)
對於整數 , 表示 。剩餘重構問題是對同一個未知整數給出若干個這樣的條件。質數是恰有兩個正因數的整數 。合數見證是這樣的數據:在某個已陳述的定理之下,其被驗證的性質證明了某個大於一的整數不是質數。某個底通過檢驗,只是意味著沒有得到該指定形式的見證。
定義 9.1.2
(強概率質數條件)
對於奇數 ,唯一地寫成 ,其中 為奇數,。對選定的整數底 ,若 與 有非平凡的最大公因數,則立即得到一個因子。否則令
重複平方可以計算這條鏈。該底的強概率質數條件是:,或者對某個 有 。這裏的等號使用由零至 的標準代表元; 代表負一。通過檢驗被有意地不稱為質數性證明。
定理/命題
定理 9.1.3
(構造性中國剩餘定理)
設 兩兩互質, 為整數剩餘。則模 恰有一個解類。由 出發,對每個新條件 ,計算
並把 同時替換為 。該狀態始終滿足 ,並且恰好表示已處理條件的全部解。
定理 9.1.4
(試除法是確定性的質數檢驗)
整數 是合數,當且僅當它有一個不超過 的質因數。因此,從整數除數 開始,在 時繼續檢驗,就得到一個正確的確定性檢驗。如果檢驗的是所有整數而不只是質數,則至多需要 次試除。
定理 9.1.5
(強條件不成立即證明合數性)
每個奇質數 對每個容許的底都滿足強概率質數條件。因此,若某個底與 的最大公因數為一,且不滿足該條件,則 是合數。若某個中間值 滿足 ,則 是 的非平凡真因子。
證明思路或證明
證明
(合併一個條件)
對於一次 CRT 合併,當前條件恰好給出 ,其中 為整數。新條件變為 。互質性使 在模 下可逆,所以存在唯一的類 。因此合併後的解類是模 的 。由 的界得 。這同時證明了初始化、保持性與唯一性。兩兩互質保證之後的每個乘積都與下一個模互質。
證明透視
合併在哪裏用到互質
這個證明靠參數化把方程組化為一條同餘式:已處理的條件恰好描述 ,於是新條件變成線性同餘式 。互質只用了一次,就是使 在模 下可逆,從而恰好得到一個類 。由於 是先前各模數的乘積,兩兩互質給出 。範圍的界完成論證:。若沒有互質,關於 的同餘式可能無解,也可能有多個類。
證明
(不超過平方根的最小因子)
對於試除法,若 是合數,寫 ,其中 。則 。 的一個質因數也是 的因數,並且不大於 。反之,不大於 的質因數是真因數,從而證明了合數性。整數比較 避免了依賴平方根的浮點近似。
證明
(終於一的平方根鏈)
對於強條件,先回顧質數模下的費馬(Fermat)恆等式。乘以一個非零剩餘會置換非零類,所以把整組非零類相乘,再約去可逆的乘積,便得到 。因此 。若 ,令 為使 的第一個下標。它的前一項平方為一,且不是一。在質數域中, 迫使 或 ,所以那個前一項必為負一。它的下標小於 ,這就確立了強條件。
證明
(由非平凡平方根取出因子)
對於因子的斷言,該同餘式說明 。若 ,則由貝祖約去會迫使 ,與 矛盾。若該最大公因數為 ,則 ,這同樣被排除。因此該最大公因數嚴格介乎一與 之間。這一論證不需要假設合數模是無平方因子的。
證明透視
必要條件有一個有用的逆否命題
質數模滿足強條件,因為它們僅有的一的平方根是正一與負一。因此條件不成立就證明該模是合數。反過來則不成立:合數模可能對某個特定的底模仿所要求的鏈。這個證明解釋的是拒絕,而不是接受之後自動得到證書。
例題詳解
例題 9.1.6
(一次合併保留全部解,而不只是一個猜測)
解 與 。第一次合併之後狀態為 。由於 ,下一個修正量為 。新狀態為 。檢驗得 且 。全部解為 ,其中 ,而不只是所顯示的這個代表元。
例題 9.1.7
(局部計算再重構一個冪)
求 。模七時,六就是負一,得剩餘六。模十一時,費馬定理把指數化為三,得 。由 出發,解 ,得 ,。因此 。這種指數約化在質數座標中是有效的,因為六與兩者都互質;而重構本身保持精確的剩餘,不引入任何數值近似。
例題 9.1.8
(費馬檢驗通過而更強的鏈將其拒絕)
合數 滿足 ,所以 。因此以二為底的費馬檢驗通過並不能證明質數性。對於更強的檢驗,,且 ,而 。所檢驗的鏈中項都不是 ,初始項也不是一,所以強條件不成立。這個非平凡平方根還給出 ,即一個顯式因子。
重構不變量是一個精確的規格
在每次合併時,乘積描述的是已處理的所有條件的完整週期。代表元被保持在標準範圍內,以限制其大小並簡化之後的計算。不需要搜尋最終乘積以下的所有整數,也不需要枚舉局部剩餘的所有組合。每一步所需的那個逆元由歐幾里得算法提供。
以乘積一作為初始化,是空條件列表的內部狀態。每個整數都滿足零個條件,所以其解類是全體整數。第一個真正的模仍然至少為二,而一在該模下的逆元是顯然的。把這一初始化與公開的模的定義分開,就避免了第一次合併時不必要的例外失敗。
該方法可以獨立檢驗:把最終代表元代入每個輸入同餘式。這驗證了構造,而乘積模下的唯一性論證則確立了完備性。僅靠代入並不能證明已描述了全部解。程式可以同時給出其代表元與乘積,使數學規格的這兩部分保持可見。
互質性與表示成本
如果兩個模有公因子,它們施加的資訊會重疊,並且可能互相矛盾。此時乘積一般不是正確的唯一性模。更一般的合併可以使用線性同餘的可解性定理與最小公倍數,但那是另一種約定。上面證明的算法必須檢查其互質性假設,而不是試圖對非單位求逆。
乘積的二進制長度以輸入各模的二進制長度之和為界。這並不使該乘積上的算術成為常數成本。之後的逆元、乘積與約化都作用於不斷增長的整數。重構做線性次數的合併,但位元複雜度的陳述還必須計入算術子程式的成本。每次合併之後保持剩餘有界,可以控制儲存,但並不消除這些算術成本。
一個完全確定的強檢驗
小於二的整數視為非質數,二與三視為質數,更大的偶數以因子二拒絕。對於剩下的奇數,把它減一分解為一個奇因子乘以二的冪。選取一個容許的底,並計算它與該模的最大公因數。介乎一與模數之間的最大公因數已給出因子證書;否則用重複平方求出奇數次冪的值以及隨後的平方鏈。
若初始值為一,或者在最終指數之前所檢驗的任一鏈項為負一,則報告該底通過。若兩者都不出現,則報告合數。當出現一的非平凡平方根時,可以提前停止,並按上述方法提取因子。這些出口意義不同:一個證明合數性,另一個只記錄通過了某個條件。實作應返回不同的狀態,而不應把兩種結果都標成同一個是非定理的答案。
初始的模冪以及至多對數次的平方,利用先前證明的重複平方算法,需要 次模乘法。模乘法與最大公因數的計算仍有各自的位元成本。這裏不聲稱任何概率誤差界。這樣的界需要另一個定理,說明對一個合數模最多有多少個底能通過,而不是僅僅重複執行必要條件的證明。
為甚麼試除法仍值得理解
試除法有簡單而完整的正確性論證,並且在拒絕時給出一個除數。它的局限在於其成本取決於數值的平方根,而不是輸入的二進制長度。質數輸入會使迴圈檢驗直至該閾值的每個候選者,相對於位數而言這可能極其巨大。但這個方法對於小的輸入,以及在應用其他方法之前去除小因子,仍然有用。
更快的拒絕檢驗與完整的確定性質數性證明是不同的目標。強條件對許多輸入給出高效且在嚴格意義上有依據的拒絕,但一個底通過並不能解決所有輸入。試除法在精確算術之下最終能解決每個整數,但所需工作量可能大得多。學生應當先弄清一個算法證明了甚麼,再比較它的速度。
概念視角算法
證書、檢驗與重構回答的是不同的問題
CRT 證明局部的值描述了唯一一個整體剩餘類。非平凡的最大公因數證明了一個因子。強鏈不成立證明質數域中的某個蘊含已被破壞。鏈通過則是較弱的結果,在成為質數性保證之前還需要額外的數學。把這些輸出區分清楚,可避免把算法未曾證明的結論當成它的保證。
常見錯誤
強檢驗「通過」是最常被誤讀的結果。
反例模式
即使強檢驗通過也不是質數證書
取 ,底為九。由於 且 ,初始鏈值為 。這個底通過了強條件,儘管該模是合數。修正後的結論是:拒絕證明合數性;對某個特定底的接受並不是質數定理的逆命題。
常見錯誤
(試除迴圈停在平方根邊界之前)
試除迴圈必須包含相等情形 。對 ,唯一的質因數是 ,而 。若用嚴格的 ,迴圈在 便停止,並錯把 判為質數。排除邊界會漏掉質數的平方。
常見錯誤
(把指數按模數約化)
不要把指數按值所在的模來約化。指數週期需要經過論證的定理及單位假設,而重複平方不需要這樣的約化。模 時 ,但把指數 模 約化為 後,,結果是錯的。
反例模式
兩個同餘式未必有公共解
聲稱:任何兩個同餘式都有解,而且解在模數乘積之下唯一。取 與 。第一式迫使 為奇數,第二式迫使 為偶數,所以沒有整數同時滿足兩式。這裏 不整除 。修正:設 ,解存在恰好當 整除兩個餘數之差,而且此時解在模 下唯一;若模數互質則 ,便得到所述的定理。
總結
CRT 利用一個逆元和一個維持的週期來合併精確的局部資訊。試除法給出完整的確定性判別準則,其數值成本為平方根量級。強合數見證利用質數域的平方根性質,給出嚴格的拒絕;對其接受狀態,必須按照定理實際的量詞來解讀。
練習
快速檢查
(對 取底 3 應用強條件,若出現非平凡平方根,則求出一個因子。)
利用 。
解答 · 答案
此處 ,所以 。由於 ,,既不是一也不是九十。在 之前沒有其他需要檢驗的下標,所以這個底拒絕。而且 , 給出一個因子。與底為九時的結果不同,這與依賴於底的必要條件是一致的。
快速檢查
(解 與 。說明為何模乘積的唯一性不成立。)
使用線性同餘定理,而不是使用不存在的逆元。
解答 · 答案
寫 。另一個條件給出 ,即 ,從而 。因此 。模六十的兩個不同的類十三與四十三都是原方程組的解。這些模並不互質;它們的 lcm 是三十,所以乘積模的唯一性斷言是錯誤的。
快速檢查
(說明為何對 ,試除迴圈必須檢驗 11。然後利用質因數定理證明 127 是質數。)
列出不超過相關平方根的每個質數。
解答 · 答案
合數 沒有小於十一的質因數,所以嚴格不等號會漏掉它唯一的質因數。對於 ,不超過其平方根的質數候選者是 。它們各自的餘數為 ,全都非零。不存在不超過平方根的質因數,所以該定理證明了質數性。