密碼學——第4章-數論與有限域基礎(編輯修改稿)
2024-09-01 05:48 本頁面
【文章內容簡介】 此外還有以下性質： ?加法可約律 ： 如果 (a+b)≡(a+c) mod n， 則 b≡c mod n ?該性質可由 (a+b)≡(a+c) mod n 的兩邊同加上 a 的加法逆元得到。 ?類似性質對乘法卻不一定成立 。 ?仔細觀察可見，與 8 互素的幾個數 1， 3， 5， 7 都有乘法逆元 。 這幾個數有什么特點呢？ ?這 一結論可推廣到任一 Zn。 數論基礎 ?模運算 ? 定理 ： 設 a∈ Zn， gcd(a, n) = 1，則 a 在 Zn 中有乘法逆元。 ? 證明： ?首先 ，集合 a Zn = {0, a, 2a, …, ( n1)a} (mod n) 與集合 Zn 等價： 1) n。 2) ia mod n ≠ ja mod n, iff i ≠ j, i,j ∈ Zn ?然后，存在 x ∈ Zn，滿足 ax ≡ 1 mod n 數論基礎 ?模 運算 (小結 ) ? 加法 ： a+b mod n = (a mod n) + (b mod n) mod n ? 減法 ： ab mod n = a+(b) mod n ? 乘法，重復加法 ： a b mod n = (a mod n) (b mod n) mod n ? 除法 ：（乘法約簡律） a/b mod n = a b1 mod n ? 注意： b1 是 b mod n的乘法逆元，存在的條件是 gcd(b, n) = 1 數論基礎 ?歐幾里得 (Euclid) 算法 ? 數論中的一個基本技術：求兩個正整數的最大公因子的簡化方法。 ? 擴展 Euclid 算法不僅可以求出兩個正整數的最大公因子，而且當兩個正整數互素時，還可求出其中一個數關于另一個數的乘法逆元。 數論基礎 ?歐幾里得 (Euclid) 算法 ? 求最大公因子 ?Euclid 算法基于以下基本結論： 對任意非負整數 a 和正整數 b，有 gcd(a, b) = gcd(b, a mod b) ?課堂練習題：證明上述命題。 數論基礎 ?歐幾里得 (Euclid) 算法 ? 求最大公因子 ?Euclid(f, d)： 設算法 的輸入是兩個 非負整數 f, d，并 且 f d Euclid(f, d) { X← f。 Y← d； : if Y=0 then return X=gcd(f, d)； R=X mod Y； X=Y； Y=R； goto 。 } ?歐幾里得 (Euclid) 算法 ? 求最大公 因子例子， gcd(1970, 1066) ? 1970 = 1 x 1066 + 904 gcd(1066, 904) 1066 = 1 x 904 + 162 gcd(904, 162) 904 = 5 x 162 + 94 gcd(162, 94) 162 = 1 x 94 + 68 gcd(94, 68) 94 = 1 x 68 + 26 gcd(68, 26) 68 = 2 x 26 + 16 gcd(26, 16) 26 = 1 x 16 + 10 gcd(16, 10) 16 = 1 x 10 + 6 gcd(10, 6) 10 = 1 x 6 + 4 gcd(6, 4) 6 = 1 x 4 + 2 gcd(4, 2) 4 = 2 x 2 + 0 gcd(2, 0) 數論基礎 ?歐幾里得 (Euclid) 算法 ? 求乘法逆元 ?如果 gcd(a, b) = 1 ，則 b 在 mod a 下有乘法逆元（不妨設 ba），即存在 x (xa)， 使得 bx≡1 mod a。 ?擴展 Euclid 算法可求 出 gcd(a, b)，當 gcd(a, b) = 1，還得到 b 的逆元。 數論基礎 ExEuclid(f, d) { //設 f d (X1, X2, X3)←(1, 0, f)。 (Y1, Y2, Y3)←(0, 1, d)。 : if Y3=0 then return X3=gcd(f, d)； no inverse。 if Y3=1 then return Y3=gcd(f, d)； Y2=d1 mod f。 Q=X3/Y3 ； (T1, T2, T3)←(X 1QY1, X2QY2, X3QY3)。 (X1, X2
環(huán)評公示相關推薦
鄂ICP備17016276號-1