搜索
密码学概论密码学的数学基础（三）★本讲授课提纲★（1）模运算和同余（复习）（2）乘法逆元素（3）扩展的欧几里德算法3设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0≤rn,用amodn表示余数r如果(amodn)=(bmodn)，则称两整数a和b模n同余，记为a≡bmodn。称与a模n同余的数的全体为a的同余类，记为[a]，称a为这个同余类的表示元素。复习：★模运算和同余★复习：★模运算和同余★模运算a(modn)的运算给出了a对模数n的余数，这种运算称为模运算（modularreduction）。从0到n-1的整数组成的集合构成了模n的完全剩余集，这意味着，对于每一个整数a，它的模n的余项是从0到n-1的某个数。★模运算和同余★同余设整数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。★模运算和同余★同余和模运算的关系同余的另一种定义：如果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)★模运算和同余★性质一：当且仅当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)。★模运算和同余★模运算的加法和减法[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★模运算和同余★模运算的乘法的结合律[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★模运算和同余★同余的加法消去律如果(a+b)≡(a+c)(modn)，那么b≡c(modn)举例：(5+23)≡(5+7)(mod8)，那么23≡7(mod8)★模运算和同余★同余的乘法消去律设整数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)★模运算和同余★模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整除的为止。★本讲授课提纲★（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=(a×x)(modn)写成另一种形式，即a-1≡x(modn)解决乘法逆元素很困难，有时候有一个方案，有时候没有。例如2模14的乘法逆元素就不存在，5模14的乘法逆元素是3。★乘法逆元素★乘法逆元素的定义假设gcd(a,n)=1，则存在整数，使得as≡1(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成立。此时可以求出ax≡1(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)(T1,T2,T3)=(A1-QB1,A2-QB2,A3-QB3)(A1,A2,A3)=(B1,B2,B3);(B1,B2,B3)=(T1,T2,T3)5）GOTO2)★扩展的欧几里德算法★扩展的欧几里德算法例1：m=1759,b=550A1A2A3B1B2B3T1T2T3Q1101759015501-310932015501-3109-5165531-3109-5165106-3394214-5165106-3394-11135511106-3394-1113551