密码学课件：二、初等数论

初等数论数论简介以下内容部分来自于“百度百科”1.整数分为正整数（自然数）、负整数和零2.确切地说，数论就是一门研究整数性质的整数性质的学科。整数的特性，比如，加、减、乘、除四则运算中，加、减、乘可以在整数范围内毫无阻碍地进行，但是除法却不行。3.在古希腊时代，数学家对数论的整除性问题就有过系统的研究，在我国古代，许多著名的数学著作中都记载有数论的相关内容，如，孙子定理、勾股数组、百钱买百鸡、韩信点兵问题等。数论简介4.在整数性质的研究中，人们发现素数是构成正整数的基本“材料”，而算术基本定理正是深刻揭示正整数与素数的重要关系。因此，深入研究整数的性质就划归为对素数性质素数性质的研究。5.18世纪末，历代数学家积累的关于整数性质的零散结论已经十分丰富。德国数学家高斯集前人之大成，撰写算术探讨一书，于1800年寄给法国科学院，但是遭到拒绝出版，高斯于1801年自己出版，标志现代数论新纪元的开始。数论简介6.按照研究方法，分为初等数论、解析数论、代数数论和几何数论。初等数论是数论中不求助于其他数学学科的帮助，只依靠初等方法来研究整数性质的分支，比如著名的“孙子定理”的证明就是典型的初等方法。7.早期的时候，人们并不清楚它的实际意义，目前，由于近代计算机学科和应用数学学科的发展，数论得到了广泛应用。比如，在计算方法、代数编码、组合论、密码学中密码学中都得到了广泛应用。数论简介8.数论在数学中具有独特地位，高斯：“数学是科学的皇后，数论是数学中的皇冠”。9.在我国近代，从20世纪30年代开始，我国在解析数论方面都有过重要贡献，如华罗庚在三角和估值、堆砌素数等方面的研究成果享有盛名。1949年以后，陈景润证明“哥德巴赫猜想”的“一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”，至今仍是最好的结果。数论简介数论中的数学方法对数学的发展起着重要作用。许多数论难题的解决是对数学思维方法的极大挑战，由此产生了大量代数的、解析的、初等的、高等的、简单的和高深复杂的数学方法。内容 素数与互素 同余与模运算 欧拉（Euler）定理 几个重要算法 中国剩余定理 模为素数的二次剩余 离散对数素数与互素1 整除定义：如果整数a、b、c之间存在关系a=bc且b0，则称b整除a或者a能被b整除，且b是a的因子或除数，a是b的倍数。记为b|a。素数与互素1 整除整除的性质：a|a如果a|1，则有a=1对于任何a0，则有a|0如果a|b且b|a，则有a=b如果a|b且b|c，则有a|c如果a|b且a|c，那么对所有的x，yZ有a|(bx+cy)，Z表示整数集。素数与互素1 整除整除的特殊例子末1位能被2整除，则该数能被2整除末2位能被4整除，则该数能被4整除末3位能被8整除，则该数能被8整除素数与互素1 整除整除的特殊例子末1位能被5整除，则该数能被5整除末2位能被25整除，则该数能被25整除末3位能被125整除，则该数能被125整除若各位数字之和能被3整除，则该数能被3整除若各位数字之和能被9整除，则该数能被9整除素数与互素1 整除7的倍数若一个整数的个位数字截去，再从余下的数中，减去个位数的2倍，如果差是7的倍数，则原数能被7整除。例：133是否7的倍数？过程如下：13-327，所以133是7的倍数；又例如判断6139是否7的倍数的过程如下：613-92595，59-5249，所以6139是7的倍数，余类推。如果差太大，可继续上述截尾、倍大、相减、验差的过程，直到能清楚判断为止。素数与互素1 整除11的倍数若偶数位数字之和与奇数位数字之和的差能被11整除，则该数能被11整除。例如：1364是否是11的倍数？偶数位数字之和与奇数位数字之和的差为0截尾法：136-41=132，13-21=11素数与互素1 整除11的倍数使用“截尾、倍大（1倍）、相减、验差”的过程。13的倍数使用“截尾、倍大（4倍）、相加、验和”的过程。17的倍数使用“截尾、倍大（5倍）、相减、验差”的过程。19的倍数使用“截尾、倍大（2倍）、相加、验和”的过程。例：验证23446是否是19的倍数？1 整除若一个整数的末三位与3倍的前面的隔出数的差能被17整除，则这个数能被17整除。（例如，17017：17-173=-34，能被17整除）若一个整数的末三位与7倍的前面的隔出数的差能被19整除，则这个数能被19整除。若一个整数的末四位与前面5倍的隔出数的差能被23(或29)整除，则这个数能被23(或29)整除其他规律素数与互素素数与互素2 素数定义：如果p1且p的因子仅为1和p，则整数p被称为素数或质数。非素数的整数被称为合数，1既不是素数也不是合数。素数与互素3 最大公因子设a,b,cZ，如果c|a且c|b，则称c是a与b的公因子或公约数。如果d满足以下条件，则称正整数d是a与b的最大公因子：（1）d是a与b的公因子（2）如果c也是a与b的公因子，则c必是d的因子最大公因子是公因子中的最大的那一个，记为dgcd(a,b)=maxc|c|a且c|b如果a和b全为0，则它们的公因子和最大公因子均无意义。素数与互素3 最大公因子例，gcd(1080,945)=1351080=23335945=3357素数与互素3 最大公因子互素：如果a与b的最大公因子为1，则称整数a与b互素，即gcd(a,b)=1。同余与模运算3 最大公因子带余数除法定理：设a和b是两个整数，b0，则存在唯一的一对整数q和r，使得a=bq+r(0r0|x,yZ，由于整数a,b不全为0，可知S非空，设S中最小的正整数为e，令e=am+bn，m,nZ。由带余除法定理，可设a=qe+r，0re，所以r=a-qe=a-q(ma+nb)=(1-qm)a-qnb。若r0，则rS，由于e是S中的最小正整数，与r0，所以ed，另一方面，由于d是a,b的一个正公因子，知de，故d=e。素数与互素3 最大公因子（6）gcd(a,b)=1的充要条件是存在整数u,v使得au+bv=1。证明：由性质（2）和（5）既得。素数与互素3 最大公因子（7）如果gcd(a,x)=gcd(b,x)=1，那么gcd(ab,x)=1证明：根据性质（2）即推论，存在整数t,y,z,w，使得at+xy=1，bz+xw=1，上两式相乘并整理得，abtz+x(w+y+xwy)=1由性质（6）得，gcd(ab,x)=1素数与互素4 算术基本定理定理1：设a是大于1的整数，则a的除1外最小正因子q是一素数，且当a是合数时，证明：假设q不是素数，由定义，q除1及本身外还有一个正因子q1，因而1q1q，但q|a，所以q1|a，这与q是a的除1外最小正因子相矛盾，故q是素数。当a是合数时，则a=a1q，且a11，由于q是a的除1外最小正因子，所以qa1，q2qa1=a，故aq aq 素数与互素4 算术基本定理说明：判断n是否为素数的最笨拙的方法是依次用2,3,n-1去除n，如果这n-2个数都不整除n，则n为素数，否则n不是素数。这种方法要作n-2次除法运算，所花费的时间至少要与n成正比。根据定理1，我们只需用 以内的整数去除n即可判别n是否为素数。n素数与互素4 算术基本定理定理2：若p是一个素数，a是任一整数，则a能被p整除或p与a互素。证明：因p是素数，由素数的定义有gcd(p,a)=1，或者gcd(p,a)=p素数与互素4 算术基本定理推论1：设a1,a2,an是n个整数，p是素数，若p|a1a2an，则p一定能够整除某一个ai。证明：假设a1,a2,an都不能被p整除，则由定理2，gcd(p,ai)=1，i=1,2,n。因此gcd(p,a1a2an)=1，这与p|a1a2an矛盾，结论成立。素数与互素4 算术基本定理定理3：任何大于1的正整数a可以写成素数之积，即a=p1p2pn，其中pi（1in）是素数。证明：当a是素数时，定理成立。当a是合数时，由定理1知必存在素数p1，且 ，所以a=p1a1，且1 a1a。若a1是素数，则定理成立。若a1是合数，同理，则必有素数p2以及适合1a2a1的正整数a2，使a=p1p2a2成立。由于a是有限的，所以有限次重复上述过程可得a=p1p2pn，其中pi（1in）是素数。ap 11素数与互素4 算术基本定理算术基本定理：设2aZ，则a可以分解成素数幂的乘积 其中，pi（i=1,2,k）是互不相同的素数，i（i=1,2,k）是正整数。若不计因子顺序，上式唯一。证明：由定理3可知，任何大于1的整数可以表示成只需证明唯一性。假设pi（i=1,2,n）与qi（i=1,2,k）都是素数，p1p2pn，q1q2qk，且a=p1p2pn=q1q2qk，因为p1|a=q1q2qk，则有某个qj，使得p1|qj，从而p1=qj。同理，有某个pi，q1=pi。又p1p2 pn，q1q2qk，可知p1=q1。重复上述过程，得到n=k，pi=qi，结论成立。kkpppa2121kkpppa2121素数与互素例：写出51480的标准分解式：51480=233251113其中2,3,5,11,13都是素数。分解整数：524287？素数与互素关于素数的一些基本结论（1）素数有无穷多个，但目前尚无有效办法确定所有素数。例如，将形如Mn=2n1的数称为梅森数（Mersenne,17世纪法国数学家）。以下是最近发现的一些梅森素数。序号pMp=2p-1Mp的位数发现时间发现者1231古代古人2371古代古人4225,964,9511221646305770772477,816,2302005年2月18日GIMPS/Martin Nowak43*30,402,4573154164756529438719,152,0522005年12月15日GIMPS/Curtis Cooper及Steven Boone44*32,582,6571245750260539678719,808,3582006年9月4日GIMPS/Curtis Cooper及Steven Boone45*37,156,66720225440630822092711,185,2722008年9月6日G I M P S/H a n s-M i c h a e l Elvenich46*42,643,80116987351656231475112,837,0642009年4月12日GIMPS/Odd M.Strindmo47*43,112,60931647026969715251112,978,1892008年8月23日GIMPS/Edson Smith48*57,885,16158188726672428595117,425,1702013年1月25日GIMPS/Curtis Cooper截止2013年2月6日，已经发现了48个梅森素数，并且确定M25964951位于梅森素数序列中的第42位。列表如下：（现在还不知道在第42个梅森素数（M25,964,951）和第48个（M57,885,161）之间是否还存在未知梅森素数，所以在其序号之前用*标出）素数与互素（2）素数定理描述素数的大致分布情况。素数的出现规律一直困惑着数学家。单个来看，素数在正整数中的出现没有规律，但从总体上看，素数的个数有规律可循：设xZ，则不超过x的素数个数可以近似的用x/lnx表示。同余与模运算1.带余除法对于任意的两个正整数a和b，存在唯一确定的两个整数k和r，满足a=kb+r且0r1，则m|a，当然也有am0a mod m故：ama mod m欧拉（Euler）定理6.欧拉定理推论（2）若gcd(a,m)=1，有a(m)1 mod m，因a,m互素，故有a(m)-1a-1 mod m，a(m)+1a mod m；对于m为素数,(m)=m-1,代入有ama mod m,am-2a-1 mod m。（3）若m=pq且p和q为素数，aZ，如果gcd(a,m)=p或q，则同样有a(m)+1a mod m。加解密运算中的几个常用算法定理：对任意两个整数a和b，不妨设ab0，有gcd(a,b)=gcd(b,a mod b)（被除数与除数的最大公因子和除数与余数的最大公因子相同）证明：对于任意整数a和b，存在整数k满足a=kb+a mod b设d是a与b的任一公因子，故d|a且d|b，所以d|(a-kb)，即d|(a mod b)，因此，d是b与a mod b的公因子。同理同理，若d是b与a mod b的公因子，则d也是a与b的公因子。所以a与b的全部公因子同b与a mod b的全部公因子完全相同，因此他们的最大公因子也相同，即gcd(a,b)=gcd(b,a mod b)。1.基本欧几里得算法（求最大公因子）计算gcd(a,b)，等价于计算gcd(b,r0)，r0=a mod b计算gcd(b,r0)，等价于计算gcd(r0,r1)，r1=b mod r0计算gcd(r0,r1)，等价于计算gcd(r1,r2)，r2=b mod r1如此反复，由于r0r1r2，则最终的余数rn+1=0当余数为0时，有gcd(rn,0)=rn因此：gcd(a,b)=gcd(rn,0)=rn1.基本欧几里得算法（求最大公因子）1.基本欧几里得算法（求最大公因子）例：求1970和1066的最大公因子。1970=11066+904，1066=1904 +162，904=5162 +94，162=194 +68，94=168 +26，68=226 +16，26=116 +10，16=110 +6，10=16 +4，6=14 +2，4=22 +0。显然gcd(2,0)=2，因此gcd(1970,1066)=2。1.基本欧几里得算法（求最大公因子）这个过程又称为辗转相除法，表示如下：a=k0b+r0b=k1r0+r1r0=k2r1+r2rn-2=knrn-1+rnrn-1=kn+1rn+0其中，r0=a mod b，r1=b mod r0，ri=ri-2 mod ri-1(i=2,3,n)。由于r0r1r20且他们皆为整数，因此在经过有限步后余数必为0。当余数为0时，有gcd(rn,0)=rn。倒推回来，可得：rn=gcd(rn,0)=gcd(rn-1,rn)=gcd(rn-2,rn-1)=gcd(r0,r1)=gcd(b,r0)=gcd(a,b)1.基本欧几里得算法（求最大公因子）说明：基本欧几里得算法的假设是ab0，如果a、b中有负整数，则可通过其绝对值来求最大公因子，若其中一个为0，则最大公因子为非0的那一个，若两个都为0，则最大公因子无意义。2.扩展欧几里得算法（求乘法逆元）回顾乘法逆元的定义：设a,b,n为整数且n1，如果ab1 mod n，则a,b称为互为模n的乘法逆元，记为ba-1 mod n。如何求乘法逆元？如何求乘法逆元？一种方法：由欧拉定理，若整数a与n互素，那么a(n)-1a-1 mod n。如果n是素数，则(n)=n-1；但如果n不是素数，则不容易求出(n)。下面介绍另一种常用方法。2.扩展欧几里得算法（求乘法逆元）由欧几里得算法可知：gcd(a,b)=rn由整个过程的倒数第二行可得：rn=rn-2-rn-1kn再由倒数第三行可得：rn-1=rn-3-rn-2kn-1，代入上式得：gcd(a,b)=(1+knkn-1)rn-2-knrn-3再由倒数第四行可得：rn-2=rn-4-rn-3kn-2代入上式得：。如此下去，最终可将gcd(a,b)表示出a和b的关于k0到kn的整系数线性组合，即sa+tb=gcd(a,b)。如果a与b互素，即gcd(a,b)=1，则有1=sa+tb，所以sa1 mod b，因此可求得a的乘法逆元：sa-1 mod b。整理：若r2=0，gcd(a,b)=r1，则：r1=(1+k0k1)b-k1a，s=-k1若r3=0，gcd(a,b)=r2，则：r2=(1+k1k2)a-(k0(1+k1k2)+k2)b，s=(1+k1k2)若r4=0，gcd(a,b)=r3，则：r3=(1+k2k3)+k0(k3+k1(1+k2k3)b-(k3+k1(1+k2k3)a，s=-(k3+k1(1+k2k3)若r5=0，gcd(a,b)=r4，则：r4=(1+k3k4)+k1(k4+k2(1+k3k4)a-(k0(1+k3k4)+k1(k4+k2(1+k3k4)+(k4+k2(1+k3k4)bs=(1+k3k4)+k1(k4+k2(1+k3k4)。例，设a=127，n=57，求a-1 mod n127=257+13 57=413+5 13=25+3 5=13+2 3=12+1 2=21+0gcd(127,57)=gcd(1,0)=1例中r5=0，gcd(a,b)=r4=1。k0=2，k1=4，k2=2，k3=1，k4=1s=(1+k3k4)+k1(k4+k2(1+k3k4)=(1+11)+4(1+2(1+11)=22。验证：sa mod n=22127 mod 57=2794 mod 57=12794=4957+1例，设a=83，n=37，求a-1 mod n83=237+937=49+1 9=91+0gcd(83,37)=gcd(1,0)=1例中r2=0，gcd(a,b)=r1=1。k0=2，k1=4，k2=9s=-k1=-4验证：sa mod n=-483 mod 37=-332 mod 37=1-332=-937+1例，设a=8191，n=1975，求a-1 mod n8191=41975+2911975=6291+229 291=1229+62 229=362+43 62=143+19 43=219+5 19=35+4 5=14+1 4=41+0gcd(8191,1975)=gcd(1,0)=13.快速指数算法在RSA等公钥密码算法中，经常面临着需要计算大量的底数和指数均为大整数的模幂运算。如果按照模幂运算的含义直接计算，一方面可能由于中间结果过大而超过计算机允许的整数取值范围，一方面工作量过大。3.快速指数算法从两个方面处理这个问题。一是利用模运算的性质：am mod n=(au mod nav mod n)mod n，m=u+v。二是考虑如何提高指数运算的有效性，例如通过计算出x,x2,x4,x8,x16，可方便组合出指数1到31之间的任何一个整数次幂，并且只需4次乘法运算即可得到答案。3.快速指数算法求am mod n的快速指数算法：将m表示成二进制的形式：m=(bkbk-1b0)2，即因此，有所以：kimibi,1,0,20kiaaaiiibibm,1,0,0220kinnananaiiiibbm,1,0,modmodmodmod02023.快速指数算法根据以上原理，可得计算am mod n的快速指数算法如下：c=0;d=1;for i=k down to 0 do c=2c;d=(dd)mod n;if bi=1 then c=c+1;d=(da)mod n;Return d;其中，变量c表示指数的变化情况，终值为m变量d表示相对于指数c的幂模n的变化情况，终值为am mod n3.快速指数算法例：用快速指数算法计算20072008 mod 20092008=(11111011000)2i109876543210bi11111011000c013715316212525150210042008d120072001188113857401152169013968613691773中国剩余定理1.n次同余方程首先给出1元n次同余方程的定义及其解的情况。定义：设f(x)=anxn+a1x+a0是未知数x的整系数多项式，称 f(x)0 mod m是关于未知数x的模m的一元同余方程，简称模m的同余方程。若an 0 mod m，则称式f(x)0 mod m为n次同余方程。1.n次同余方程设a是整数，当x=a时，方程 f(x)=anxn+a1x+a00 mod m成立，则称a是方程f(x)0 mod m的解。问题：当x=a时，x=a+m，x=a+2m，等是否是方程的解？分析：an(a+qm)n mod m=(an mod m(a+qm)n mod m)mod m=(an mod m(a+qm)mod m)n mod m)mod m=(an mod m(a mod m+qm mod m)mod m)n mod m)mod m=(an mod m(a mod m+0)mod m)n mod m)mod m=(an mod m an mod m)mod m=anan mod m1.n次同余方程对于同余方程：f(x)=anxn+a1x+a00 mod m由分析可知，当x=a是方程的解时，x=a+qm(aZ)也是方程的解。针对形如式x=a+qm的解，可表示成同余等式：xa mod m。因此，同余方程的一个解就是模m的一个同余类同余类。可知，同余方程的解数指其关于模m互不同余的所有解的个数。1.n次同余方程同余方程的解的个数：模m的剩余类只有m个，因此，模m的同余方程的解数不会超过m。在模m的任意取定的一组完全剩余系中，适合同余方程的解的个数就是同余方程的解数。特别的特别的，可以通过将整数x=0,1,m-1逐个代入同余方程验证其是否成立的方法找出其全部解。2.一次同余方程定义：设a，b是整数，x是未知数，则 axb mod m,a 0 mod m称为模m的一次一次同余方程。下面分析一次同余方程的解的情况。2.一次同余方程定理：设a，b是整数，d=gcd(a,m)，a 0 mod m，则方程axb mod m有解的充分必要条件是d|b。若方程有解，则恰有d=gcd(a,m)个解。证明：必要性 若同余方程有解xt mod m，则必定存在整数y，使得 b-ax=my，即ax+my=b。因为d|a，d|m，所以d|b。充分性 由于d=gcd(a,m)，根据最大公因数的性质（2），存在整数u,v，使得au+mv=d。由于d|b，则有整数c使得b=cd。于是a(cu)+m(cv)=cd=b，因而方程有解xcu mod m。（下面探讨解的个数）2.一次同余方程定理：设a，b是整数，d=gcd(a,m)，a 0 mod m，则方程axb mod m有解的充分必要条件是d|b。若方程有解，则恰有d=gcd(a,m)个解。证明：若同余方程axb mod m有解x0，则存在y0，使得x0与y0是不定方程ax+my=b的特解，且其全部整数解是显然，此式所确定的x都满足方程axb mod m。),1,0(),gcd(),gcd(00ttmaayytmamxx2.一次同余方程定理：设a，b是整数，d=gcd(a,m)，a 0 mod m，则方程axb mod m有解的充分必要条件是d|b。若方程有解，则恰有d=gcd(a,m)个解。证明：由于d=gcd(a,m)，令t=dq+r（qZ，r=0,1,2,d-1），代入全部整数解式中，得容易验证，当r=0,1,2,d-1时，相应的解对于模m是两两互不同余的，所以同余方程axb mod m恰有d个解。mrdmxrdmqmxtmamxxmod),gcd(000mdmdxdmxdmxxxmod)1(,2,00002.一次同余方程由定理可知，当d=gcd(a,m)且d|b时同余方程有解，此时求解同余方程axb mod m化归为求解同余方程由此可知，一次同余方程的求解问题转换成求解形如同余方程axb mod m，gcd(a,m)=1，a 0 mod m的问题。说明说明：方程axb mod m和 的解数与模不同，所以两个方程不是同解方程。对于此同余方程，有四种常用的求解方法。dmdbxdamoddmdbxdamod例，求解方程：（1）16x18 mod 22计算d=gcd(a,m)=gcd(16,22)=2，所以d|b，则方程有解。因d=2，所以方程有两个解两个解。穷举法：将x=0,1,2,21分别代入方程，计算确认，发现x=8和x=19是方程的解，所以方程的解为：x8 mod 22和x19 mod 22（2）8x9 mod 11（(16/d)x(18/d)mod(22/d)）计算gcd(8,11)=1，则方程有一个解。穷举法：将x=0,1,2,10分别代入方程，只有当x=8时是方程的解，所以方程的解为x8 mod 112.一次同余方程（1）穷举法令未知数x依次取x=0,1,2,m-1并代入方程进行验证，若有整数解x=r时方程成立，则xr mod m即为方程的解。当模m的数值很大时，计算了较大。（2）辗转相除法由于gcd(a,m)=1，辗转相除求出适合au+mv=1的整数u和v，此时，xbu mod m即为方程的整数解。（3）公式法由于gcd(a,m)=1，根据Euler定理可知有a(m)1 mod m，其中(m)是欧拉函数。由原方程可得axba(m)b mod m，因gcd(a,m)=1，故xa(m)-1b mod m，即为方程的解2.一次同余方程（4）分数法首先，将同余方程写成 的形式，然后在 的分子和分母位置上加上m的适当倍数（或者分子分母同时乘以一个与m互素的非零整数），使得通过约分后（或者分子分母同时模m后）所得新分数的分母的绝对值逐渐变小。如果变形后的新分母为1或-1，分子为r，则此时可得方程的解为 xr mod m 或 x-r mod m此法在一次同余方程的求解中往往比较有效。mabxmodab2.一次同余方程例，解同余方程8x9 mod 11.解：此时gcd(8,11)=1，同余方程只有一个解。（1）穷举法将x=0,1,2,10分别代入方程，只有当x=8时是方程的解。故x8 mod 11（2）辗转相除法由于11=18+3,8=23+2,3=12+1,经逆推计算可得(-4)8+311=1,即8(-4)9+1139=9，因此x(-4)98 mod 11是同余方程的解。2.一次同余方程例 解同余方程8x9 mod 11.解 此时gcd(8,11)=1，同余方程只有一个解。（3）公式法因为11是素数，(11)=10，故x9898 mod 11是同余方程的解。（4）分数法11mod811mod18211525811989x11mod811mod1812306265252427383989x3.中国剩余定理我国古代的孙子算经中的问题：今有物不知其数，三三数之剩二，x2 mod 3五五数之剩三，x3 mod 5七七数之剩二，x2 mod 7问物几何？求x？3.中国剩余定理定义：设n1,n2,nk是大于1的正整数，a1,a2,ak是整数，由k(k2)个一元一次同余方程联立而成的同余式称为一元一次同余方程组。设x=a是同余方程组的解，设M=n1,n2,nk（n1到nk的最小公倍数），则x=a+qM(qZ)都是方程组的公共解，记为xa mod M，因此方程组的解是模M的一个剩余类。kknaxnaxnaxmodmodmod22113.中国剩余定理中国剩余定理：设n1,n2,nk是两两互素的正整数，那么对任意的整数a1,a2,ak，一次同余方程组 xai mod ni,i=1,2,k在同余意义下必有唯一解，且这个解是其中，证明：先证同余方程不会有多个解。设有两个解c1和c2，那么对所有ni，都有c1c2ai mod ni，故c1-c20 mod ni，ni|(c1-c2)。又因为所有的ni两两互素，所以N|(c1-c2)，即c1c2 mod N，也就是c1、c2在mod N下同余，即在模N同余意义下是同一个解，因此，同余方程组在不可能有多个解。NaNNxkiiii11modiiiiikiinNNnNNnNmod1,/,113.中国剩余定理中国剩余定理：设n1,n2,nk是两两互素的正整数，那么对任意的整数a1,a2,ak，一次同余方程组 xai mod ni,i=1,2,k在同余意义下必有唯一解，且这个解是其中，证明：下证 为方程的解。NaNNxkiiii11modiiiiikiinNNnNNnNmod1,/,11NaNNxkiiii11mod3.中国剩余定理证明：ni与Ni互素，因此Ni关于模ni的逆Ni-1存在。另一方面且若ji，则nj|Ni。因此所以（性质：若ab mod n，d|n，d0，则ab mod d）是此同余方程组的解。得证iiinNNmod11jjjjjjkijiiinanaNNnaNNmodmodmod111kiiiiNaNNx11mod3.中国剩余定理例，解同余方程组11mod97mod25mod43mod1xxxx3.中国剩余定理解：方程组中，n1=3,n2=5,n3=7,n4=11，两两互素，满足中国剩余定理的条件。a1=1,a2=4,a3=2,a4=9。N1=5711,N2=3711,N3=3511,N4=357下面计算N1,N2,N3,N4的逆。由于N1 mod 3 2121，故可取N1-1=1 mod 3=1；由于N2 mod 5 3211，故可取N2-1=1 mod 5=1；由于N3 mod 7 3544，故可取N3-1=2 mod 7=2；由于N4 mod 11 3576，故可取N4-1=2 mod 3=2；xN1N1-1a1+N2N2-1a2+N3N3-1a3+N4N4-1a4 (5711)11+(3711)1(-1)+(3511)22+(357)2(-2)(mod 35711)385-231+660-420394 mod 11553.中国剩余定理练习题：（1）解同余方程：256x 123 mod 337（2）有一队士兵，若三人一组，则余1人；若五人一组，则缺2人；若十一人一组，则余3人。已知士兵人数不超过170人，问这队士兵的人数是多少？模为素数的二次剩余二次同余方程的一般形式是 ax2+bx+c0 mod m，a 0 mod m设m的分解式是 m=p11p22pkk，可证二次同余方程有解的充要条件是同余方程 ax2+bx+c0 mod pii，i=1,2,k有解。模为素数的二次剩余利用同余式的性质，同余方程 ax2+bx+c0 mod pii可化归为求解 ax2+bx+c0 mod p，p为素数为素数的同余方程。（1）如果p=2，根据剩余类的定义，直接验证x0或1 mod p。（2）如果gcd(a,p)=p，则p|a，同余方程成为一次方程。综上，只须考察p2且gcd(a,p)=1的情形。模为素数的二次剩余针对方程ax2+bx+c0 mod p，p2，p为素数，a,p互素。因gcd(a,p)=1，所以gcd(4a,p)=1，方程等价于4a2x2+4abx+4ac0 mod p，即(2ax+b)2b2-4ac mod p通过变量替换y2ax+b mod p和k=b2-4ac，将方程归结为同余方程y2k mod p。当k0 mod p时，同余方程只有解y0 mod p，只需考虑p与k互素（p为素数）的情形。模为素数的二次剩余定义：对于奇素数p（大于2的素数，如3,5,7,11等）和整数a，gcd(a,p)=1，若同余方程 x2a mod p有解，则称a是模p的二次剩余，记为aQR(P)，否则，称a是模p的二次非剩余，记为aQNR(P)。模为素数的二次剩余例如：设二次同余方程x2a mod p，其中p=7当a=1，x21 mod 7，求得x1 mod 7，x6 mod 7;当a=2，x22 mod 7，求得x3 mod 7，x4 mod 7;当a=3，x23 mod 7，无解;当a=4，x24 mod 7，求得x2 mod 7，x5 mod 7;当a=5，x25 mod 7，无解;当a=6，x26 mod 7，无解。根据定义：（1）a=1,2,4是模7的二次剩余，（2）a=3,5,6是模7的二次非剩余。模为素数的二次剩余进一步讨论：当a=8，x28 mod 7(1+7)mod 71 mod 7，解同a=1的情况；当a=9，x29 mod 7(2+7)mod 72 mod 7，解同a=2的情况；。显然，对于同余方程x2a mod p，若a1是模p的二次剩余（或二次非剩余），则a1+qp(qZ)是模p的二次剩余（或二次非剩余）。即所有与a1模p同余的数都是模p的二次剩余（二次非剩余）。由此可知，模p的一个二次剩余（或二次非剩余）实质上就是模p的一个简化剩余类简化剩余类。模为素数的二次剩余例如：设二次同余方程x2a mod p，其中p=7x21 mod 7，有解x1 mod 7和x6 mod 7;x22 mod 7，有解x3 mod 7和x4 mod 7;x23 mod 7，无解;x24 mod 7，有解x2 mod 7和x5 mod 7;x25 mod 7，无解;x26 mod 7，无解。模7的二次剩余为1,2,4，则1+7q,2+7q,4+7q（qZ）都是模7的二次剩余，也就是简化剩余类17,27,47都是模7的二次剩余。模为素数的二次剩余一个结论：模p的二次剩余的全体和二次非剩余的全体数量相同，都是(p-1)/2=3个。模为素数的二次剩余说明：对于二次同余方程x2a mod p如果有解xb mod p，则另一个解x-b mod p是不同的解。假设是同一个解，即b-b mod p，即2b0 mod p则上式只有在b=0或p|b时成立，推得p|a，这与定义中的前提假设矛盾，故b-b mod p。因此xb mod p是方程的两个不同的解。于是，若方程有解，则必有两个解。模为素数的二次剩余下面给出a是否为模p的二次剩余或二次非剩余的判别条件。定理（Euler判别法）对于奇素数p和整数a，gcd(a,p)=1（1）a是模p的二次剩余的充要条件为且若a是模p的二次剩余，则方程x2a mod p有两个解；（2）a是模p的二次非剩余的充要条件为papmod121papmod121模为素数的二次剩余定理（Euler判别法）证明：先证对于任何与p互素的a，a(p-1)/21 mod p与a(p-1)/2-1 mod p有且仅有一式成立。由于a与p互素，因此由费尔马小定理可知a(p-1)1 mod p故，有(a(p-1)/2+1)(a(p-1)/2-1)0 mod p，即P|(a(p-1)/2+1)(a(p-1)/2-1)。假设P|(a(p-1)/2+1)且P|(a(p-1)/2-1)，则a(p-1)/21 mod p与a(p-1)/2-1 mod p同时成立，即，-11 mod p，这与p是奇素数(p2)矛盾，因此，a(p-1)/21 mod p与a(p-1)/2-1 mod p有且仅有一式成立。模为素数的二次剩余定理（Euler判别法）证明：下面证明a是模p的二次剩余的充要条件是同余式a(p-1)/21 mod p成立。先证必要性，若a是模p的二次剩余，则必定存在x0使得 x02a mod p，p为奇素数，则2|p-1，有x0(p-1)a(p-1)/2 mod p（相乘(p-1)/2次），由于a与p互素，所以x0也与p互素，由欧拉定理可知 x0(p-1)1 mod p所以 a(p-1)/21 mod p必要性得证。模为素数的二次剩余定理（Euler判别法）证明：再证充分性，设 a(p-1)/21 mod p 成立，因p是素数，那么a与p必定互素。构造一次同余方程kxa mod p，kZp*=1,2,p-1当k取Zp*中的某个t时，设方程的解为xxi mod p，xiZp*，此时方程的解唯一(若有两个解，则kxikxj mod p，k与p互素，有xi=xj)。如果a不是模p的二次剩余，则kxi。可将Zp*按k,xi作为一对两两分完，因此有 (p-1)!a(p-1)/2 mod p由Wilson定理：(p-1)!-1 mod p，所以有a(p-1)/2-1 mod p，这与前提条件矛盾。充分性得证。模为素数的二次剩余练习题：对Wilson定理进行证明。若p是素数，则(p-1)!-1 mod p。由a是二次剩余的充要条件直接推出a为二次非剩余的充要条件为：a(p-1)/2 1 mod p，即 a(p-1)/2-1 mod p。得证模为素数的二次剩余例 判断：（1）3是否是17的二次剩余（2）7是否是29的二次剩余解：（1）由3(17-1)/2 mod 17(34 mod 17)(34 mod 17)mod 17 (1313)mod 17=16 -1=-117+16，-1 mod 17=16所以：3(17-1)/2-1 mod 17,3不是模17的二次剩余，而是模17的二次非剩余。（2）7(29-1)/21 mod 29，则7是29的二次剩余。模为素数的二次剩余Euler判别法的两个推论：（1）-1是模p的二次剩余，当且仅当p1 mod 4，p为奇素数。（2）设p是奇素数，a1、a2均与p互素，则若a1、a2均为模p的二次剩余，则a1a2也是模p的二次剩余；若a1、a2均为模p的二次非剩余，则a1a2也是模p的二次剩余；若a1为模p的二次剩余，a2为模p的二次非剩余，则a1a2是模p的二次非剩余。离散对数设有同余方程ax1 mod m，考虑其解的情况。由欧拉定理，若a,m互素，有a(m)1 mod m，x=(m)是方程的解。例：若a=5，m=11，求x使5x1 mod 11.由欧拉定理：5(11)1 mod 11，x=(11)=10是方程的解。515 mod 11，523 mod 11，534 mod 11，549 mod 11，551 mod 11，565 mod 11，573 mod 11，584 mod 11，599 mod 11，5101 mod 11，从上可以看出，至少x=5，x=10，x=5n（n=1,2,）是方程的解。（后面将说明是否存在不是5的倍数的解）本原根本原根定义：称使方程ax1 mod m（gcd(a,m)=1,m1）成立的最小正整数解n为a模m的阶。本原根回到上例中：求x使5x1 mod 11.515 mod 11，523 mod 11，534 mod 11，549 mod 11，551 mod 11，所以5模11的阶为5。565 mod 11，573 mod 11，584 mod 11，599 mod 11，5101 mod 11（x=(m)），定义：如果a模m的阶x=(m)，则称a为m的本原根或者本原元。例中：(11)=10，所以5不是11的本原根。本原根例：若a=7，n=11，求x使7x1 mod 11.717 mod 11，725 mod 11，732 mod 11，743 mod 11，7510 mod 11，764 mod 11，776 mod 11，789 mod 11，798 mod 11，7101 mod 11，例中：7模11的阶为10，而(11)=10，所以7是11的本原根。只有以下形式的整数才有本原根：2,4,p,2p，其中为整数，p为奇素数。离散对数进一步说明“阶”的意义：例 a=7,n=19，则717 mod 19，7211 mod 19,731 mod 19,即7模19的阶为3。则有73k+j=73k7j7j mod 19，故747 mod 19，7572 mod 19，7673 mod 19，即从74 mod 19开始，所求的模运算出现循环，循环周期为3，也就是7模19的阶。离散对数1.a模m的阶的性质性质1：gcd(a,m)=1,同余方程为ax1 mod m。设a模m的阶为n，则n|(m)。证明：根据欧拉定理，(m)是方程的一个解。设阶n不能整除(m)，则可令(m)=kn+r，0rn.那么，a(m)akn+r(an)karar mod m，所以ar1 mod m，得知r也是方程的解。n为a模m的阶，根据阶的定义，n是使同余方程成立的最小正整数，这与rn矛盾。得证。实际上实际上，满足同余方程ax1 mod m的任意x都是阶n的倍数。离散对数1.a模m的阶的性质性质2：如果a是m的本原根，则a mod m,a2 mod m,a(m)mod m互不相同，且均与m互素。证明：因a是m的本原根，所以(m)是a模m的阶。设存在1ij(m)，使得：aiaj mod m。另设j=i+t，因1i,j(m)，故1t(m)。因a与m互素，所以aj,ai,at均与m互素，等式两边同乘at得aiatajat mod m，即ai+tajajat mod m整理得1at mod m。因1t(m)，这和(m)是a模m的阶矛盾。所以a mod m,a(m)mod m互不相同。例，考察同余方程为5x1 mod 9计算：515 mod 9，527 mod 9，538 mod 9，544 mod 9，552 mod 9，561 mod 9，所以5模9的阶n=6，而(9)=6，所以5是9的本原根。因此：5 mod 9,52 mod 9,53 mod 9,54 mod 9,55 mod 9,56 mod 9=1,2,4,5,7,8可以看到5 mod 9,52 mod 9,53 mod 9,54 mod 9,55 mod 9,56 mod 9互不相同，且都与9互素。离散对数特别地，如果m为素数，a是m的本原根，则a mod m,a2 mod m,a3 mod m,am-1 mod m(m-1)个数互不相同，且均与m互素。因此方程y=ax mod m（m为素数，a是m的本原根），x1,2,m-1，y1,2,m-1，建立集合1,2,m-1到集合1,2,m-1之间的一一映射一一映射。离散对数例：设a=2，m=1121 mod 11=2,22 mod 11=4,23 mod 11=8,24 mod 11=5,25 mod 11=10,26 mod 11=9,27 mod 11=7,28 mod 11=3,29 mod 11=6,210 mod 11=1.显然，在模m=11下，集合2 mod 11,22 mod 11,23 mod 11,210 mod 11与集合1,2,3,10相等。且集合中的元素互不相同，且与11互素。因此，11为素数，2是11的本原根，当xZ11*=1,2,10，模指数函数y2x mod 11是Z11*到Z11*的一一映射。离散对数一一映射yax mod m建立在本原根的基础上，下面说明本原根的数量。例：考虑a=3,m=7，和a=5,m=7的情况，则313 mod 7,515 mod 7322 mod 7,524 mod 7336 mod 7,536 mod 7344 mod 7,542 mod 7355 mod 7,553 mod 7361 mod 7,561 mod 73模7的阶为6，5模7的阶也为6，而(7)=6，故7的本原根有两个。所以，整数整数m的本原根不唯一的本原根不唯一。离散对数2.离散对数的定义设m为素数，a是m的本原根，则在模m下 a mod m,a2 mod m,a3 mod m,am-1 mod m产生1到m-1之间的所有值，且每个值仅出现一次。因此：对任意x1,m-1，都存在唯一正整数y(0ym)，使得 yax mod m。这样，模m下a的指数幂运算为 yax mod m，1xm-1称x为模m下以a为底y的对数，记为：xlogay mod m（有的资料上表示为x=inda,p(y)）由于运算定义在模m的有限域上，所以称为离散对数运算离散对数运算。离散对数2.离散对数当a、m和x已知时，根据yax mod m利用快速指数算法可以比较容易地求出y，至少需要2logam次运算。如果已知a、m和y，根据xlogay mod m求x，目前已知的最好的算法的时间复杂度时间复杂度为：只要m足够大，求解离散对数问题相当困难，在时间上不可行。由于离散对数问题具有较好的单向性，离散对数问题在公钥密码学中有广泛应用。如美国数字签名标准算法DSA等都是建立在离散对数问题之上。323lnlnexpmmO离散对数3.离散对数的性质（1）loga10 mod m（2）logaa1 mod m（3）logaxy(logax mod m+logay mod m)mod(m)素性检测算法素性检测：判定一个给定的整数是否为素数费尔马小定理：若m是素数，a与m互素，则am-11 mod m。根据费尔马小定理，对于一个给定的整数n，随机选择整数a，计算an-1 mod n：（1）如果an-1 mod n不为1，则n肯定不是素数。（2）如果an-1 mod n为1，则n可能是素数。满足费尔马小定理是必要条件。素性检测算法例如：2341-1 mod 341=1，2和341互素，但是341（=1131）不是素数。341是满足2n-1 mod n1最小的合数n。210=1024=3413+1，210 mod 341 1 2340 mod 341=(210)34 mod 341=1还有其他的数满足费马小定理，但也不是素数的数，如Carmichael（卡米切尔）数。前3个Carmichael数是561,1105,1729。Carmichael数非常少，在1108范围内的整数中，只有255个Carmichael数。素性检测算法费尔马小定理是素数检测的必要条件，为了提高检测准确率，增加其他条件。引理：如果m是大于2的素数，则二次同余方程x21 mod m的解只有x1 mod m或x1 mod m和xm-1 mod m。引理的逆否的命题：如果方程x21 mod m存在x 1 mod m或存在x m-1 mod m的解，则m不是大于2的素数。(例，32 mod 8=1，所以8不是素数。)因此，验证一个数m不是素数，只要验证方程x21 mod m存在非1或m-1的解。素性检测算法下面对引理进行证明。引理：如果p是大于2的素数，则二次同余方程x21 mod p的解只有x1 mod p。证明：由x21 mod p得x2-10 mod p，所以(x+1)(x-1)0 mod p。有p|(x+1)，或p|(x-1)，或者p|(x+1)且p|(x-1)。如果p|(x+1)且p|(x-1)同时成立，则存在整数s和t，满足：x+1=sp，x-1=tp。两式相减得2=(s-t)p。因p是大于2的素数，上式不成立。因此p|(x+1)或p|(x-1)，故x-1 mod p或x1 mod p。素性检测算法目前常用的素性检测算法是Miller-Rabin(米勒-拉宾)素性检测算法。引理的逆否命题引理的逆否命题和费尔马小定理费尔马小定理是Miller-Rabin素性检测算法的依据。下面给出Miller-Rabin(米勒-拉宾)素性检测算法的描述。素性检测算法Miller-Rabin(米勒-拉宾)算法描述如下：Miller-Rabin(a,n);/a,n为输入，n是待检测的数，a是随机选择的小于n的整数represent(n-1)as binary bkbk-1b0;/n-1表示成二进制数d1;for i=k downto 0 doxd;d(dd)mod n;if (d=1)and(x1)and(xn-1)then return TRUE;/若返回TRUE，则方程x21 mod n存在非1（模n）的解 if bi=1 then d(da)mod n;if d1 then return TRUE;/d=an-1 mod n,由费尔马小定理,若n为素数,则d=1Return FALSE返回TURE，则n不是素数；返回FALSE，则n有可能是素数。素性检测算法算法说明：（1）算法的两个输入中，n是待检测的数，a是小于n的整数。如果算法的返回值为TURE，则n不是素数；如果返回FALSE，则n有可能是素数。（2）在for循环结束时，d=an-1 mod n，由费尔马定理可知，如果n为素数，则d为1；反之，若d1，则n不是素数，返回TURE。（3）由于n-1-1 mod n，结合算法中变量x和d的联系，可知for循环体内的if条件(d=1)and(x1)and(xn-1)意味着方程x21 mod n存在非1（模n）的解，知n不是素数，返回TURE。素性检测算法算法的意义：算法只能确定一个数不是素数，但是不能确定一个数是素数。假设我们选择了s个不同的a对一个数n进行验证，如果算法每次都返回FALSE，则以(1-2-s)的概率确信n是素数，也就是误判的概率是2-s。当s足够大时，以极大的概率相信n是素数，通常要求s80。