第13次课密码学中常用数学知识课件

密码学中常用的数学知识密码学中常用的数学知识群、环、域群、环、域素数和互素数素数和互素数模运算模运算费尔玛定理和欧拉定理费尔玛定理和欧拉定理素性检验素性检验欧几里德算法欧几里德算法中国剩余定理中国剩余定理密码学中常用的数学知识密码学中常用的数学知识群的定义:u一些数字组成的集合 u一个二元运算，运算结果属于此集合（封闭性）u服从结合律。有单位元，逆元。u如果是可交换的，则成为Abel群*为乘法时，称为乘法群为乘法时，称为乘法群 逆元（逆元（a-1）*为加法时，称为加法群为加法时，称为加法群 逆元（逆元（-a）环环的定义的定义:uAbel 群，及一个乘法运算：群，及一个乘法运算：u 满足结合律与满足结合律与加法的分配律加法的分配律 u如果加法满足交换律如果加法满足交换律,则称交换环则称交换环u例：整数例：整数 mod N（for any N）群群的定义的定义:*:*为乘法时，称为乘法群为乘法时，称为乘法群 逆元（逆元（a-a-域的定义：u是Abel加群 u环 u是Abel 乘群 u例：整数 mod P（P 为素数）Galois 域：域：u 如果如果 n是素数是素数 p，则模运算，则模运算modulo p 形成形成 Galois Field modulo p u 记为：记为：GF(p)域域的定义：的定义：Galois Galois 域：域：因子：对整数 b!=0 及 a,如果存在整数 m 使得 a=mb,称 b 整除 a,也称b是a的因子。记作 b|a 例 1,2,3,4,6,8,12,24 整除 24素数：素数：素数素数:只有因子只有因子 1 1 和自身和自身1 1 是一个平凡素数是一个平凡素数例例 2,3,5,7 2,3,5,7 是素数是素数,4,6,8,9,10,4,6,8,9,10 不是不是因子：素数：因子：素数：200200以内的素数：以内的素数：2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199素数分解：素数分解：把整数把整数n n写成素数的乘积写成素数的乘积 分解整数要比乘法困难分解整数要比乘法困难 整数整数 n n的素数分解是把它写素数的乘积的素数分解是把它写素数的乘积 eg.91=7 13;3600=2eg.91=7 13;3600=24 4 3 32 2 5 52 2 200200以内的素数：素数分解：以内的素数：素数分解：互素数：互素数：整数整数 a,ba,b 互素是指互素是指 它们没有除它们没有除1之外的其它因子之外的其它因子。8 与与15 互素互素 8的因子的因子1,2,4,8 15的因子的因子 1,3,5,15 1 是唯一的公因子是唯一的公因子记为：记为：gcd(8,15)=1互素数：互素数：设n是一正整数,a是整数,若 a=qn+r,0rn,则a mod n=r若(a mod n)=(b mod n),称为a,b模n同余，记为ab mod n称与a模n同余的数的全体为a的同余类，记为a，a称为这个同余类的代表元素。-21-20-19-18-17-16-21-20-19-18-17-16 1515-14-13-12-11-10-9-8-14-13-12-11-10-9-8 -7 -6-5-4-3-2-1 -7 -6-5-4-3-2-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 8 9 10 11 12 13 14 15 16 17 18 19 20 14 15 16 17 18 19 20 21 22 23 24 25 26 27 21 22 23 24 25 26 27 28 29 30 31 32 33 34 28 29 30 31 32 33 34 设设n n是一正整数是一正整数,a,a是整数是整数,若若 a=qn+r,0rn,a=qn+r,0rd1.Xf;Yd;2.If Y=0 then return X=gcd(f,d)3.R=X mod Y4.X=Y;5.Y=R6.Goto 2假定输入是两个正整数假定输入是两个正整数Euclid算法：算法：ngcd(55,22)=gcd(22,11)=gcd(11,0)=11ngcd(11,10)=gcd(10,1)=1Euclid(f,d)fdEuclid(f,d)fd假定输入是两个正整数假定输入是两个正整数EuclEucl欧几里德算法-求乘法逆元若gcd(a,b)=1,b在模a下有乘法逆元(设ba)。即存在xd)1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d);2.If Y3=0,then return X3=gcd(f,d);停止，没有逆元停止，没有逆元;3.If Y3=1,then return Y3=gcd(f,d);Y2=d-1 mod f;4.Q=X3 div Y3（整数除）（整数除）;5.(T1 T2 T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1 X2 X3)(Y1Y2 Y3);7.(Y1Y2 Y3)(T1 T2 T3);8.Goto 2扩展欧几里德算法：扩展欧几里德算法：求求d模模f的逆元的逆元Extended Euclid(f,d)(fd)Extended Euclid(f,d)(fd)扩展欧几扩展欧几例：求解例：求解 11d(mod51)=1的步骤。的步骤。即求即求11-1mod51=？循循环环次次数数QX1X2X3Y1Y2Y3初初值值-10510111Extended Euclid(f,d)(fd)1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d);2.If Y3=0,then return X3=gcd(f,d);停止，没有逆元停止，没有逆元;3.If Y3=1,then return Y3=gcd(f,d);Y2=d-1 mod f;4.Q=X3 div Y3（整数除）（整数除）;5.(T1 T2 T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1 X2 X3)(Y1Y2 Y3);7.(Y1Y2 Y3)(T1 T2 T3);8.Goto 21411-1mod51=14Q=X3 div Y3=51/11=4 T1=X1-Q*Y1=1-4*0=1 1-470111211-47-15431-1542-93412-93-3 141f*X1+d*X2=X3f*Y1+d*Y2=Y3f*T1+d*T2=T3例：求解例：求解 11d(mod51)=1 11d(mod51)=1的步骤。的步骤。即求即求11-11-孙子算经里所提出的问题之一如下:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二.问物几何？”“答日二十三.”把这个问题的提法用同余式的式子来表达，它可表把这个问题的提法用同余式的式子来表达，它可表示成解示成解同余式组同余式组x 2(mod 3),x 3(mod 5),x 2(mod 7)其中其中x是所求物数是所求物数.一般解为一般解为:x 70a+21b+15c(mod 105)这个解法这个解法,在明朝程大位的在明朝程大位的算法统宗算法统宗(1593)(1593)里有下面一首诗歌里有下面一首诗歌:三人同行七十稀，三人同行七十稀，五树梅花甘一枝，五树梅花甘一枝，七子团圆整半月，七子团圆整半月，除百零五便得知。除百零五便得知。x=70*2+21*3+15*2(mod105)=233mod105 =23孙子算经里所提出的问题之一如下孙子算经里所提出的问题之一如下:把这个问题把这个问题用途若已知某个数关于一些两两互素的数的同余集，可重构此数。大数用小数表示、大数的运算通过小数实现。例如：例如：Z Z1010中每个数都可从这个数关于中每个数都可从这个数关于2 2和和5 5（1010的两个互素的的两个互素的因子）的同余类重构。因子）的同余类重构。比如已知比如已知x x关于关于2 2和和5 5的同余类分别是的同余类分别是00和和33，即：即：x mod 20 x mod 20，x mod 53x mod 53。可知是偶数且被可知是偶数且被5 5除后余数是除后余数是3 3，所以可得所以可得8 8是满足这一关系的惟一的是满足这一关系的惟一的x x。用途例如：用途例如：Z10Z10中每个数都可从这个数关于中每个数都可从这个数关于2 2和和5 5（10 10的两个互的两个互大数用小数表示、大数的运算通过小数实现。大数用小数表示、大数的运算通过小数实现。例如：假设只能处理例如：假设只能处理5 5以内的数，要考虑以内的数，要考虑1515以内的数。以内的数。将将1515分解为分解为3 3和和5 5。将。将1515以内的数（以内的数（0-140-14）列表（行）列表（行0-20-2，列，列0-40-4）。）。0123400612391101713425112814数字所在行号为该数除数字所在行号为该数除3 3的余数的余数数字所在列号为该数除数字所在列号为该数除5 5的余数的余数乘法：乘法：12*13(mod15)=12*13(mod15)=？1212的行号的行号0 0，列号，列号2 2；1313的行号的行号1 1，列号，列号3 3。行：行：0*1(mod3)=0列：列：2*3(mod5)=1612*13(mod15)=6加法：加法：12+13(mod15)=?12+13(mod15)=?行：行：0+1(mod3)=10+1(mod3)=1列：列：2+3(mod5)=02+3(mod5)=01012+13(mod15)=10大数用小数表示、大数的运算通过小数实现。例如：假设只能处理大数用小数表示、大数的运算通过小数实现。例如：假设只能处理5 5定理定理3.5（中国剩余定理）（中国剩余定理）设设m1,m2,mk是两两互素的正是两两互素的正整数，整数，则一次同余方程组，则一次同余方程组对模对模M有惟一解有惟一解:其中其中ei满足满足令令Mi=M/mi ;ei=Mi=Mi-1(modmi)x=M1M1a1+M2M2a2+MkMkak(modM)定理定理3.5 3.5（中国剩余定理）（中国剩余定理）设设m1,m2,mkm1,m2,mk是两两互素是两两互素 韩信点兵韩信点兵:有兵一队有兵一队,若列成五行纵队若列成五行纵队,则末行一人则末行一人;成六行纵成六行纵队队,则末行五人则末行五人;成七行纵队成七行纵队,则末行四人则末行四人;成十一行纵队成十一行纵队,则末行则末行十人十人,求兵数求兵数.解 设设x是所求兵数是所求兵数,则依题意则依题意:x 1(mod 5),x 5(mod 6),x 4(mod 7),x 10(mod 11)则：则：m1=5,m2=6,m3=7,m4=11 a1=l,a2=5,a3=4,a4=10 M=m1m2m3m4=56711=2310 M1=M/m1=2310/5=462,M2=385,M3=330,M4=210.有有M1M1 1(mod 5),即即1 462 M1 2M1(mod 5),因此因此M1=3 同理可求同理可求M2=1,M3=1,M4=1.故解为故解为:x 13462+15385+14330+110210 6731 2100(mod 2310)即即 x=2100+2310k,k=0,1,2,.令令Mi=M/mi ;ei=Mi=Mi-1(modmi)x=M1M1a1+M2M2a2+MkMkak(modM)韩信点兵韩信点兵:有兵一队有兵一队,若列成五行纵队若列成五行纵队,则末行一人则末行一人;