現(xiàn)代密碼學(xué)課件--第10講-公鑰密碼-資料下載頁(yè)
2025-07-25 12:41本頁(yè)面
【正文】 3)?(X1QY1,X2QY2,X3QY3)。 6. (X1 X2 X3)?(Y1Y2 Y3)。 7. (Y1Y2 Y3)?(T1 T2 T3)。 2 2022/8/22 20 中國(guó)剩余定理 ? 如果已知某個(gè)數(shù)關(guān)于一些量量互素的數(shù)的同余類集，就可以重構(gòu)這個(gè)數(shù) ? 定理 (中國(guó)剩余定理 )： 設(shè) m1,m2,… ,mk是兩兩互素的正整數(shù)， 則一次同余方程組 對(duì)模 M有唯一解 ??? kiimM1??????????kk amxamxamxm odm odm od2211?iiiikkkmemMeMaemMaemMaemMxm o d1m o d)( 222111?????滿足?2022/8/22 21 中國(guó)剩余定理 ? 中國(guó)剩余定理可以將一個(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。 考慮一般 am ≡1 mod n, 如果 a,n互素，至少有一個(gè)整數(shù) m滿足這一方程。稱滿足這一方程的最小正整數(shù) m為模 n下 a的 階 。 ? 例： a=7,n=19. 71 ≡7 mod 19, 72 ≡11 mod 19, 73 ≡1 mod 19,所以 7模 19的階為3。從冪次為 4開(kāi)始出現(xiàn)循環(huán)，循環(huán)周期與元素的階相同
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1