补充材料数论基础

1、数论基础,4.1数论简介习题,4.1.1素数和互素数1.因子设a，b(b0)是两个整数，如果存在另一整数m，使得a=mb，则称b整除a，记为b|a，且称b是a的因子。,4.1数论简介,数论是密码学特别是公钥密码学的基本工具，本章首先介绍密码学中常用的一些数论知识，然后介绍公钥密码体制的基本概念和几种重要算法。,整数具有以下性质：a|1，那么a=1。a|b且b|a，则a=b。对任一b(b0)，b|0。b|g，b|h，则对任意整数m、n有b|(mg+nh)。这里只给出的证明，其他3个性质的证明都很简单。性质的证明：由b|g，b|h知，存在整数g1、h1，使得g=bg1,h=bh1所以mg+nh=m

2、bg1+nbh1=b(mg1+nh1),因此b|(mg+nh)。,2.素数称整数p(p1)是素数，如果p的因子只有1，p。任一整数a(a1)都能惟一地分解为以下形式：其中p1p2pt是素数，ai0(i=1,t)。例如91=711，11011=711213,这一性质称为整数分解的惟一性，也可如下陈述：设P是所有素数集合，则任意整数a(a1)都能惟一地写成以下形式：其中ap0,等号右边的乘积项取所有的素数，然而大多指数项ap为0。相应地，任一正整数也可由非0指数列表表示。例如：11011可表示为a7=1,a11=2,a13=1。两数相乘等价于对应的指数相加，即由k=mn可得：对每一素数p,kp=m

3、p+np。而由a|b可得：对每一素数p,apbp。这是因为pk只能被pj(jk)整除。,3.互素数称c是两个整数a、b的最大公因子，如果c是a的因子也是b的因子，即c是a、b的公因子。a和b的任一公因子，也是c的因子。表示为c=gcd(a,b)。由于确定大数的素因子不很容易，所以这种方法不能直接用于求两个大数的最大公因子，如何求两个大数的最大公因子在下面介绍。如果gcd(a,b)=1，则称a和b互素。,由于要求最大公因子为正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(|a|,|b|)。由任一非0整数能整除0，可得gcd(a

4、,0)=|a|。如果将a，b都表示为素数的乘积，则gcd（a,b）极易确定。例如：300=22315218=2132gcd(18,300)=213150=6一般由c=gcd(a,b)可得：对每一素数p，cp=min(ap,bp)。,设n是一正整数，a是整数，如果用n除a，得商为q，余数为r，则a=qn+r,0rn,其中x为小于或等于x的最大整数。用amodn表示余数r，则。如果(amodn)=(bmodn)，则称两整数a和b模n同余，记为abmodn。称与a模n同余的数的全体为a的同余类，记为a，称a为这个同余类的表示元素。注意：如果a0(modn)，则n|a。,4.1.2模运算,同余有以下性

5、质：若n|(a-b)，则abmodn。(amodn)(bmodn)，则abmodn。abmodn,则bamodn。abmodn,bcmodn,则acmodn。从以上性质易知，同余类中的每一元素都可作为这个同余类的表示元素。,求余数运算（简称求余运算）amodn将整数a映射到集合0,1,n-1，称求余运算在这个集合上的算术运算为模运算，模运算有以下性质：(amodn)+(bmodn)modn=(a+b)modn。(amodn)-(bmodn)modn=(a-b)modn。(amodn)(bmodn)modn=(ab)modn。,性质的证明：设（amodn）=ra，(bmodn)=rb，则存在整数

6、j、k使得a=jn+ra，b=kn+rb。因此(a+b)modn=(j+k)n+ra+rbmodn=(ra+rb)modn=(amodn)+(bmodn)modn（证毕）性质、的证明类似。,例4.1设Z8=0,1,7，考虑Z8上的模加法和模乘法，结果如表4.1所示。（见77页表4.1）从加法结果可见，对每一x，都有一y，使得x+y0mod8。如对2，有6，使得2+60mod8，称y为x的负数，也称为加法逆元。对x，若有y，使得xy1mod8，如331mod8，则称y为x的倒数，也称为乘法逆元。本例可见并非每一x都有乘法逆元。,一般地，定义Zn为小于n的所有非负整数集合，即Zn=0,1,n-1，

7、称Zn为模n的同余类集合。其上的模运算有以下性质：交换律(w+x)modn=(x+w)modn(wx)modn=(xw)modn结合律(w+x)+ymodn=w+(x+y)modn(wx)ymodn=w(xy)modn分配律w(x+y)modn=wx+wymodn单位元(0+w)modn=wmodn(1w)modn=wmodn加法逆元对wZn，存在zZn，使得w+z0modn，记z=-w。,此外还有以下性质：如果(a+b)(a+c)modn，则bcmodn，称为加法的可约律。该性质可由(a+b)(a+c)modn的两边同加上a的加法逆元得到。,然而类似性质对乘法却不一定成立。例如63672mo

8、d8，但37mod8。原因是6乘以0到7得到的8个数仅为Z8的一部分，见例4.1。即如果将对Z8作6的乘法6Z8（即用6乘Z8中每一数）看作Z8到Z8的映射的话，Z8中至少有两个数映射到同一数，因此该映射为多到一的，所以对6来说，没有惟一的乘法逆元。但对5来说，551mod8，因此5有乘法逆元5。仔细观察可见，与8互素的几个数1，3，5，7都有乘法逆元。这一结论可推广到任一Zn。,定理4.1设aZn，gcd(a,n)=1，则a在Zn中有乘法逆元。证明：首先证明a与Zn中任意两个不相同的数b、c（不妨设cb）相乘，其结果必然不同。否则设abacmodn，则存在两个整数k1,k2，使得ab=k1n

9、+r，ac=k2n+r，可得a(b-c)=(k1-k2)n，所以a是(k1-k2)n的一个因子。又由gcd(a，n)=1，得a是k1-k2的一个因子，设k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，与0cbn矛盾。所以|aZn|=|Zn|，又知aZnZn，所以aZn=Zn。因此对1Zn，存在xZn，使得ax1modn，即x是a的乘法逆元。记为x=a-1。（证毕）,设p为一素数，则Zp中每一非0元素都与p互素，因此有乘法逆元。类似于加法可约律，可有以下乘法可约律：如果(ab)(ac)modn且a有乘法逆元，那么对(ab)(ac)modn两边同乘以a-1，即得bcmodn,费尔

10、玛(Fermat)定理和欧拉(Euler)定理在公钥密码体制中起着重要作用。1.费尔玛定理定理4.2(Fermat)若p是素数，a是正整数且gcd(a,p)=1，则ap-11modp。证明：由4.1.2的讨论知当gcd(a,p)=1时,aZp=Zp，其中aZp表示a与Zp中每一元素做模p乘法。又知a00modp，所以aZp-0=Zp-0，a(Zp-0)=Zp-0。即amodp,2amodp,(p-1)amodp=1,2,p-1,4.1.3费尔玛定理和欧拉定理,所以a2a(p-1)a(amodp)(2amodp)(p-1)amodp)modp(p-1)!modp另一方面a2a(p-1)a=(p-

11、1)!ap-1因此(p-1)!ap-1(p-1)!modp由于(p-1)!与p互素，因此(p-1)!有乘法逆元，由乘法可约律得ap-11modp。（证毕）,Fermat定理也可写成如下形式：设p是素数，a是任一正整数，则apamodp。2.欧拉函数设n是一正整数，小于n且与n互素的正整数的个数称为n的欧拉函数，记为(n)。例如：(6)=2，(7)=6，(8)=4。若n是素数，则显然有(n)=n-1。例如：由21=37，得(21)=(3)(7)=26=12。,定理4.3若n是两个素数p和q的乘积，则(n)=(p)(q)=(p-1)(q-1)。证明：考虑Zn=0,1,pq-1，其中不与n互素的数有

12、3类，A=p,2p,(q-1)p，B=q,2q,(p-1)q,C=0，且AB=，否则ip=jq，其中1iq-1，1jp-1,则p是jq的因子，因此是j的因子，设j=kp，k1。则ip=kpq，i=kq，与1iq-1矛盾。所以(n)=|Zn|-|A|+|B|+|C|=pq-(q-1)+(p-1)+1=(p-1)(q-1)=(p)(q)（证毕）,3.欧拉定理定理4.4（Euler）若a和n互素，则a(n)1modn。证明：设R=x1,x2,x(n)是由小于n且与n互素的全体数构成的集合，aR=ax1modn,ax2modn,ax(n)modn，对aR中任一元素aximodn，因a与n互素，x1与n

13、互素，所以axi与n互素，且aximodnd。Euclid（f,d）1.Xf;Yd；2.ifY=0thenreturnX=gcd(f,d)；3.R=XmodY；4.X=Y；5.Y=R；6.goto2。,例4.2求gcd(1970,1066)。1970=11066+904,gcd(1066,904)1066=1904+162,gcd(904,162)904=5162+94,gcd(162,94)162=194+68,gcd(94,68)94=168+26,gcd(68,26)68=226+16,gcd(26,16)26=116+10,gcd(16,10)16=110+6,gcd(10,6)10=

14、16+4,gcd(6,4)6=14+2,gcd(4,2)4=22+0,gcd(2,0)因此gcd(1970,1066)=2。,中国剩余定理是数论中最有用的一个工具，定理说如果已知某个数关于一些两两互素的数的同余类集，就可重构这个数。例如：Z10中每个数都可从这个数关于2和5（10的两个互素的因子）的同余类重构。比如已知x关于2和5的同余类分别是0和3，即xmod20，xmod53。可知是偶数且被5除后余数是3，所以可得8是满足这一关系的惟一的x。,4.1.6中国剩余定理,定理4.5（中国剩余定理）设m1,m2,mk是两两互素的正整数，则一次同余方程组对模M有惟一解:其中ei满足,证明：设,i=

15、1,2,k，由Mi的定义得Mi与mi是互素的，可知Mi在模mi下有惟一的乘法逆元，即满足的ei是惟一的。,下面证明对i1,2,k，上述x满足ai(modmi)x。注意到当ji时，mi|Mj，即Mj0(modmi)。所以(Mjejmodmj)modmi(Mjmodmi)(ejmodmj)modmi)modmi0而(Mi(eimodmi)modmi(Miei)modmi1所以x(modmi)ai，即ai(modmi)x,下面证明方程组的解是惟一的。设x是方程组的另一解，即xai(modmi)(i=1,2,k)由xai(modmi)得x-x0(modmi)，即mi|(x-x)。再根据mi两两互素，有M|(x-x)，即x-x0(modM)，所以x(modM)=x(modM)。(证毕)中国剩余定理提供了一个非常有用的特性，即在模M下可将非常大的数x由一组小数(a1,a2,ak)表达。,例4.4由以下方程组求x。解：M=2357=210