密码学中的数论基础.ppt

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

1、数论是密码学特别是公钥密码学的基本工具。数论概念:研究“离散数字集合”运算是“+”,“×”例:整数:5+9=14;5×3=5+5+5=15多项式:x2+1+x=x2+x+1;x×x2+1=x3+x1.数论简介运算概念运算:模数运算模多项式运算进一步运算:指数运算,逆运算整除对整数b!=0及a,如果存在整数m使得a=mb,称b整除a,也称b是a的因子记作b

2、a例1,2,3,4,6,8,12,24整除241.因子:设a，b(b≠0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b

3、a，且称b是a的因子。1.

4、1素数和互素数整数具有以下性质：①a

5、1，那么a=±1。②a

6、b且b

7、a，则a=±b。③对任一b(b≠0)，b

8、0。④b

9、g，b

10、h则对任意整数m、n有b

11、(mg+nh)。1.1素数和互素数这里只给出④的证明，其他3个性质的证明都很简单。性质④的证明：由b

12、g，b

13、h知，存在整数g1、h1，使得g=bg1,h=bh1所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此b

14、(mg+nh)。1.1素数和互素数2.素数:称整数p(p>1)是素数，如果p的因子只有±1，±p。任一整数a(a>1)都能惟一地分解为以下形式

15、：其中p1>p2>…pt是素数，ai>0(i=1,…,t)。例如91=7×11，11011=7×112×131.1素数和互素数这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a(a>1)都能惟一地写成以下形式：其中ap≥0,等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数列表表示。例如：11011可表示为{a7=1,a11=2,a13=1}。两数相乘等价于对应的指数相加，即由k=mn可得：对每一素数p,kp=mp+np。而由a

16、b可得：对每一素数p,ap≤b

17、p。这是因为pk只能被pj(j≤k)整除。1.1素数和互素数3.互素数称c是两个整数a、b的最大公因子，如果①c是a的因子也是b的因子，即c是a、b的公因子。②a和b的任一公因子，也是c的因子。表示为c=gcd(a,b)。1.1素数和互素数由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(

18、a

19、,

20、b

21、)。由任一非0整数能整除0，可得gcd(a,0)=

22、a

23、。如果将a，b都表示为素数的乘积，则gcd(a,b)极易确定。例如：300=2

24、2×31×52；18=21×32gcd(18,300)=21×31×50=6一般由c=gcd(a,b)可得：对每一素数p，cp=min(ap,bp)。1.1素数和互素数由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。如果gcd(a,b)=1，则称a和b互素。1.1素数和互素数整数互素整数a,b互素是指它们没有除1之外的其它因子8与15互素8的因子1,2,4,815的因子1,3,5,151是唯一的公因子素数与不可约多项式素数:只有因子1和自身1是一个平凡素

25、数例2,3,5,7是素数,4,6,8,9,10不是素多项式或不可约多项式irreducible:不可写成其他因式的乘积x2+x=x×x+1是非不可约多项式;x3+x+1是不可约多项式一些素数200以内的素数:2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199素数分解把整数n写成素数的成绩分解整数要比乘法困难整数n的素数分解是把它写素数的乘积eg:91=7×

26、13;3600=24×32×52设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0≤r

27、a。1.2模运算同余有以下性质：①若n

28、(a-b)，则a≡bmodn。②(amodn)≡(bmodn)，则a≡bmodn。③a≡bmodn,则b≡am

29、odn。④a≡bmodn,b≡cmodn,则a≡cmodn。从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。1.2模运算求余数运算（简称求余运算）amodn将整数a映射到集合{0,1,…,n-1}，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质：①[(amodn)+(bmodn)]modn