高中数学选修53(密码学算法基础)-选修课密码学5-省公开课一等奖全国示范课微课金奖课件

密码学概论密码学数学基础（三）第1页★本讲讲课提要★（1）模运算和同余（复习）（2）乘法逆元素（3）扩展欧几里德算法第2页3设n是一正整数，a是整数，假如用n除a，得商为q，余数为r，则a=qn+r,0≤r<n,用amodn表示余数r假如(amodn)=(bmodn)，则称两整数a和b模n同余，记为a≡bmodn。称与a模n同余数全体为a同余类，记为[a]，称a为这个同余类表示元素。复习：★模运算和同余★第3页复习：★模运算和同余★模运算a(modn)运算给出了a对模数n余数，这种运算称为模运算（modularreduction）。从0到n-1整数组成集合组成了模n完全剩下集，这意味着，对于每一个整数a，它模n余项是从0到n-1某个数。第4页★模运算和同余★同余设整数a,b,n(n≠0)，假如a-b是n整数倍（正或负），我们就说“a与b模n同余”，记做a≡b(modn)。有时，b被叫做a模n余数。另一个描述：假如a与b差能被n整除，就说a≡b(modn)，即存在非零整数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)模运算和同余性质性质二：(自反性)对任意整数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)性质六：设整数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页★模运算和同余★同余乘法消去律设整数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页★乘法逆元素★乘法逆元素引入仿射密码解密时，需由加密函数y=9x+2(mod26)中反解出x，x=(1/9)(y-2)(mod26)1/9就表示在模26条件下，9乘法逆元素，换句话说，就是：要求在0,1,2,3,4,…,25找一个数，这个数和9相乘再取模26运算，结果为1。第14页★乘法逆元素★乘法逆元素普通提法寻找一个x，使得1=(a×x)(modn)写成另一个形式，即a-1≡x(modn)处理乘法逆元素很困难，有时候有一个方案，有时候没有。比如2模14乘法逆元素就不存在，5模14乘法逆元素是3。第15页★乘法逆元素★乘法逆元素定义假设gcd(a,n)=1，则存在整数，使得as≡1(modn)，即s是a(modn)乘法逆元素。第16页★本讲讲课提要★（1）模运算和同余（2）乘法逆元素（3）扩展欧几里德算法第17页★扩展欧几里德算法★关于ax+by=d由欧几里德算法能够得到下面主要结论设a和b是两个正整数（最少有一个非零），d=gcd(a,b)，则存在整数x和y使得ax+by=d成立，假如a和b都是素数，那么存在整数x和y使得ax+by=1成立。此时能够求出ax≡1(modb)中x。第18页★扩展欧几里德算法★关于ax+by=d求解ax+by=1可使用扩展欧几里德算法。扩展欧几里德算法不但能确定两个正整数最大条约数，假如这两个数互素，还能确定他们各自乘法逆元素。第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