《保障与安全数论》由会员分享，可在线阅读，更多相关《保障与安全数论（30页珍藏版）》请在金锄头文库上搜索。
1、数论导引数论导引1 1 素数和数的互素素数和数的互素 除数除数(因子因子)的概念：的概念：设设z为所有全体整数构成的集合，若为所有全体整数构成的集合，若 b0且且 使得使得a=mb , 此时称此时称b整除整除a.记为记为b a,还称还称b为为a的除数的除数(因子因子). 注注:若若a=mb+r且且0r1被称为素数是指被称为素数是指p的因子仅有的因子仅有1,-1,p,-p。定义定义：若ax mod n =1，则称a与x对于模n互为逆元。用Euclid算法求乘法逆元 若a和n互素，则a在模n下有逆元。算术基本定理：算术基本定理： 任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt
2、，这里P1P2P3Pt是素数，其中i0最大公约数：最大公约数： 若a,b,cz，如果ca，cb，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足d是a和b的公约数。对a和b的任何一个公约数c有cd。注注：1*. 等价的定义形式是： gcd（a,b）maxk ka，kb 2*若gcd（a,b）=1，称a与b是互素的。2模模 算术算术 全体整数Z构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合z为整数环整数环。整数环z对除法运算不封闭。带余除法：带余除法： az0，可找出两个唯一确定的整数q和r,使a=qm+r, 0=r1）分成一些两两不交
3、的等价类。 3*.整数模m同余类共有m个，他们分别为mk+0,mk+1, mk+2,mk+(m-1); kz，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称0,1,2,m-1为标准完全剩余系。Z模12的标准剩余系为：0,1,2,3,4,5,6,7,8,9,10,11自反性对称性传递性 4*. 对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘 （可交换的、可结合的、可分配的）而且，简化运算每个中间结果的模n运算，其作用与先进行全部运算，然后再简化模n运算是一样的。(1)a(mod m)b(mod m) mod m =(ab)(mod m)(2)a(mod
4、 m) b(mod m) mod m =a b(mod m)(3) )(a b)(mod m)+(a c)(mod m) mod m =(a (b+c)(mod m)例1 152 mod 12 =(3*3) mod 12=9例2 通过同余式演算证明5601是56的倍数，2231是47的倍数。 解： 注意53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂， 即有56560-1。注意26=64-30(mod47),于是223=(26)325=(26 26)26 25 900 (-30) (32) mod(47) (7)(-30) (32) (mod47
5、) (-30) (224) (mod47) (-30) (36) (mod47) (-1080) (mod47) 1(mod47) 于是有 47223-1求117 (mod13)， 112 =121 4 (mod13)， 114 42 3 (mod13)，117 114 3 2 (mod13)定理定理：(消去率)对于abac（mod m）来说，若(a,m)1则bc(mod m)5*.一次同余方程axb(mod m)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b 定理定理：如记(a,m)=d,则同余方程axb(mod m)有解的充分必要条件是db。当这个
6、条件满足时，恰有d个模m同余类中的整数是上述方程的解。 证明：略。（从ax+my=b入手）6*.整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m)zm=0,1,m-1 在4中已说明zm对剩余类的加法，乘法是封闭的，可列出它们的加乘表。我们称zm为剩余类环（或同余类环）7*.在整数环z中是没有零因子的，即两个非零整数的乘积一定不等于0，但是剩余环则不然。 例z12中：3*4=12=0 说明，zm中的元素可分为两类，一类是零因子中的元素可分为两类，一类是零因子，即若zm,0存在zm且0，有*=0，称，都为zm中的零因子。另一类是可逆元另一类是可逆元，即若zm，存在zm使*=1，此时,互为
7、各自的逆元，记-1=；-1=定理：定理：剩余类环zm中元素=a为zm的可逆元(a,m)=1要证明这个定理，只需证明下列引理：引理引理：任意两个整数任意两个整数a和和b都有一个最大公约数，这样一都有一个最大公约数，这样一个最大公约数个最大公约数d可以表示成可以表示成a,b二数关于整系数的线性二数关于整系数的线性组合，即有组合，即有s,tz，使，使dsatb。证明（自己看)不妨设b0，用辗转相除法，先用b去除a，得 a=q1b+r1,0=r1b;(1)如果r1=0，停止，否则再用r1去除b，得 b=q2r1+r2,0=r2r1;(2)如果r2=0，停止，否则再用r2去除r1，得 r1=q3r2+r
8、3;0=r3r2;(3)等等，这样一直进行下去，可得一系列关系式：rk-3=qk-1rk-2+rk-1,0=rk-1rk-2; (k-1)rk-2=qkrk-1+rk,0=rk r2 r3 r4 rk=0是严格递降的一串非负整数，故最后总会出现余数为0的情形：rk-1=qk+1rk(k+1)所以，进行有限步必停止，此时d=rk=(a,b)定成立，这是因为1*. 可见rk为a和b的公约数，只要按倒序分析自然有此结论。2*. a和b的任何一个公约数c都是rk的约数，只要按正序分析，自然可知。为证定理的后一部分，将式(1)做移项有 r1=s1a+t1b（其中s1=1,t1= -q1）再将式(2)右端
9、通过移项变为r2=s2a+t2b这样一直下去，最后得d=rk=s*a+t*b,s,tz欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。Euclid算法是基于下面一个基本结论： 对任意非负整数a和正整数b，有gcd(a, b)=gcd(b,a mod b)。即a，b的公因子集合与b，a mod b的公因子集合相等，两个集合的最大值也相等。例如： gcd(55, 22)=gcd(22, 55 mod 22) = gcd(22,11) =
10、gcd(11, 0)=11。在求两个数的最大公因子时，可重复使用以上结论。例如： gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=gcd(1,0)=1。欧几里得算法例子：求gcd(180，252)，并将他表示为180和252这两个数的一个带整系数的线性组合。解：252=1*180+72(1)180=2*72+36 (2)72=2*36(3) 得gcd(180,252)=36，同时有72=252-1*180 (1 ) 由(2)得36=180-2*72 (2 )将(1)代入(2 )，即得 36=180-2*(252-180) =3*180
11、-2*252求gcd(1970,1066)=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=16+4,gcd(6, 4)6=14+2,gcd(4, 2) 4=22+0,gcd(2, 0)因此gcd(1970, 1066)=2。
12、计算逆元的方法有1、用欧拉推广公式解：x=(ba (n)-1)modn2、用欧几里德算法解： x=(b(a -1modn)modn 通常欧几里德算法在计算逆元方面较欧拉推广更快，特别是500位范围内的数。Euclid算法就是用这种方法，因gcd(a, b)=gcd(|a|, |b|)，因此可假定算法的输入是两个正整数，设为d，f，并设f d。Euclid（f, d）1. Xf; Yd；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在mod a下有乘
13、法逆元（不妨设ba），即存在一x (x0，用辗转相除法，先用b去除a，得 r0 =q1 r1 +r2, 0r2r1 r1 =q2 r2 +r3, 0r3r2;等等，这样一直进行下去，可得一系列关系式：rm-2=qm-1rm-1+rm, 0rmd） 1. (X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d);2. if Y3=0 then return X3=gcd(f, d)；no inverse;3. if Y3=1 then return Y3=gcd(f, d)；Y2=d-1 mod f;4. Q=X3Y3 ；5. (T1,T2,T3)(X1-QY1,X2-QY2,X3
14、-QY3);6. (X1,X2,X3)(Y1,Y2,Y3);7. (Y1,Y2,Y3)(T1,T2,T3);8. goto 2。算法中的变量有以下关系：fT1+dT2=T3;fX1+dX2=X3;fY1+dY2=Y3在算法EUCLID (f, d)中，X等于前一轮循环中的Y，Y等于前一轮循环中的X mod Y。而在算法Extended Euclid(f, d)中，X3等于前一轮循环中的Y3，Y3等于前一轮循环中的X3-QY3，由于Q是Y3除X3的商，因此Y3是前一轮循环中的Y3除X3的余数，即X3 mod Y3，可见Extended Euclid(f, d)中的X3、Y3与Euclid(f,
15、d)中的X、Y作用相同，因此可正确产生gcd(f, d)。如果gcd(f, d)=1，则在最后一轮循环中Y3=0，X3=1，因此在前一轮循环中Y3=1。由Y3=1可得: fY1+dY2=Y3，fY1+dY2=1，dY2=1+(-Y1)f，dY21 mod f，所以Y2d-1 mod f。例 用扩展Euclidean算法计算28-1mod 75解：75=2*28+19 （1） 28= 1*19+9 （2） 19=2*9+1 （3）逆推19=75-2*28 （4） 9=28-1*19 （5） 1=19-2*9 （6）把（4）、（5）代入（6）得1=3*75-8*28因而28-1mod 75=-8
16、mod 75=67作业：编程计算17-1mod101， 357-1mod 1234。17-1mod101 6, 357-1mod 1234 Gcd(550,1759)=1,550关于模1759的乘法逆元是355，即550*350 1mod17593 Format定理和定理和Euler定理定理 Format定定理理：如果p是素数并且a是正整数,pa(a不能被p整除，即a不是p的倍数)，那么，ap-11(mod p) 或者：若p是素数，则ap mod p=a例：若 46 mod 7=4096 mod 7=1 则则 47 mod 7=16384 mod 7=4注：易见对gcd（a，p）1 有apa(
17、modp) Euler 函数 欧拉函数(n) (Euler函数(n)：当n1 时，(1)1；当n1时，(n)等于比n小而与n互素的正整数的个数。例1 (3)= (4) = (6) =2，(5)=4，(7) =6 例2 以n24为例，比24小而与24 互素的正整数为：1，5，7，11，13，17，19，23因此，我们有(24)8。 易见，若p为素数，则(p)p1。 n12， (12)？注：1*.若p，q都为素数且pq，此时有(pq)(p)(q)=（p1）（q1）证明（自学）：考虑zpq剩余类的集合是 0，1，2，（pq-1） 集合中与pq不互素的元素子集为 p,2p,(q-1)p和子集q,2q,
18、(p-1)q以及0，于是若设npq，有(n)=pq-(q-1)+(p-1)+1 =(p-1)(q-1)=(p)(q)例：(21)=(3*7)=(3)(7)=2*6=12.2*.设n= p1e1p2e2prer，其中p1,p2,pr为互异素数， 则(n)= p1e1-1p2e2-1prer-1(p1-1)(p2-2)(pr-1) =n(1-1/p1) (1-1/p2) (1-1/p3) (1-1/pr)例3：n=21=3*7，有两个素数3和7，这样， (21) =21(1-1/3)(1-1/7)=12即21中有12个整数与21是互素的: 1, 2, 4, 5，8, 10， 11, 12， 13,
19、 16， 17, 19 n24=3*8=3*23， (24)=24(1-1/3)*(1-1/2)=8即24中有8个整数与24是互素的： 1，5，7，11，13，17，19，23欧拉定理（欧拉定理（Euler）：）： 若整数若整数a与整数与整数n互素，则互素，则a(n)1(mod n)推论推论：若a与n互素，则a与a (n)-1 互为逆元。互为逆元。例4 求5关于模7 的乘法逆元。解 由于7是素数， (7) =7-1=6，所以5关于模7的乘法逆元为 5 6-1 mod7=55mod7=3注：注：1*. np时，有ap-11(mod p)为Format定理！2*.易见a(n)+1a(mod n)3
20、*.若n=pq，p与q为相异素数，取0mn，若gcd(m,n)1，有m(n)+1m(mod n)， 也即m(p-1)(q-1)+1m(mod n).4*.由 (m(n)k1k(mod n) 知mk(n)1(modn)， 进一步mk(n)+1m(mod n) mk(p-1)(q-1)+1m(mod n)推广欧拉定理：推广欧拉定理： 若a b (mod r) ，则对于任意幂m， 有am bm (mod r) am (r) 1 (mod r) 若a b (mod r) ，则对于任意的整数c， 有ac bc (mod r) Xm (r)+1 X (mod r)4 原根(primitive root)E
21、uler定理表明,对两个互素的整数a,n,a(n) 1 mod n定义：定义：存在最小正整数m(n) (m|(n),使得am 1 mod n，若对某个a, m=(n),则称a是n的一个原根对于素数p,若a是p的一个原根,则: a,a2, ,ap-1是(模p)各不相同的,从而构成了p的非0剩余类,即与1,2,(p-1)关于模p等价. 5 离散对数离散对数若a是素数p的一个原根,则对任意整数b,br mod p,其中0rp-1因此，对任意整数b和素数p ，存在唯一的整数i, 使得:bai mod p 1i(p-1)称指数i为以a为底模p的b的离散对数，记作inda,p(b).容易知道: inda,p(xy)= inda,p(x)+inda,p(y) mod (p) inda,p(xr)= rinda,p(x) mod (p) inda,p(1)=0,因为 a0 mod p =1 mod p=1 inda,p(a)=1，因为 a1 mod p =a 5 离散对数离散对数离散对数的计算:ygx mod p已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的公钥算法的经典例子Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC
