高中数学选修5-3(密码学算法基础) 选修课密码学5 课件

密码学概论,密码学的数学基础（三）,本讲授课提纲,（1）模运算和同余（复习）,（2）乘法逆元素,（3）扩展的欧几里德算法,3,设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0rn,用amodn表示余数r,如果(amodn)=(bmodn)，则称两整数a和b模n同余，记为abmodn。,称与a模n同余的数的全体为a的同余类，记为a，称a为这个同余类的表示元素。,复习：模运算和同余,复习：模运算和同余,模运算a(modn)的运算给出了a对模数n的余数，这种运算称为模运算（modularreduction）。从0到n-1的整数组成的集合构成了模n的完全剩余集，这意味着，对于每一个整数a，它的模n的余项是从0到n-1的某个数。,模运算和同余,同余设整数a,b,n(n0)，如果a-b是n的整数倍（正的或负的），我们就说“a与b模n同余”，记做ab(modn)。有时，b被叫做a模n的余数。另一种描述：如果a与b的差能被n整除，就说ab(modn)，即存在非零整数k，使得a=b+nk。,模运算和同余,同余和模运算的关系同余的另一种定义：如果a(modn)=b(modn)，则称a和b模n同余,记做ab(modn)。a(modn)=b(modn)ab(modn)举例：73(mod23)=4;27(mod23)=4;所以7327(mod23),模运算和同余,性质一：当且仅当n|a，a0(modn),模运算和同余的性质,性质二：(自反性)对任意整数a，有aa(modn),性质三：(对称性)如果ab(modn)，那么ba(modn),性质四:(传递性)如果ab(modn)，bc(modn)，那么ac(modn),性质五：如果m|(a-b)，则ab(modm),性质六：设整数a，b，c，d，n(n0)，假设ab(modn)，且cd(modn)，那么a+cb+d(modn)，a-cb-d(modn)，acbd(modn)。,模运算和同余,模运算的加法和减法a(modn)b(modn)(modn)=(ab)(modn)举例：已知11(mod8)=3；15(mod8)=711(mod8)+15(mod8)(mod8)=(3+7)(mod8)=2=(11+15)(mod8)=26(mod8)=211(mod8)-15(mod8)(mod8)=(3-7)(mod8)=4=(11-15)(mod8)=-4(mod8)=4,模运算和同余,模运算的乘法的结合律a(modn)b(modn)(modn)=(ab)(modn)举例：11(mod8)15(mod8)(mod8)=(37)(mod8)=21(mod8)=5=(1115)(mod8)=165(mod8)=5,模运算和同余,同余的加法消去律如果(a+b)(a+c)(modn)，那么bc(modn)举例：(5+23)(5+7)(mod8)，那么237(mod8),模运算和同余,同余的乘法消去律设整数a,b,c,n(n0)，且gcd(a,n)=1，如果abac(modn)，那么bc(modn)。举例：53=157(mod8)，511=557(mod8)53511(mod8)311(mod8),模运算和同余,模n除法模n除法主要用乘法消去律和乘法逆元素来解决举例：解2x+7=3(mod17)2x3-7-4(mod17)，于是有x-215(mod17)举例：解5x+6=13(mod11)5x7(mod11)，此处涉及乘法逆元素，一种可行的方法是试探所有的7,18,29,40,51直到有能被5整除的为止。,本讲授课提纲,（1）模运算和同余(复习）,（2）乘法逆元素,（3）扩展的欧几里德算法,乘法逆元素,乘法逆元素的引入仿射密码解密时，需由加密函数y=9x+2(mod26)中反解出x，x=(1/9)(y-2)(mod26)1/9就表示在模26的条件下，9的乘法逆元素，换句话说，就是：要求在0,1,2,3,4,25找一个数，这个数和9相乘再取模26运算，结果为1。,乘法逆元素,乘法逆元素的一般提法寻找一个x，使得1=(ax)(modn)写成另一种形式，即a-1x(modn)解决乘法逆元素很困难，有时候有一个方案，有时候没有。例如2模14的乘法逆元素就不存在，5模14的乘法逆元素是3。,乘法逆元素,乘法逆元素的定义假设gcd(a,n)=1，则存在整数，使得as1(modn)，即s是a(modn)的乘法逆元素。,本讲授课提纲,（1）模运算和同余,（2）乘法逆元素,（3）扩展的欧几里德算法,扩展的欧几里德算法,关于ax+by=d,由欧几里德算法可以得到下面的重要结论设a和b是两个正整数（至少有一个非零），d=gcd(a,b)，则存在整数x和y使得ax+by=d成立，如果a和b都是素数，那么存在整数x和y使得ax+by=1成立。此时可以求出ax1(modb)中的x。,扩展的欧几里德算法,关于ax+by=d,求解ax+by=1可使用扩展的欧几里德算法。扩展的欧几里德算法不仅能确定两个正整数的最大公约数，如果这两个数互素，还能确定他们各自的乘法逆元素。,扩展的欧几里德算法,扩展的欧几里德算法,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)(T