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

炸桌棺澡者馁俯扣砷叛泰皮圣敷款照歇碗项攻凡甫米售词都井署霹顺浚粳第13次课-密码学中常用数学知识课件第13次课-密码学中常用数学知识课件;密码学中常用的数学知识 群、环、域 素数和互素数 模运算 费尔玛定理和欧拉定理 素性检验 欧几里德算法 中国剩余定理;群G,*的定义: 一些数字组成的集合 一个二元运算，运算结果属于此集合（封闭性） 服从结合律。有单位元，逆元 。 如果是可交换的，则成为Abel群;域F,+,*的定义： F,+是Abel加群 环 F-{0},*是Abel 乘群 例： 整数 mod P （ P 为素数）;因子： 对整数 b!=0 及 a , 如果存在整数 m 使得 a=mb,称 b 整除 a, 也称b是a的因子。 记作 b|a 例 1,2,3,4,6,8,12,24 整除 24;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;互素数： 整数 a, b 互素是指 它们没有除1之外的其它因子。 8 与15 互素 8的因子1,2,4,8 15的因子 1,3,5,15 1 是唯一的公因子 记为：gcd(8,15)=1;设n是一正整数,a是整数,若 a=qn+r, 0≤rn, 则a mod n=r 若(a mod n)=(b mod n),称为a,b模n同余， 记为a≡b mod n 称与a模n同余的数的全体为a的同余类，记为[a]，a称为这个同余类的代表元素。;同余的性质： 若n|(a-b)，则a≡b mod n (a mod n) ≡(b mod n),则a≡b mod n a≡b mod n，则b≡a mod n a≡b mod n， b≡c mod n，则a≡c mod n;定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元。 证明思路： 用反证法证明a和Zn中任何两个不同的数相乘结果都不相同 从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1 mod n 设a为素数，Zp中每一个非零元素都与a互素，因此有乘法逆元，有乘法可约律 (a×b)=(a×c) mod n, b=c mod n;费尔玛定理： 若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1 mod p 证明： ;欧拉函数 设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n);爱拉托斯散(Eratosthenes)筛法 定理： 设n是正整数，若对所有满足p≤ 的素数p，都有 p | n，那么n一定是素数。;引理： 如果p为大于2的素数，则方程x2≡1 mod p的解只有和x≡1和x≡-1;Miller-Rabin素性概率检测法 n为待检测数，a为小于n的整数，将n-1表示为二进制形式bkbk-1…b0,d赋初值为1，算法核心如下： for i=k downto 0 do {x?d; d?(d×d) mod n; if d=1 and (x≠1)and(x≠n-1) then return False if bi=1 the d?(d×a) mod n } if d ≠1 then return False; return True 若返回False,n不是素数,若返回True,有可能是素数。;密码学中常用的数学知识 群、环、域 素数和互素数 模运算 费尔玛定理和欧拉定理 素性检验 欧几里德算法 中国剩余定理;2. 两个正整数互素，可以求一个数关于另一个数的乘法逆元 性质: 对任意非负整数a和正整数b, 有 gcd(a,b)=gcd(b,a mod b) 证明： ;Euclid(f,d) fd 1. X?f;Y?d; 2. If Y=0 then return X=gcd(f,d) 3. R=X mod Y 4. X=Y; 5. Y=R 6. Goto 2 ;欧几里德算法--求乘法逆元 若gcd(a,b)=1, b在模a下有乘法逆元(设ba)。 即存在xa,bx≡1 mod a 思路：求gcd(a,b)，当gcd(a,b)=1时，则返回b的逆元。 ;Extended Euclid(f,d) (fd) 1.（X1 X2 X3)?(1,0,f);(