保障與安全數(shù)論ppt課件-資料下載頁
2025-01-12 13:12本頁面
【正文】 = p1e1p2e2… prer，其中 p1,p2,…,p r為互異素?cái)?shù)， 則 φ(n)= p1e11p2e21… prer1(p11)(p22)…(p r1) =n(11/p1) (11/p2) (11/p3)… (1 1/pr) 例 3：① n=21=3*7，有兩個(gè)素?cái)?shù) 3和 7，這樣， ?(21) =21(11/3)(11/7)=12 即 21中有 12個(gè)整數(shù)與 21是互素的 : 1, 2, 4, 5， 8, 10， 11, 12， 13, 16， 17, 19 ② n＝ 24=3*8=3*23， φ(24)=24(11/3)*(11/2)=8 即 24中有 8個(gè)整數(shù)與 24是互素的 ： 1， 5， 7， 11， 13， 17， 19， 23 25 ⑶ 歐拉定理（ Euler）： 若整數(shù) a與整數(shù) n互素，則 aφ(n)≡1(mod n) ? 推論 ： 若 a與 n互素，則 a與 a φ(n)1 互為逆元。 ? 例 4 求 5關(guān)于 模 7 的乘法逆元。 ? 解 由于 7是素?cái)?shù)， ?(7) =71=6，所以 5關(guān)于模 7的 乘法逆元為 5 61 mod7=55mod7=3 注： 1*. n＝ p時(shí)，有 ap1≡1(mod p)為 Format定理！ 2*.易見 aφ(n)+1≡a(mod n) 3*.若 n=pq， p與 q為相異素?cái)?shù)，取 0mn，若 gcd(m,n)＝ 1，有 mφ(n)+1≡m(mod n)， 也即 m(p1)(q1)+1≡m(mod n). 4*.由 (mφ(n))k≡1k(mod n) 知 mkφ(n)≡1(modn)， 進(jìn)一步 mkφ(n)+1≡m(mod n) mk(p1)(q1)+1≡m(mod n) 推廣歐拉定理： 若 a ≡b (mod r) ， 則對于任意冪 m， 有 am ≡ bm (mod r) am ?(r) ≡1 (mod r) 若 a ≡b (mod r) ， 則對于任意的整數(shù) c， 有 ac ≡ bc (mod r) Xm ?(r)+1 ≡X (mod r) 27 4 原根 (primitive root) ? Euler定理表明 ,對兩個(gè)互素的整數(shù) a,n, a?(n) ? 1 mod n ? 定義： 存在最小正整數(shù) m??(n) (m|?(n)),使得 am ? 1 mod n，若對某個(gè) a, m=?(n),則稱 a是 n的一個(gè)原根 ? 對于素?cái)?shù) p,若 a是 p的一個(gè)原根 ,則 : a,a2, …,a p1 是 (模 p)各不相同的 ,從而構(gòu)成了 p的非 0剩余類 ,即與{1,2,…,(p 1)}關(guān)于模 p等價(jià) . 28 5 離散對數(shù) ? 若 a是素?cái)?shù) p的一個(gè)原根 ,則對任意整數(shù) b, b≡r mod p,其中 0≤r≤p1 ? 因此， 對任意整數(shù) b和素?cái)?shù) p ， 存在唯一的整數(shù) i, 使得 :b?ai mod p 1?i?(p1) ? 稱指數(shù) i為以 a為底模 p的 b的離散對數(shù)， 記作 inda,p(b).容易知道 : inda,p(xy)= [inda,p(x)+inda,p(y)] mod ?(p) inda,p(xr)= [r?inda,p(x)] mod ?(p) ? inda,p(1)=0,因?yàn)? a0 mod p =1 mod p=1 inda,p(a)=1，因?yàn)? a1 mod p =a 29 5 離散對數(shù) ? 離散對數(shù)的計(jì)算 : y?gx mod p – 已知 g,x,p,計(jì)算 y是容易的 – 已知 y,g,p,計(jì)算 x是困難的 30 公鑰算法的經(jīng)典例子 ? DiffieHellman密鑰交換算法 ? 背包算法 ? RSA算法 ? EIGamal算法 ? 橢圓曲線密碼算法 ECC
試題試卷相關(guān)推薦
鄂ICP備17016276號-1