高中數(shù)學選修53(密碼學算法基礎)-選修課密碼學5-省公開課一等獎全國示范課微課金獎課件

密碼學概論密碼學數(shù)學基礎（三）第1頁★本講講課提要★（1）模運算和同余（復習）（2）乘法逆元素（3）擴展歐幾里德算法第2頁3設n是一正整數(shù)，a是整數(shù)，假如用n除a，得商為q，余數(shù)為r，則a=qn+r,0≤r<n,用amodn表示余數(shù)r假如(amodn)=(bmodn)，則稱兩整數(shù)a和b模n同余，記為a≡bmodn。稱與a模n同余數(shù)全體為a同余類，記為[a]，稱a為這個同余類表示元素。復習：★模運算和同余★第3頁復習：★模運算和同余★模運算a(modn)運算給出了a對模數(shù)n余數(shù)，這種運算稱為模運算（modularreduction）。從0到n-1整數(shù)組成集合組成了模n完全剩下集，這意味著，對于每一個整數(shù)a，它模n余項是從0到n-1某個數(shù)。第4頁★模運算和同余★同余設整數(shù)a,b,n(n≠0)，假如a-b是n整數(shù)倍（正或負），我們就說“a與b模n同余”，記做a≡b(modn)。有時，b被叫做a模n余數(shù)。另一個描述：假如a與b差能被n整除，就說a≡b(modn)，即存在非零整數(shù)k，使得a=b+nk。第5頁★模運算和同余★同余和模運算關系同余另一個定義：假如a(modn)=b(modn)，則稱a和b模n同余,記做a≡b(modn)。a(modn)=b(modn)a≡b(modn)舉例：73(mod23)=4;27(mod23)=4;所以73≡27(mod23)第6頁★模運算和同余★性質一：當且僅當n|a，a≡0(modn)模運算和同余性質性質二：(自反性)對任意整數(shù)a，有a≡a(modn)性質三：(對稱性)假如a≡b(modn)，那么b≡a(modn)性質四:(傳遞性)假如a≡b(modn)，b≡c(modn)，那么a≡c(modn)性質五：假如m|(a-b)，則a≡b(modm)性質六：設整數(shù)a，b，c，d，n(n≠0)，假設a≡b(modn)，且c≡d(modn)，那么a+c≡b+d(modn)，a-c≡b-d(modn)，ac≡bd(modn)。第7頁★模運算和同余★模運算加法和減法[a(modn)±b(modn)](modn)=(a±b)(modn)舉例：已知11(mod8)=3；15(mod8)=7[11(mod8)+15(mod8)](mod8)=(3+7)(mod8)=2=(11+15)(mod8)=26(mod8)=2[11(mod8)-15(mod8)](mod8)=(3-7)(mod8)=4=(11-15)(mod8)=-4(mod8)=4第8頁★模運算和同余★模運算乘法結合律[a(modn)×b(modn)](modn)=(a×b)(modn)舉例：[11(mod8)×15(mod8)](mod8)=(3×7)(mod8)=21(mod8)=5=(11×15)(mod8)=165(mod8)=5第9頁★模運算和同余★同余加法消去律假如(a+b)≡(a+c)(modn)，那么b≡c(modn)舉例：(5+23)≡(5+7)(mod8)，那么23≡7(mod8)第10頁★模運算和同余★同余乘法消去律設整數(shù)a,b,c,n(n≠0)，且gcd(a,n)=1，假如ab≡ac(modn)，那么b≡c(modn)。舉例：5×3=15≡7(mod8)，5×11=55≡7(mod8)5×3≡5×11(mod8)3≡11(mod8)第11頁★模運算和同余★模n除法模n除法主要用乘法消去律和乘法逆元素來處理舉例：解2x+7=3(mod17)2x≡3-7≡-4(mod17)，于是有x≡-2≡15(mod17)舉例：解5x+6=13(mod11)5x≡7(mod11)，此處包括乘法逆元素，一個可行方法是試探全部7,18,29,40,51……直到有能被5整除為止。第12頁★本講講課提要★（1）模運算和同余(復習）（2）乘法逆元素（3）擴展歐幾里德算法第13頁★乘法逆元素★乘法逆元素引入仿射密碼解密時，需由加密函數(shù)y=9x+2(mod26)中反解出x，x=(1/9)(y-2)(mod26)1/9就表示在模26條件下，9乘法逆元素，換句話說，就是：要求在0,1,2,3,4,…,25找一個數(shù)，這個數(shù)和9相乘再取模26運算，結果為1。第14頁★乘法逆元素★乘法逆元素普通提法尋找一個x，使得1=(a×x)(modn)寫成另一個形式，即a-1≡x(modn)處理乘法逆元素很困難，有時候有一個方案，有時候沒有。比如2模14乘法逆元素就不存在，5模14乘法逆元素是3。第15頁★乘法逆元素★乘法逆元素定義假設gcd(a,n)=1，則存在整數(shù)，使得as≡1(modn)，即s是a(modn)乘法逆元素。第16頁★本講講課提要★（1）模運算和同余（2）乘法逆元素（3）擴展歐幾里德算法第17頁★擴展歐幾里德算法★關于ax+by=d由歐幾里德算法能夠得到下面主要結論設a和b是兩個正整數(shù)（最少有一個非零），d=gcd(a,b)，則存在整數(shù)x和y使得ax+by=d成立，假如a和b都是素數(shù)，那么存在整數(shù)x和y使得ax+by=1成立。此時能夠求出ax≡1(modb)中x。第18頁★擴展歐幾里德算法★關于ax+by=d求解ax+by=1可使用擴展歐幾里德算法。擴展歐幾里德算法不但能確定兩個正整數(shù)最大條約數(shù)，假如這兩個數(shù)互素，還能確定他們各自乘法逆元素。第19頁★擴展歐幾里德算法★擴展歐幾里德算法1)(A1,A2,A3)=(1,0,m);(B1,B2,B3)=(0,1,b)2)ifB3=0,returnA3=gcd(m,b);noinverse;ifB3=1,returnB3=gcd(m,b);B2=b-1modm;3)Q=【A3/B3】4)(T1,T2,T3)=(A1-QB1,A2-QB2,A3-QB3)(A1,A2,A3)=(B1,B2,B3);(B1,B2,B3)=(T1,T2,T3)5）GOTO2)第20頁★擴展歐幾里德算法★擴展歐幾里德算法例1：m=1759,b=550A1A2A3B1B2B3T1T2T3Q