【安全課件】第12講--分組密碼小節(jié)-文庫吧資料
2025-03-17 03:03本頁面
【正文】 A(x)=q(x)B(x)+r(x)和 deg(r)deg(B)的 q(x)和 r(x). Step3 當(dāng) r(x)=0時(shí) ,輸出 B(x)=gcd(a(x),b(x))和z(x),m(x)。z(x)=0。s(x)=1。 后返回執(zhí)行 Step2. 9 歐幾里得算法： 計(jì)算 gcd(a(x),b(x))和使z(x)a(x)+y(x)b(x)=gcd(a(x),b(x))成立的 z(x),y(x). Step1 A(x)?a(x)。 y?tqy。 s?w。 B?r w?x。 Step2 計(jì)算帶余除法，求出滿足 A=qB+r和 0=rB的 q和 r. Step3 當(dāng) r=0時(shí) ,輸出 B=gcd(a,b)和 x,y。x=0。s=1。B?r后返回執(zhí)行 Step2. 5 ? 例 1 計(jì)算 gcd(63,100) ? 解 63 = 0 100 + 63, 100 = 1 63 + 37, 63 = 1 37 + 26 37 = 1 26 + 11, 26 = 2 11 + 4, 11 = 2 4 + 3, 4 =1 3 +1, 3 = 3 1 + 0 故 gcd(63,100)=1. 6 系數(shù)的計(jì)算 ? 倒推進(jìn)行 (將余數(shù)代入 ): ? 1 = 4 1 3 = 4 1 (11 2 4) = 1 11+(1+2) 4 = 1 11 + 3 4 = 1 11 + 3 (26 –2 11) = 7 11 + 3 26 = 7 (37 –26) + 3 26 = 7 37+ (7+3) 26 = 7 37 +10 26 = 7 37+10 ( 6337) = 10 63 17 37 = 10 63 17 (10063) = 17 100 + 27 63 7 輸出使得 ax+by=gcd(a,b)的 gcd(a,b)和 x,y的推理過程 . ? 記 a0=a,a1=b, 則求 ax+by=gcd(a,b)的過程可寫為： ? 即 0,22111132112100???????????????kkkkkkkkkaaaqaaaqaaaqaaaqa且??0,22111121131002???????????????kkkkkkkkkaaaqaaq
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1