使用者:Gqqnb/筆記/計算機安全與數論
整係數二元一次方程之整數解、最大公約數、歐幾里德算法[編輯]
通常談到最大公因數時, 我們都會提到一個非常基本的事實: 給予二整數 a 與 b, 必存在有整數 x 與 y 使得ax + by = gcd(a,b)。[1]
有兩個數a,b,對它們進行輾轉相除法,可得它們的最大公約數——這是眾所周知的。然後,收集輾轉相除法中產生的式子,倒回去,可以得到ax+by=gcd(a,b)的整數解。
例如,用類似輾轉相除法,求47x+30y=1的整數解。
- 47=30*1+17
- 30=17*1+13
- 17=13*1+4
- 13=4*3+1
然後把它們改寫成「餘數等於」的形式
- 17=47*1+30*(-1) //式1
- 13=30*1+17*(-1) //式2
- 4=17*1+13*(-1) //式3
- 1=13*1+4*(-3)
然後把它們「倒回去」
- 1=13*1+4*(-3) //應用式3
- 1=13*1+[17*1+13*(-1)]*(-3)
- 1=13*4+17*(-3) //應用式2
- 1=[30*1+17*(-1)]*4+17*(-3)
- 1=30*4+17*(-7) //應用式1
- 1=30*4+[47*1+30*(-1)]*(-7)
- 1=30*11+47*(-7)
得解x=-7, y=11。
這個方法疑似就是擴展歐幾里德算法。
模運算[編輯]
例題1:試求同餘方程 x + 11 ≡ 7 (mod 17) 的解。
解:x ≡ 7 - 11 ≡ -4 ≡ 13 (mod 17) 。 答案若寫成負的並沒什麼錯誤。 但當我們在模 n 之下工作時,通常將最後的答案表示為介於 0 與 n - 1 之間的整數。
除法原理:在模 n 下,若要兩邊同除以某數,該數須與 n 互質。
例題2:試求同餘方程 4x + 11 ≡ 7 (mod 17) 的解。
解:4x ≡ 7 - 11 ≡ -4 (mod 17), 所以 x ≡ -1 ≡ 16 (mod 17)。 被 4 除沒問題, 因為 gcd(4,17) = 1。
例題3:試求同餘方程 3x +12 ≡ 17 (mod 21) 的解。
讀者可以自行嘗試一下,再繼續看本文。這些同餘方程可以轉化為整係數二元一次方程之整數解的問題。
- 3x +12 ≡ 17 (mod 21)
- => 3x+12=17+21y
- => 3x+21y=5 (y的正負無所謂)。
讀者可能還沒試到解,其實,貝祖等式說因為3和21的最大公約數是3,不是2的倍數,所以此方程無解。
同餘方程的線性表示[編輯]
對於任意的同餘方程a ≡ b (mod n),都有 (根據定義,a,b同餘,m就是它們在模n下的餘數),然後a-b=(x-y)n => a-b=kn。
例題4:試求同餘方程 5x + 7 ≡ 11 (mod 17) 的解。
解:5x ≡ 4 (mod 17)。兩邊可以除以5,因為5和17互質。但在模 17 之下是什麼意思呢? 我們知道 4 ≡ 21 ≡ 38 ≡ 55 ≡ ··· (mod 17), 所以 5x ≡ 4 (mod 17) 與 5x ≡ 55 (mod 17) 是一樣的。恰好55又是5的倍數,所以現在我們可除以 5 得到 x ≡ 11 (mod 17) 為其答案。 注意 4 ≡ 11* 5 (mod 17), 所以在模 17 之下 11 就如同是一樣。到了這裡,就可以引入模反元素這個概念了。
模反元素[編輯]
例題4也可以這麼算:不知怎麼的,我們知道了5 * 7 ≡ 1 (mod 17)。就如同,是5的乘法逆元一樣,我們把7稱為5在模17下的模反元素。
疑似模反元素可以為負數,只要絕對值小於模就可以了(可以參考餘數的範圍);但人們往往喜歡把它「正過來」。
求模反元素[編輯]
已知a,求a在模b下的模反元素。
設有ax ≡ 1 (mod b),然後把它寫成線性方程 ax-1=by => ax+by=1。
已知擴展歐幾里德算法可求形如ax+by=1的方程的整數解,於是ExtendedGCD(a,b)={1,x,y},得模反元素為x。