動機
勒讓德(Legendre)符號用於檢測模質數下的平方數,但它的定義本身已假定分母為質數。雅可比(Jacobi)符號把算術互反律的規則推廣至每個正奇數分母。它的定義用到質因數分解,但憑藉互反律,我們可以在不求出這些質因子的情況下計算它。
這個分別在計算上很有用,在概念上卻很危險。雅可比符號取值為一,並不能證明它是模合數的平方;符號被快速算出,也不能證明分母是質數。我們將證明精確的規則,在算法中維持一個帶符號的不變量,並準確指出其輸出究竟能確立甚麼。
本章使用前面的質數二次互反律及其補充定律、唯一分解定理、歐幾里得(Euclid)餘數與最大公因數。輸入要求中並未暗含任何質數判定或因數分解算法。本章所有分母都是正奇數;推廣至偶數分母的克羅內克(Kronecker)符號不在本章範圍之內。
定義
定義 6.3.1
(不以因數分解為輸入的因數分解式定義)
對奇數 ,設其質因數分解為 ,定義
右邊的符號是勒讓德符號。對每個整數 (包括 ),規定 。雅可比符號為 當且僅當 ;否則它等於 或 。它只依賴於 模 的剩餘類,並且對分子具有乘性。它對奇數分母亦具有乘性,而且不要求兩個分母因子互質。
該記號是數學記號,而不是有理數的商。在分母為質數時它就是勒讓德符號;在分母為合數時,它把各質數處的結果連同重數組合在一起,因而可能損失資訊。
概念視角組合
符號即一個置換的符號
對奇數 及 ,乘以 置換模 的剩餘,而雅可比符號等於這個置換的符號;此處只陳述這個描述,不作證明。對 、,循環為 、、、 和 。四個偶數長度的循環給出符號 ,與 相符。這個描述同樣不需要分解,但要處理全部 個剩餘,工作量遠多於歐幾里得算法。
定理
定理 6.3.2
(奇數分母的互反律及兩條補充定律)
對每個正奇數 ,
對互質的正奇數 ,
更一般地,重排後的規則
對所有正奇數 都成立:當它們有公因子時,兩邊都是零。
定理 6.3.3
(帶符號的歐幾里得算法可計算該符號)
對任意整數 與正奇數 ,下列算法返回 。先將 模 約化,令 ,當 時重複以下步驟:
- 將 寫成 ,其中 為奇數。若 為奇數且 或 ,則把 換成 。
- 若 ,則把 換成 。
- 將 替換為 。
終止時,若 則返回 ,否則返回 。每連續兩次非終止迭代,模數至少減半,因此在初始約化之後共有 次迭代。對於 位元的已約化輸入,採用普通的小學算術, 次位元運算是一個有效的保守界。若初始分子更長,則其約化的代價須另行計入。
證明思路
證明
(由質數互反律得到奇數分母互反律)
剩餘性質與乘積規則。 每個質因子對應的勒讓德符號都具有剩餘性質與乘性,因此它們的乘積亦具有這些性質。若存在公因子,則至少有一個勒讓德因子為零;若不存在公因子,則每個因子都是 。奇數分母相乘就是把它們的質數指數相加,所以即使兩個分母的分解有重疊,分母乘性仍然成立。
補充定律。 對奇數 ,
由於 ,這是偶數。所以 的奇偶性等於 與 各自對應量的奇偶性之和。將各質數關於 的補充定律按重數相乘,便得到 。同樣,
是偶數,因為 且 。將各質數關於二的補充定律相乘,便得到 。這些論證同樣適用於質數冪的情形;若把分母當作無平方因子數處理,就會得到錯誤的符號。
互反律。 設 與 互質。每一對交叉的質數貢獻 次質數互反律的符號,總奇偶性為
由奇數乘積的奇偶性恆等式,這兩個因子模 分別與 和 同餘。於是互反律得證。若某個質數同時整除 與 ,則兩個雅可比符號均為零;這就給出了算法所需的重排規則,而無須事先知道最大公因數。乘積形式的陳述仍須保留互質假設:兩個零符號之積並不等於所示的符號。
證明
(帶符號歐幾里得算法的正確性)
在每一階段,不變量是
其中 是原來的輸入,而 是奇數。初始約化保持該不變量,因為符號只依賴於 模 。去掉 相當於把當前符號乘以 ,這正是第一次符號更新。重排後的互反律給出 ,其符號就是第二次符號更新;而 給出新的數對。無論是否存在公因子,這些步驟都保持不變量,而且新分母 仍是奇數。
約化之後 ,所以當前分母嚴格遞減,循環必以 終止。對 ,;對 ,按空積約定它為 。這就證明了返回規則。最大公因數亦保持不變:因為 是奇數,,而 。因此最終的 等於 ;零的結果並不是某個未完成計算中遺留下來的部分符號。
證明透視
奇數性、零規則與不變量各在何處使用
證明從不直接計算該符號;它一直攜帶「原來的符號等於 乘以當前符號」這條等式,只改變當前數對。三個假設在特定位置被使用。當前分母為奇數,才使兩條補充定律與互反律可以應用,亦使去掉二的因子不影響最大公因數;算法只把奇部 移入分母,從而維持這一點。第二次符號更新用的是在最大公因數大於一時仍然成立的重排互反律;互質的乘積形式需要預先知道最大公因數,而這正是算法尚未算出的東西。最後,關於二的補充定律要讀取當前分母,因為不變量談的是當前符號。
論證在 處閉合,此時兩件事相遇:空積約定在分母為一時給出值一,而最大公因數的保持說明終止時的分母就是原來的最大公因數。缺少後者,返回的零便無從解釋。整個過程從不索取輸入的質因子,所以快速求值並不是質數證書或平方根證書。
證明
(迭代次數與位元開銷界)
約化之後,正的分子小於分母 ,其奇部 亦然,而 就是下一個分母。若 ,一次迭代便使分母減半。否則 ;若它為零,算法停止;若不為零,再下一個分母是它的奇部,至多為 。因此每兩次迭代分母至少減半,而多去掉的二的因子只會使它更小。
設初始約化後的分母有 位元,則迭代次數為 。讀取模 或模 的餘數以及剝去末尾零位元只需 次位元運算,而不超過 位元的兩數之間的小學式帶餘除法代價為 。由此得到總計 的界。這是一個保守的、已證明的界,並不是對快速算術下最優性的斷言。若分子的位元數遠多於 ,則其初始模約化必須另行計入;僅以 表示的代價界會遺漏輸入的一部分。
例題詳解
例題 6.3.4
(不分解分母的多步求值)
對 ,相繼得到的已約化數對為
偶數分子 貢獻一個因子二,而分母 ,所以符號不變。沒有任何一次互反律交換中的兩個奇數參數同時模 餘 。在數對 處,去掉三個因子二會使符號改變,因為 。最後的奇數分子為 ,得到最終數對 。因此該符號等於 。餘數的檢驗包括 與 ;計算中既沒有使用亦沒有斷言 的任何因數分解。
例題 6.3.5
(公因子由終止時的分母檢測出來)
對 ,第一次交換時 ,符號不變,得到 。去掉一個因子二會使符號改變,因為 ,留下的奇部為 。下一個餘數是 ,所以終止時的分母為 。返回值為 ,與公因子 一致。
中間的符號為負,但它要與終止時的零符號相乘。若只返回該符號,就會把一個部分不變量誤當作答案。該算法無須先對任何一個整數作因數分解,便能檢測出非平凡的最大公因數。
例題 6.3.6
(雅可比值為一並不是平方證書)
對 ,由質因子得 與 ,因此兩者之積為 。然而 並不是模 的平方,因為模 約化後需要一個模 餘 的平方數。等價地,互反律給出 。
損失的資訊是各質數處分別的符號:兩個負的結果相乘得到正的結果。對於奇數平方分母,這種損失更為明顯:每個與分母互質的分子,其符號都是 ,因為每個質數的指數都是偶數。質數檢驗必須把該符號與額外的模冪資訊作比較,而不能把它當作單獨的判決。
常見錯誤
反例模式
互質時的乘積形式不能用於有公因子的情形
取 ,則兩個雅可比符號之積為零,而互反律中的符號為負一,因為兩數模四都餘三。這並不矛盾:那條乘積等式要求互質。重排後用於算法的規則讀作「零等於帶符號的零」,仍然成立。只有當這些符號都是非零的符號時,這兩種寫法才等價。
常見錯誤
(用最初的分母讀取關於二的補充定律)
去掉因子二時的符號取決於當前分母模 的餘數。在 中,因子二是在數對 處去掉的,而 ,符號不變。若改用 ,便會把符號翻轉而返回 ,正確值卻是 。二的因子只從分子中去掉;分母始終保持為奇數。
常見錯誤
(終止分母大於一時仍返回累積符號)
約定 只適用於分母為 的情形。若循環終止於 且 ,則無論 是甚麼,答案都是 ;在 中累積符號是 ,但該符號等於 。
快速檢查
快速檢查
(若算法輸出 ,原來的分子是否必定模 為 ?)
解答 · 答案
不必。輸出 表示終止時的分母,即 ,大於 。取 、,輸出為 ,但 ;最大公因數是 。
快速檢查
(若輸出為 且 , 是否必定有模 的平方根?)
解答 · 答案
不必。,但 不是模 的平方,因此亦不是模 的平方。兩個負的質數符號相乘得到 。
練習
練習 6.3.7
(用該算法求 ,並交代每一次符號更新與剩餘約化。)
基礎
解答(3)
- 1
約化並作第一次交換
。由於 是奇數且 ,符號不變,下一個數對是 。
- 2
去掉因子二並交換
,且 ,所以關於二的補充定律為正。此時 ,故 ,下一個數對是 。
- 3
完成循環
給出 與數對 ,然後是 。答案為 ,與 一致。
練習 6.3.8
(證明:對奇數 ,當 時 ,否則為 。並給出一個模 下與 互質的非平方例子。)
核心證明
解答(3)
- 1
按因數分解寫出平方分母
若 ,則 ,所以 。
- 2
利用每個指數都是偶數
關鍵一步
若 ,每個勒讓德因子都是 ,其偶次冪為 。若 ,則某個 ,給出一個零因子。
- 3
給出例子
∎模 的單位平方數是 。所以 與 互質且 ,但它不是模 的平方。
練習 6.3.9
(在下一個奇數分母 大於舊分母 一半的情形下,驗證「兩次迭代減半」的論證。為何去掉二的因子不會破壞該界?)
核心證明
解答(3)
- 1
計算下一個餘數
。
依據: 迫使商為 。
- 2
再跟進一次迭代
若 ,算法已經終止。否則再下一個分母是 的奇部,至多為 。
- 3
計入去掉的二的因子
∎去掉二的因子是把一個數換成它的一個因數,所以只會使下一個分母變小。至多兩步之後,原來的大小便減半。
練習 6.3.10
(說明分母的因數分解如何驗證雅可比符號的計算、為何尋找它不是算法的一步,並由輸出 給出一個有效結論和一個無效結論。)
綜合
解答(3)
- 1
以因數分解作獨立檢驗
給定 ,可以把勒讓德符號 相乘;這是按定義重新計算同一個量。
- 2
為何算法不需要它
關鍵一步
帶符號的不變量只使用已證明的互反律、補充定律與歐幾里得餘數,所以從不索取質因子。
- 3
有效與無效的結論
輸出 說明 不是模 的平方:與 互質的平方會使每個勒讓德因子都等於 。它並不說明 是質數;例如 ,而 是合數。
解答與相關筆記
各題解答已附於上面的練習中。本章給出了完整的奇數分母雅可比互反律及一種已證明的求值方法。克羅內克符號、歐拉(Euler)—雅可比概率質數檢驗以及高級的位元複雜度算法需要進一步的論證。