rsa算法及安全性分析-在線瀏覽
2025-02-26 02:14本頁面
【正文】 證明思路： 1. 用反證法證明 a和 Zn中任何兩個不同的數(shù)相乘結(jié)果都不相同 2. 從 1得出 a Zn=Zn,因此存在 x∈Z n,使a x=1 mod n ? 設 p為素數(shù)， Zp中每一個非零元素都與 p互素，因此有乘法逆元，有乘法可約律 (a b)=(a c) mod n, b=c mod n 中國剩余定理 ? 如果已知某個數(shù)關(guān)于一些量量互素的數(shù)的同余類集，就可以重構(gòu)這個數(shù) ? 定理 (中國剩余定理 )： 設 m1,m2,…,m k是兩兩互素的正整數(shù)， 則一次同余方程組 對模 M有唯一解 ??? kiimM1??????????kk amxamxamxm o dm o dm o d2211?iiiikkkmemMeMaemMaemMaemMxm o d1?????滿足m o d)( 222111?中國剩余定理 ?中國剩余定理可以將一個很大的數(shù) x表示為一組較小的數(shù) (a1,…a k) ?例： 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 費爾瑪定理和歐拉定理 ?費爾瑪定理 若 p是素數(shù)， a是正整數(shù)且 gcd(a,p)=1，則 ap1≡1 mod p 證明： gcd(a,p)=1,則 a Zp=Zp, a (Zp{0})=Zp{0} {a mod p,2a mod p,… ,(n1)a mod p} ={0,1,… ,p1} (a mod p) (2a mod p) … (n1)a mod p=(p1)! mod p (p1)! ap1=(p1)! mod p (p1)!與 p互素，所以乘法可約律， ap1=1 mod p 費爾瑪定理和歐拉定理 ?歐拉函數(shù) ?設 n為一正整數(shù)，小于 n且與 n互素的正整數(shù)的個數(shù)稱為 n的歐拉函數(shù)，記為 φ (n) ?定理：若 n是兩個素數(shù) p和 q的乘積，則φ (n)＝ φ (p) φ (q
試題試卷相關(guān)推薦
鄂ICP備17016276號-1