第08讲 数论理论介绍.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八讲 数论理论介绍,上海交通大学计算机科学系,郑东,本讲,介绍数论的概念及在,galois,域中计算的概念,1.数论介绍,数论概念:,研究“离散数字集合”,运算是“+”,“”,例:,整数:,5+9=14;5 3=5+5+5=15,多项式:,x,2,+1+x=x,2,+x+1;x x,2,+1=x,3,+x,运算概念,运算:,模数运算,模多项式运算,进一步运算:,指数运算,逆运算,理解公钥算法的基础,2.整除,对整数,b!=0,及,a,如果存在整数,m,使得,a=,mb,称,b,整除,a,也称,b,是,a,的因子,记作,b|a,例,1,2,3,4,6,8,12,24,整除,24,3.素数与不可约多项式,素数:只有因子 1 和自身,1 是一个平凡素数,例 2,3,5,7 是素数,4,6,8,9,10 不是,素多项式或不可约多项式,irreducible,:,不可写成其他因式的乘积,x,2,+x=x x+1,是非不可约多项式;,x,3,+x+1,是不可约多项式,4.一些素数,200,以内的素数:,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,5.素数分解(,PrimeFactorisation,),把,整数,n,写成素数的成绩,分解整数要比乘法困难,整数,n,的素数分解是把它写素数的乘积,eg,.,91=7 13;3600=2,4,3,2,5,2,6.整数互素,整数,a,b,互素是指 它们没有除1之外的其它因子,8 与15 互素,8,的因子1,2,4,8,15,的因子,1,3,5,15,1,是唯一的公因子,8.模算式,除法取余运算,同余(,congruence),for,a=b mod n,如果,a,b,除以,n,余数相同,eg,.,100=34 mod 11,b,叫做,a,模,n,的剩余,通常,0=,b=n-1,eg,.,-12mod7=-5mod7=2mod7=9mod7,可以进行整数运算,9.,模运算举例,-21-20-19-18-17-16 15,-14-13-12-11-10-9-8,-7 -6-5-4-3-2-1,0 1 2 3 4 5 6,7 8 9 10 11 12 13,14 15 16 17 18 19 20,21 22 23 24 25 26 27,28 29 30 31 32 33 34,10.模算术运算,加法,a+b mod n,减法,a-b mod n=a+(-b)mod n,11.乘法除法,乘法,a.b mod n,重复加法,除法,a/b mod n,乘以,b,的逆元,:,a/b=a.b,-1,mod n,如果,n,是素数,b,-1,mod n,存在,s.t,b.b,-1,=1 mod n,例.,2.3=1,mod 5 hence 4/2=4.3=2 mod 5,12模递归运算,模递归运算是“模除求余”,例.,r=a mod n,计算,a=d.n+r,33 mod 7=4.7+5;,得数是 5,通常,r,取,正数,例,-18,mod 7=-3.7+3;,答案是3,a+/-b mod n=a mod n+/-b mod n mod n,13.运算法则,类似于正常算术运算:,结合律:,(,a+b)+c=a+(b+c)mod n,交换 律,分配律,(,a+b).c=(a.c)+(b.c)mod n,加法单位元乘法单位元,0+,w=w mod n,1,w=w mod n,乘法运算类同,14群.环.域,群的,定义,:,一些数字组成的集合,一个加法运算，运算结果属于此集合,（,封闭性）,服从结合律。有单位元，逆元,如果是可交换的，则成为,abelian,群,15。环,环:,abelian,群，及一个乘法运算：,满足结合律与加法的分配律,如果加法满足交换律,则称交换环,例：整数,mod N（for any N）,16。域,域：,abelian,加群,环,abelian,乘群,(,ignoring 0),例：,integers mod P（P,为素数）,17。,Galois,域,如果,n,是素数,p,则模,运算,modulo,p,形成,Galois Field modulo p,记为：,GF(p),18。,GF(p),中的指数运算,许多加密运算需要指数运算,b=,a,e,mod p,重复乘法运算,eg,.,7,5,=7.7.7.7.7,一个好的方法是不是平方 和乘法,19。平方、乘法运算,计算指数的快速有效算法,思想：重复平方运算,计算最终结果的乘法运算,20。平方乘法运算,例,7,5,=7,4,.7=3.7=10,mod 11;3,129,mod 11=4,let base=a,result=1,for each bit,e,i,(LSB to MSB)of exponent,if,e,i,=0 then,square base mod p,if,e,i,=1 then,multiply result by base mod p,square base mod p(except for MSB),at end the required answer is result,21。,平方乘法举例,7,5,=7,4,.7=3.7=10,mod 11,base,res,exp(5=101,2,),7 1,nitialise,7.7=49=5 1.7=7,result=result x base,square base),5.5=25=3 0(square base),3.3=9 7.3=21=10 1(result=result x base,square base),22。,GF(p),中的离散对数,指数的逆问题是寻找,整数模,p,的离散对数,即：求,x,使得,a,x,=b mod p,eg,.x=log,3,4 mod?(,ie,x,st,.3,x,=4 mod?),无解,eg,.x=log,2,3 mod 13=4（,利用连续实验）,计算指数相对容易，求离散对数一般很难,可以证明若,p,素数,则总存在 离散对数（,for any,b!=0,）,a,的连续指数可以生成群（,the group,mod p,）,a,叫做一个本原根（,a,primitive root,）,较困难的问题,Greatest Common Divisor,数论中的一个普遍问题：决定最大公因子（,greatest common divisor,(GCD)）,GCD,(a,b),是整除,a,b,的最大整数,经常用于证明两个数互素,OK！,