第二章 数论基础.ppt

第二章密码学的数学基础 数论理论介绍 1.数论介绍 数论概念: 研究“离散数字集合” 运算是“+” ,“×” ，例: 整数: 5 + 9 = 14; 5 × 3 = 5 + 5 + 5 = 15 多项式: x2 + 1 + x = x2+x+1; x × (x2+1) = x3+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: 不可写成其他因式的乘积 x2+x = x×(x+1) 是非不可约多项式; x3+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写成素数的成绩 定理: 每一个正合数,可表示为素数的成绩,并且不考虑成绩的顺序时,表示法是唯一的. 分解整数要比乘法困难 例：91 = 7 × 13 ; 3600 = 24 × 32 × 52 6.整数互素 整数 a, b 互素是指 它们没有除1之外的其它公因子 8 与15 互素 8的因子1,2,4,8 15的因子 1,3,5,15 1 是唯一的公因子 7.模算式 除法取余运算 同余( 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 8.模算术运算 加法 a+b mod n 减法 a-b mod n = a+(-b) mod n 9.乘法\除法 乘法: a.b mod n 重复加法 除法: a/b mod n 等价于a乘以b的逆元: a/b = a.b-1 mod n 如果n是素数, b-1 mod n 存在 即有: b.b-1 = 1 mod n 10 模递归运算 模递归运算是“模除求余” 例.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 11.运算法则 结合律: (a+b)+c = a+(b+c) mod n 交换律 (a+b)+c = (a+c)+b mod n 分配律 (a+b).c = (a.c)+(b.c) mod n 加法单位元\乘法单位元 0+w = w mod n 1×w = w mod n ? 几个重要定理 中国剩余定理 欧拉定理和费尔玛定理 威尔逊定理 平方剩余定理 中国剩余定理 目的:解同余方程组 中国剩余定理:设 是两两互素的正整数，则 有模 唯一解，由下式给出： 其中 ，且 剩余集 剩余类: 所有模m和r同余的整数组成一个剩余类[r] 完全剩余集,一组数r1, r2, …, rm, 分别属于不同的同余类,则称它构成了一个模m的完全剩余集合. 欧拉定理和费尔玛定理 欧拉函数：对任一正整数n，欧拉函数 表示小于n且与n互素的正整数的个数。 欧拉定理：若a和m互素，则 费尔玛定理：若p是素数，（a，p）=1，则 威尔逊定理 威尔逊定理：若p是素数，则 反之，若整数p满足 则p是一素数 平方剩余定理 平方剩余：a与p互素，p是奇素数，若 则称a是模p的平方剩余。 定理：若p是奇素数，则整数1,2,…,p-1中正好有(p-1)/2个是模p的平方剩余，其余的 (p-1)/2个是非平方剩余。 群，和有限域的概念 12 群 群的定