《数论理论介绍幻灯片.ppt》由会员分享，可在线阅读，更多相关《数论理论介绍幻灯片.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数论理论介绍第1页，共26页，编辑于2022年，星期六n本讲介绍数论的概念及在galois 域中计算的概念第2页，共26页，编辑于2022年，星期六1.数论介绍n数论概念:n 研究“离散数字集合”n运算是“+”,“”n例:n整数:5+9=14;5 3=5+5+5=15 n多项式:x2+1+x=x2+x+1;x x2+1=x3+x 第3页，共26页，编辑于2022年，星期六运算概念n运算:n模数运算n模多项式运算n进一步运算:n指数运算,逆运算理解公钥算法的基础理解公钥算法的基础第4页，共26页，编辑于2022年，星期六2.整除n对整数 b!=0 及 a,如果存在整数如果存在整数 m 使得 a=
2、mb,称 b 整除 a,也称b是a的因子n记作 b|a n例 1,2,3,4,6,8,12,24 整除 24 第5页，共26页，编辑于2022年，星期六3.素数与不可约多项式n素数:只有因子 1 和自身n1 是一个平凡素数n例 2,3,5,7 是素数,4,6,8,9,10 不是n素多项式或不可约多项式irreducible:n 不可写成其他因式的乘积n x2+x=x x+1 是非不可约多项式;x3+x+1 是不可约多项式第6页，共26页，编辑于2022年，星期六4.一些素数n200 以内的素数:n 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 6
3、1 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 第7页，共26页，编辑于2022年，星期六5.素数分解(PrimeFactorisation)PrimeFactorisation)n把整数n写成素数的成绩n分解整数要比乘法困难n整数 n的素数分解是把它写素数的乘积 eg.91=7 13;3600=24 32 52 第8页，共26页，编辑于2022年，星期六6.整数互素n整数 a,b 互素是指 它们没有除1之外的其它因子n8 与15
4、 互素 n8的因子1,2,4,8 n15的因子 1,3,5,15 n1 是唯一的公因子n 第9页，共26页，编辑于2022年，星期六8.模算式n除法取余运算 n同余(congruence)for a=b mod n n如果a,b 除以n,余数相同neg.100=34 mod 11 nb 叫做a模n的剩余 n通常 0=b=n-1 neg.-12mod7=-5mod7=2mod7=9mod7 n可以进行整数运算 第10页，共26页，编辑于2022年，星期六9.,模运算举例n-21-20-19-18-17-16 15n-14-13-12-11-10-9-8 n-7 -6-5-4-3-2-1 n 0
5、1 2 3 4 5 6 0 1 2 3 4 5 6 n7 8 9 10 11 12 13 n14 15 16 17 18 19 20 n21 22 23 24 25 26 27 n28 29 30 31 32 33 34 第11页，共26页，编辑于2022年，星期六10.模算术运算n加法加法a+b mod n n减法减法na-b mod n=a+(-b)mod n 第12页，共26页，编辑于2022年，星期六11.乘法除法n乘法乘法na.b mod n n重复加法 n除法除法 na/b mod n n乘以b的逆元:a/b=a.b-1 mod n n如果n是素数,b-1 mod n 存在 s.t
6、 b.b-1=1 mod n n例.2.3=1 mod 5 hence 4/2=4.3=2 mod 5 第13页，共26页，编辑于2022年，星期六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 第14页，共26页，编辑于2022年，星期六13.运算法则类似于正常算术运算:结合律结合律:(a+b)+c=a+(b+c)mod n 交换交换 律律分配律分配律(a+b).c=(a.c)+(b
7、.c)mod n 加法单位元加法单位元 乘法单位元乘法单位元0+w=w mod n 1w=w mod n 乘法运算类同第15页，共26页，编辑于2022年，星期六14群.环.域群的定义:n一些数字组成的集合 n一个加法运算，运算结果属于此集合（封闭性）n服从结合律。有单位元，逆元 n如果是可交换的，则成为abelian群第16页，共26页，编辑于2022年，星期六15。环环:oabelian 群，及一个乘法运算：o 满足结合律与加法的分配律 o如果加法满足交换律,则称交换环o例：整数 mod N（for any N）第17页，共26页，编辑于2022年，星期六16。域域：oabelian 加群
8、 o环 oabelian 乘群(ignoring 0)o例：integers mod P（P 为素数）第18页，共26页，编辑于2022年，星期六1717。Galois Galois 域域 如果 n是素数 p 则模运算modulo p 形成 Galois Field modulo p 记为：GF(p)第19页，共26页，编辑于2022年，星期六18。GF(p)GF(p)中的指数运算中的指数运算许多加密运算需要指数运算 b=ae mod p 重复乘法运算 eg.75=7.7.7.7.7 一个好的方法是不是平方 和乘法第20页，共26页，编辑于2022年，星期六1919。平方、乘法运算。平方、乘法
9、运算计算指数的快速有效算法 思想：重复平方运算 计算最终结果的乘法运算 第21页，共26页，编辑于2022年，星期六20。平方乘法运算例 75=74.7=3.7=10 mod 11;3129 mod 11=4 let base=a,result=1 for each bit ei(LSB to MSB)of exponent if ei=0 then square base mod p if ei=1 then multiply result by base mod psquare base mod p(except for MSB)at end the required answer is
10、result第22页，共26页，编辑于2022年，星期六2121。平方乘法举例。平方乘法举例n75=74.7=3.7=10 mod 11nbase res exp(5=1012)n7 1 nitialisen7.7=49=5 1.7=7 result=result x base,square base)n5.5=25=3 0(square base)n3.3=9 7.3=21=10 1(result=result x base,square base)第23页，共26页，编辑于2022年，星期六22。GF(p)GF(p)中的离散对数中的离散对数n指数的逆问题是寻找 整数模 p 的离散对数n即：
11、求 x 使得 ax=b mod p neg.x=log3 4 mod?(ie x st.3x=4 mod?)无解neg.x=log 2 3 mod 13=4（利用连续实验）n计算指数相对容易，求离散对数一般很难n可以证明若 p 素数,则总存在 离散对数（for any b!=0）na 的连续指数可以生成群（the group mod p）na 叫做一个本原根（a primitive root）n较困难的问题 第24页，共26页，编辑于2022年，星期六Greatest Common Divisorn数论中的一个普遍问题：决定最大公因子（greatest common divisor(GCD)）n GCD(a,b)是整除a,b的最大整数n经常用于证明两个数互素 第25页，共26页，编辑于2022年，星期六n OK！第26页，共26页，编辑于2022年，星期六