整數算法可以處理極其龐大的數值,卻不必遍歷所有更小的整數。這是因為餘數保留了我們所需的整除資訊,而一個二進制位可以描述一大段重複的乘法。關鍵的技巧是辨明每次壓縮之後究竟保留了甚麼。我們將對歐幾里得(Euclid)算法使用公因數不變量,對模冪運算使用乘積不變量,然後考察它們的緊湊描述實際需要多少運算量。
動機
假設某個程式必須求解 17x≡1(mod43)。在這裏逐一檢驗全部四十三個剩餘類可以得到答案,但這既無法解釋為何解存在,也無法處理數百位的模數。最大公因數的計算則兩者兼顧:它的餘數揭示逆元是否存在,而它的代入過程把逆元作為一個證書給出,只需一次乘法和一次取餘便可檢驗。
同樣地,若透過把 a 恰好乘 e 次來計算 ae,就忽略了 e 是如何被給出的。一個有 k 個二進制位的指數可能接近 2k。於是長度為 e 的迴圈相對於輸入中這一部分的長度而言是指數級的。重複平方法逐位處理指數的各個數字,從而只需關於 k 為線性次數的模乘法,就能得到同一個數學上的冪。
這些都是精確的整數算法。它們的證書表達的是等式與整除關係,不含任何數值容差。這使它們與下一章的近似保證形成有益的對照。精確並不表示算術是免費的:即使我們把兩個長整數的乘法寫成一個乘積,它也涉及許多位運算。
定義
對於整數 d,a,記號 d∣a 表示存在整數 c 使得 a=dc。對於不全為零的非負整數 a,b,它們的最大公因數 gcd(a,b) 是同時整除兩者的最大正整數。對 a>0,我們約定 gcd(a,0)=a。對於任意正負號的整數,應先取絕對值,再應用非負整數的算法。
對於整數 a 與 b>0,帶餘除法給出唯一的整數 q,r,使得 a=qb+r 且 0≤r<b。歐幾里得算法(輾轉相除法)從一個非負數對 (a,b) 出發,當 b>0 時反覆把它替換為 (b,amodb)。當第二個座標變為零時,其輸出為第一個座標。
固定模數 m≥2。同餘式 a≡b(modm) 表示 m∣(a−b)。每個剩餘類可以由 0,1,…,m−1 之一作為規範代表。a 的模逆元是滿足 au≡1(modm) 的整數 u。當逆元存在時,唯一的是 u 所在的剩餘類;整數 u,u+m,u−m 是同一個逆元類的不同代表。
我們考慮的模冪運算以整數 a 為底、非負整數 e 為指數,且 m≥2。指數為零的約定是 a0=1,在這個代數計算中底為零時亦然。負指數需要逆元,不在此輸入規格之內。輸入長度指編碼後的整數的二進制位數,並在需要時計入固定的分隔符與正負號。
定理/命題
定理 5.1.1
(歐幾里得算法計算最大公因數與 Bézout 證書)
對於不全為零的非負整數 a,b,歐幾里得算法會終止並返回 d=gcd(a,b)。存在整數 s,t 使得 sa+tb=d。這樣的係數可以透過記錄並代入各步除法來計算,也可以在更新各個餘數的同時更新相應的係數對來計算。
整數 a 在模 m≥2 下有逆元,當且僅當 gcd(a,m)=1。更一般地,同餘方程 ax≡c(modm) 有解,當且僅當 d=gcd(a,m) 整除 c。在有解的情形下,它在模 m 意義下恰有 d 個互不相同的解類。
初始化 r=1,b=amodm,q=e。當 q>0 時,若 q 為奇數,則把 r 模 m 乘以 b;把 b 替換為 b2modm;並把 q 替換為 ⌊q/2⌋。終止時,r 是 ae(modm) 的規範代表。當 e 有 k 個二進制位時,該過程使用 O(k) 次模乘法;指數為零時不需要任何乘法。
最後一個定理中各條指令的次序至關重要。奇數情形的更新使用的是舊的 b,即在對它平方之前。亦可以作為優化而省去最後一次不被使用的平方,但下面的證明針對的是所陳述的過程。依據一個確切的賦值序列來書寫不變量,可以避免含糊的算法獲得一個看似嚴謹的證明。
證明思路或證明
證明
(歐幾里得算法:不變量、終止與 Bézout 證書)
若 a=qb+r,則一個整數整除 a,b 兩者,當且僅當它整除 b,r 兩者。一個方向用到 r=a−qb,另一個方向用到 a=qb+r。因此,歐幾里得的每一步更新都保持全部公因數構成的集合不變,從而亦保持其中最大的正元素不變。當第二個座標為正時,它嚴格遞減,所以由良序原理可知算法終止。在最終數對 (d,0) 處,最大公因數是 d,這就證明了正確性。
每個初始座標都是原始輸入的整數組合:a=1a+0b 且 b=0a+1b。每當兩個餘數是這樣的組合時,把其中一個乘以商後再相減,所得的差亦是這樣的組合。因此最後一個非零餘數具有 sa+tb 的形式。這是證書的一個構造性證明,而不是斷言適當的係數「總會存在」。要實作它,為當前的兩個座標各儲存一個係數對,並對這些係數對施行同樣的減法。
概念視角結構
最大公因數是所有整數組合的生成元
設 a,b 不全為零,則集合 {sa+tb:s,t∈Z} 對加法和取負都封閉,所以它恰由其最小正元素的全部倍數組成。這個元素同時整除 a 和 b,又是它們的組合,因此每個公因數都整除它:它就是 gcd(a,b)。用這個描述來看,a 在模 m 下可逆,當且僅當 1 是 a 與 m 的組合。
若 au+mv=1,則模 m 約化得 au≡1。當最大公因數為一時,Bézout 恆等式提供了這樣的 u,v。反之,若有逆元,則存在整數 v 使得 au−1=mv,所以 a,m 的每個公因數都整除一。這就在兩個方向上證明了逆元存在的判別準則。
對於一般的同餘方程,任何解都給出 ax−c=mv,所以 d 必須整除 c。當它整除時,把整數等式除以 d,得到
(a/d)x≡c/d(modm/d).兩個新的係數 a/d 與 m/d 互質,所以在模 m/d 下恰有一個解類。若 m/d=1,這只是說每個整數都滿足約化後的同餘式;此時不需要模數為一的逆元定理。無論哪種情形,代表該類的整數在模 m 下恰好分裂為 d 個類,可用 x0+j(m/d)(0≤j<d)作代表。所列出的互異代表之差小於一個完整的模數,因而不可能同餘。每個解都與其中之一同餘。
對於重複平方法,維持
rbq≡ae(modm).它在初始時成立。把舊指數寫成 q=2h+ε,其中 ε 為零或一。更新後的狀態為 r′=rbεmodm,b′=b2modm,q′=h,所以 r′(b′)q′≡rb2h+ε=rbq。因此不變量得以保持。非負的指數不斷減小直至為零。此時它的冪貢獻為一,留下 r≡ae;每次乘法之後做約化,使 r 保持規範形式。
證明透視
保留資訊,縮減參數
歐幾里得算法在使餘數減小的同時保持公因數集合不變。重複平方法在縮短指數的同時保持乘積不變。在每個證明中,資訊的保持確立部分正確性,而遞減的參數確立終止性。僅有遞減的參數只能說明程式會終止;一個很快返回錯誤答案的程式同樣可能具有遞減參數。
例題詳解
例題 5.1.4
(一次最大公因數計算同時回答了一個不可能性問題)
計算 252=1⋅198+54,198=3⋅54+36,以及 54=1⋅36+18,隨後是 36=2⋅18。最大公因數為十八。反向代入得 18=54−36=4⋅54−198=4⋅252−5⋅198。這個恆等式無需重複搜尋便可檢驗結果。它還證明了 252x≡1(mod198) 不可能成立:十八整除左邊的每個值以及模數,卻不能整除一。
對於 17 與 43,除法為 43=2⋅17+9,17=9+8,9=8+1。因此 1=9−8=2⋅9−17=2⋅43−5⋅17。係數負五給出模 43 的逆元類 38,並且 17⋅38=646=15⋅43+1。對於另一個同餘方程,6x≡8(mod14) 除以最大公因數二後化為 3x≡4(mod7)。由於三在模七下的逆元是五,故 x≡20≡6(mod7)。模十四的兩個解是六和十三。檢驗可知,36 與 78 的餘數都是八。
要計算 713mod23,使用 13=8+4+1。逐次平方得到的剩餘是 7、3、9 和 12,分別對應一次、二次、四次和八次冪。把所選的剩餘相乘,得 7⋅9⋅12=756≡20(mod23)。按所陳述的迴圈,狀態 (r,b,q) 初始為 (1,7,13),接著依次是 (7,3,6)、(7,9,3)、(17,12,1) 和 (20,6,0)。不變量解釋了為何跳過偶數指數時的乘法不會損失任何資訊。b 的最終值六並未被使用,所以實作中可以省略最後一次平方。
要分析歐幾里得算法,首先安排 a≥b>0,並設兩個輸入至多有 L 位。每兩個餘數步驟,正的餘數至少縮減為原來的一半。事實上,對於連續的正餘數 u>v>r,若 v≤u/2,則縮減已經發生;否則商為一,於是 r=u−v<u/2。因此共有 O(L) 次除法。若採用普通長除法,每次為 O(L2) 次位運算,則保守的上界為 O(L3)。這是一個有效的多項式上界,並不聲稱是實作所能達到的最優界。
對於模冪,設底數已經按一個 L 位的模數約化。剩餘至多有 L 位,乘積至多有 2L 位。直式乘法再加長除法,每次模乘法的代價為 O(L2) 次位運算。因此 k 位的指數使主迴圈需要 O(kL2) 次位運算,前提是透過移動索引逐位讀取指數,而不是反覆複製整個剩餘商。讀入並首次約化一個長得多的底數,還需要取決於該底數長度的額外代價。儲存常數個剩餘所需的空間為 O(L) 位;若明確保留指數,則另需 O(k) 位。
常見錯誤
反例模式
消去不可逆的因子
一條誘人的規則說:由 cx≡cy(modm) 可推出 x≡y(modm)。取 c=2,m=6,x=1,y=4:cx=2,cy=8≡2(mod6),所以假設成立,但 x−y=−3 不能被六整除。當 gcd(c,m)=1 時規則成立,因為乘以 c 的逆元保持等價性。一般地,設 d=gcd(c,m),寫 c(x−y)=mk 並除以 d:互質的 c/d 與 m/d 迫使 m/d∣x−y,所以消去只能給出 x≡y(modm/d)。此例中 1≡4(mod3)。
擴展歐幾里得算法給出的逆元係數可能為負;在 17 與 43 的例子中它是 −5。把它約化到 0,…,m−1(此處為 38)改變的是其代表,而不是其剩餘類。各種程式語言對帶正負號餘數的約定不同,所以當輸入可能為負時,應當明確地實作數學上的規範餘數。
一個迴圈迭代 e 次,並不會僅僅因為迴圈變量被稱為指數就成為關於 log2e 的多項式。反過來,統計出 O(loge) 次乘法,也不能說明計算完整的整數 ae 只需關於輸入長度的多項式空間:該完整輸出可能有指數多位數字。在這裏,是模約化使中間值保持有界。
總結
餘數保留公因數並使歐幾里得算法終止;追蹤它們的線性組合則產生可檢驗的 Bézout 恆等式。該恆等式刻劃了模逆元,並解決所有線性同餘方程。重複平方法在消耗指數位的同時保持一個乘積不變量。一旦明確陳述所保留的資訊、輸入編碼與算術模型,正確性與效率都會變得更加清晰。
練習
練習 5.1.7
(計算 gcd(99,78),並求整數 s,t 滿足 99s+78t=gcd(99,78)。)
核心
解答(3)
1逐步做除法
99=78+21,78=3⋅21+15,21=15+6,15=2⋅6+3,6=2⋅3。最後一個非零餘數是 3。
2反向代入
3=15−2⋅6=3⋅15−2⋅21=3⋅78−11⋅21=14⋅78−11⋅99。
3寫出證書
最大公因數為三,一組係數為 (s,t)=(−11,14);確實 −1089+1092=3。
快速檢查
(求解 9x≡6(mod15),列出模十五的每一個解類。解釋為何 9x≡4(mod15) 無解。)
解答 · 答案
最大公因數為三,故除以它得 3x≡2(mod5)。三的逆元是二,因此 x≡4(mod5)。它在模十五下的三個類是四、九和十四。第二個同餘式不可能成立,因為三不整除四。
快速檢查
(透過逐次平方的剩餘計算 311mod17,並陳述指數為零時的不變量。)
解答 · 答案
一次、二次、四次和八次冪對應的剩餘是 3,9,13,16。由於 11=8+2+1,答案為 16⋅9⋅3≡7(mod17)。當 q=0 時,不變量寫作 r≡311(mod17),所以返回的規範剩餘是七。
快速檢查
(某個擬議的實作在應用奇數情形的乘法之前先對 b 平方。證明它在指數為一時失敗,並說明如何修復。)
解答 · 答案
從 (1,amodm,1) 出發,先平方會使奇數情形的更新使用 a2 而不是 a。取 a=2,m=5,錯誤的答案是四而不是二。應當在奇數更新中使用舊的底數,或者為一個刻意不同的算法另行推導不同的不變量。
快速檢查
(當指數為 2k 時,比較重複乘法與重複平方法。區分指數的數值與其二進制編碼長度。)
解答 · 答案
重複乘法使用約 2k 次乘法。重複平方法使用約 k 次;2k 的編碼有 k+1 位。在做模約化的情況下,每次乘法的代價亦是關於模數長度的多項式。若不做約化,則必須另行計入不斷增長的輸出規模。