密码学中常用数学知识.ppt

《密码学中常用数学知识.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、公钥密码密码学中常用的数学知识公钥密码体制的基本概念RSA算法4.1.1群、环、域群的定义:一些数字组成的集合一个二元运算，运算结果属于此集合（封闭性）服从结合律。有单位元，逆元。如果是可交换的，则成为Abel群*为乘法时，称为乘法群逆元（a-1）*为加法时，称为加法群逆元（-a）环的定义:Abel群，及一个乘法运算：满足结合律与加法的分配律如果加法满足交换律,则称交换环例：整数modN（foranyN）域的定义：是Abel加群环是Abel乘群例：整数modP（P为素数）Galois域：如果n是素数p，则模运算modulo

2、p形成GaloisFieldmodulop记为：GF(p)4.1.2素数和互素数因子：对整数b!=0及a,如果存在整数m使得a=mb,称b整除a,也称b是a的因子。记作b

3、a例1,2,3,4,6,8,12,24整除24素数：素数:只有因子1和自身1是一个平凡素数例2,3,5,7是素数,4,6,8,9,10不是200以内的素数：2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199素数分解：把整数n写成素数的乘积分解整数要比乘法

4、困难整数n的素数分解是把它写素数的乘积eg.91=7×13;3600=24×32×52互素数：整数a,b互素是指它们没有除1之外的其它因子。8与15互素8的因子1,2,4,815的因子1,3,5,151是唯一的公因子记为：gcd(8,15)=14.1.3模运算设n是一正整数,a是整数,若a=qn+r,0≤r

5、345678910111213141516171819202122232425262728293031323334同余的性质：若n

6、(a-b)，则a≡bmodn(amodn)≡(bmodn),则a≡bmodna≡bmodn，则b≡amodna≡bmodn，b≡cmodn，则a≡cmodn求余运算amodn将a映射到集合{0,1,…,n-1},求余运算称为模运算。模运算的性质[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)×(bmodn)]modn=(a×b)modn定理:设a∈Zn,gcd(a,n

7、)=1,则a在Zn有逆元。证明思路：用反证法证明a和Zn中任何两个不同的数相乘结果都不相同从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1modn设a为素数，Zp中每一个非零元素都与a互素，因此有乘法逆元，有乘法可约律(a×b)=(a×c)modn,b=cmodn定义Zn为小于n的所有非负整数集合Zn={0,1,2,…,n-1}4.1.4费尔玛定理和欧拉定理费尔玛定理：若p是素数，a是正整数且gcd(a,p)=1，则ap-1≡1modp证明：当gcd(a,p)=1,则a×Zp=Zp。又因为a×0≡0modp,所以a×(Zp-{0})=Zp-{0}即：{amodp,2amodp,…,

8、(n-1)amodp}={1,…,p-1}(amodp)×(2amodp)×…×(n-1)amodp=(p-1)!ap-1modp因此：(p-1)!ap-1modp=(p-1)!modp(p-1)!与p互素，所以乘法可约律，ap-1=1modp欧拉函数设n为一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为φ(n)欧拉定理若a和n互素,则aφ(n)=1modn例：Φ(6)=2,Φ(7)=6,Φ(8)=4显然，若n是素数，Φ(n)=n-1定理：若n是两个素数p和q的乘积，则Φ(n)＝Φ(p)Φ(q)=(p-1)(q-1)例：21=3×7，因此φ(21)=φ(3)×φ(7)=2×

9、6=124.1.5素性检验爱拉托斯散(Eratosthenes)筛法定理：设n是正整数，若对所有满足p≤的素数p，都有p

10、n，那么n一定是素数。对给定的数检验其是否为素数若要找出不大于n的所有素数：先将2到n之间的整数列出，从中删除小于等于的所有素数的倍数，余下的整数即是所要求的素数。此方法在n很大时，实际上是不可行的。Miller-Rabin素性概率检测法引理：如果p为大于2的素数，则方程x2≡1modp的解只有和x≡1和x≡-1