安全與保密(編輯修改稿)
2025-01-24 19:27 本頁面
【文章內(nèi)容簡介】 模 7的簡化剩余集為 {1， 2， 3， 4， 5， 6} ? 歐拉函數(shù)：記為 ?(n)，為模 n的簡化剩余集中元素的個數(shù)。 ? 如果 n是素數(shù)，則 ?(n) = n1 ? 若 n=pq，其中 p、 q為素數(shù)，則 ?(n)=（ p1)(q1) ? 例： n=15 , n=3 ? 5 , p=3, q=5 ? ?(n)=2 ? 4=8 ? 15的簡化剩余集為 {1， 2， 4， 7， 8， 11， 13， 14} ? 歐拉擴展的 Fermat小定理：如果 gcd(a,n) = 1，則 a?(n) mod n = 1。 ? a的乘法逆元： x=a ?(n)1 mod n ? 例：求 5關(guān)于模 7的乘法逆元 解：方法一： 7=5+2 5=2 ? 2+1 1=52 ? 2 =52 ? (75) =3 ? 52 ? 7 5關(guān)于模 7的乘法逆元為 3 ? 方法二： n=7 n為素數(shù)， gcd(5,7)=1, ?(n)=n1=71=6 x= a ?(n)1 mod n =5 61 mod 7=55mod 7=3 ? 例： 4關(guān)于模 7的乘法逆元 解： ?(7)=71=6 n為素數(shù) gcd(4,7)=1 x= a ?(n)1 mod n =461 mod 7=45mod 7=2 中國剩余定理 ? 定理：如果 n的素數(shù)因子分解式為 p1?p2 ? … ? pt，則一組方程 (x mod pi） = ai，其中 i = 1,2,…, t，有唯一解 x，其中 x小于 n（其中某些 pi可能相等）。 ? 例：今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？ x mod 3 = 2 x mod 5 = 3 x mod 7 = 2 ? 解法： 令 a1=2， a2=3， a3=2， p1=3， p2=5， p3=7， n=p1 ? p2 ? p3=3 ? 5 ? 7=105， M1=n/p1=35, M2=n/p2=21, M3=n/p3=15 求解 35 x1 mod 3=1, 得 x1=2 求解 21 x2 mod 5=1, 得 x2=1 求解 15 x3 mod 7=1, 得 x3=1 則 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (35 ? 2 ? 2+21 ? 1 ? 3+15 ? 1 ? 2) mod 105 = 233 mod 105 = 23 ? 練習： ? 今有數(shù)不知其數(shù)，兩兩數(shù)之剩 1，三三數(shù)之剩 2，五五數(shù)之剩 2，求該數(shù)。 ? 解法： 令 a1=1， a2=2， a3=2， p1=2， p2=3， p3=5， n=p1 ? p2 ? p3=2 ? 3 ? 5=30 M1=n/p1=15, M2=n/p2=10, M3=n/p3=6 求解 15 x1 mod 2=1, 得 x1=1 求解 10 x2 mod 3=1, 得 x2=1 求解 6 x3 mod 5=1, 得 x3=1 則 x = (M1 x1 a1+M2 x2 a2+M3 x3 a3 ) mod n = (15 ? 1 ? 1+10 ? 1 ? 2+6 ? 1 ? 2) mod 30 = 47 mod 30 = 17 ? 課后練習： ? 今有數(shù)不知其數(shù)，五五數(shù)之剩 2，七七數(shù)之剩 5，十一十一數(shù)之剩 3，求該數(shù)。 二次剩余 ? 定義：設(shè) p為素數(shù)， a0且 ap，如果存在某個 x，滿足 x2 ? a (mod p)，則稱 a為模 p的二次剩余。否則稱 a為模 p的非二次剩余。 ? 例 1： p=5, a=4 x=2 22 ?4 （ mod 5） ? 例 2： p=11, a=5 x=4 42 ?5 （ mod 11） Legendre（勒讓得）符號 ? 記為 L(a,p)，其中 a為任意整數(shù)， p為大于 2的素數(shù)。 ? 定義： ? L(a,p) = 0，如果 a能被 p整除； ? L(a,p) = 1，如果 a是模 p的二次剩余； ? L(a,p) = 1，如果 a是模 p的非二次剩余； ? 計算： L(a,p) = a(p1)/2 mod p 公式驗證： L(a,p) = a(p1)/2 mod p = (a(p1) mod p)1/2 = 1 189。 Fermat小定理： am1 ? 1 (mod m) = 177。1 L(a,p) = 1=p1 Legendre符號的用途 ? 用 Legendre符號來驗證 a是否是模 p的二次剩余 ? 舉例 : ? 驗證： a=5是否是 p=11的二次剩余？ L(a,p) = a(p1)/2 mod p=5(111)/2 mod 11=55 mod 11=1 即 L(5,11) =1 所以 5是模 11的二次剩余 (72 ?5 mod
教學課件相關(guān)推薦
鄂ICP備17016276號-1