現(xiàn)代密碼學(xué)課件--第10講-公鑰密碼(參考版)
2025-07-28 12:41本頁面
【正文】 從冪次為 4開始出現(xiàn)循環(huán)，循環(huán)周期與元素的階相同 。稱滿足這一方程的最小正整數(shù) m為模 n下 a的 階 。 2 2022/8/22 20 中國剩余定理 ? 如果已知某個(gè)數(shù)關(guān)于一些量量互素的數(shù)的同余類集，就可以重構(gòu)這個(gè)數(shù) ? 定理 (中國剩余定理 )： 設(shè) m1,m2,… ,mk是兩兩互素的正整數(shù)， 則一次同余方程組 對(duì)模 M有唯一解 ??? kiimM1??????????kk amxamxamxm odm odm od2211?iiiikkkmemMeMaemMaemMaemMxm o d1m o d)( 222111?????滿足?2022/8/22 21 中國剩余定理 ? 中國剩余定理可以將一個(gè)很大的數(shù) x表示為一組較小的數(shù) (a1,… ak) ? 例： x≡1 mod 2, x≡2 mod 3, x≡3 mod 5 x≡5 mod 7,求 x ? 解： M＝ 2 3 5 7＝ 210， M1=105, M2=70, M3=42, M4=30, (Mi=M/mi),可以求得 e1=1, e2=1, e3=3, e4=4,所以x=105 1 1＋ 70 1 2＋ 42 3 3＋30 4 5 mod 210＝ 173 2022/8/22 22 離散對(duì)數(shù) ? 求模下的整數(shù)冪 ? 根據(jù)歐拉定理，若 gcd(a,n)=1,則 af(n) ≡1 mod n。 6. (X1 X2 X3)?(Y1Y2 Y3)。 4. Q=X3 div Y3。 3. If Y3=1, then return X3=gcd(f,d)。 2. If Y3=0, then return X3=gcd(f,d)。即存在 xa,bx≡1 mod a Extended Euclid(f,d) (fd) 1.（ X1 X2 X3)?(1,0,f)。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1