保障與安全數(shù)論ppt課件(編輯修改稿)
2025-02-08 13:12 本頁面
【文章內(nèi)容簡(jiǎn)介】 個(gè)數(shù)關(guān)于另一個(gè)數(shù)的乘法逆元。 Euclid算法是基于下面一個(gè)基本結(jié)論： 對(duì)任意非負(fù)整數(shù) a和正整數(shù) b，有 gcd(a, b)=gcd(b,a mod b)。即 a， b的公因子集合與 b， a mod b的公因子集合相等，兩個(gè)集合的最大值也相等。 例如： gcd(55, 22)=gcd(22, 55 mod 22) = gcd(22,11) =gcd(11, 0)=11。 在求兩個(gè)數(shù)的最大公因子時(shí)，可重復(fù)使用以上結(jié)論。 例如： gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=gcd(1,0)=1。 歐幾里得算法 12 例子 ：求 gcd(180， 252)，并將他表示為 180和 252這兩個(gè)數(shù)的一個(gè)帶整系數(shù)的線性組合。 解： 252=1*180+72 (1) 180=2*72+36 (2) 72=2*36 (3) 得 gcd(180,252)=36，同時(shí)有 72=2521*180 (1 ?) 由 (2)得 36=1802*72 (2 ?) 將 (1?)代入 (2 ?)，即得 36=1802*(252180) =3*1802*252 求 gcd(1970,1066)=2 13 求 gcd(1970, 1066)。 1970=1 1066+904, gcd(1066, 904) 1066=1 904+162, gcd(904, 162) 904=5 162+94, gcd(162, 94) 162=1 94+68, gcd(94, 68) 94=1 68+26, gcd(68, 26) 68=2 26+16, gcd(26, 16) 26=1 16+10, gcd(16, 10) 16=1 10+6, gcd(10, 6) 10=1 6+4, gcd(6, 4) 6=1 4+2, gcd(4, 2) 4=2 2+0, gcd(2, 0) 因此 gcd(1970, 1066)=2。 14 計(jì)算逆元的方法有 用歐拉推廣公式解： x=(b a φ(n)1)modn 用歐幾里德算法解： x=(b (a 1modn))modn 通常歐幾里德算法在計(jì)算逆元方面較歐拉推廣更快，特別是 500位范圍內(nèi)的數(shù)。 15 Euclid算法就是用這種方法，因 gcd(a, b)=gcd(|a|, |b|)，因此可假定算法的輸入是兩個(gè)正整數(shù)，設(shè)為 d， f，并設(shè)f d。 Euclid（ f, d） 1. X←f。 Y←d ； 2. if Y=0 then return X=gcd(f,d)； 3. R=X mod Y； 4. X=Y； 5. Y=R； 6. goto 2。 16 求乘法逆元 如果 gcd(a, b)=1 ，則 b在 mod a下有乘法逆元（不妨設(shè)ba），即存在一 x (xa)，使得 bx≡1 mod a。推廣的Euclid算法先求出 gcd(a, b)，當(dāng) gcd(a, b)=1時(shí)，則返回 b的逆元。 17 擴(kuò)展 Euclidean 算法 設(shè) r0為 a ， r1為 b0，用輾轉(zhuǎn)相除法，先用 b去除 a，得 r0 =q1 r1 +r2, 0r2r1 r1 =q2 r2 +r3, 0r3r2。 等等，這樣一直進(jìn)行下去，可得一系列關(guān)系式： rm2=qm1rm1+rm, 0rmrm1 rm1=qmrm 結(jié)論：假定 gcd(r0 , r1)=1, 1 = gcd(r0 , r1)= sm r0+tm r1 那么 r11mod r0 = tmmod r0 18 Extended Euclid(f, d) （設(shè) f d） 1. (X1,X2,X3)←(1,0,f)。(Y1,Y2,Y3)←(0,1,d)。 2. if Y3=0 then return X3=gcd(f, d)； n
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1