数论基础课件

1、数论简介,带余除法,带余除法定理 设a 和b 为整数，b 0，则存在惟一的整数q 和r 使得a = qb + r，0 r 0, 整除有如下性质 1. 若c | b，b | a, 则c | a； 2. 若b | a，则bc | ac； 3. 若c | a，c | b，则对任意整数m，n 有 c |ma + nb。,模运算,设n是一正整数,a是整数,若 a=qn+r, 0rd 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(55,22)=gcd(22,11)=

2、gcd(11,0)=11,扩展的欧几里德算法,求乘法逆元 若gcd(a,b)=1, b在模a下有乘法逆元(设bd),扩展的欧几里德算法,1.（X1 X2 X3)(1,0,f);(Y1Y2 Y3)(0,1,d); 2. If Y3=0, then return X3=gcd(f,d);no inverse; 3. If Y3=1, then return X3=gcd(f,d);Y2=d-1 mod f; 4. Q=X3 div Y3; 5. (T1 T2 T3)(X1-QY1,X2-QY2,X3-QY3); 6. (X1 X2 X3)(Y1Y2 Y3); 7. (Y1Y2 Y3)(T1 T2

3、T3); 8.Goto 2,例1,求gcd(12345,11111),例1解答,ri qi 12345 11111 1 1234 9 5 246 4 1 1 4,例2,求,例2解答,ri qi ti 60 0 19 3 1 3 6 -3 1 3 19,中国剩余定理,定理(中国剩余定理)： 设m1,m2,mk是两两互素的正整数， 则一次同余方程组 对模M有唯一解,中国剩余定理,例：x1 mod 2, x2 mod 3, x3 mod 5 x5 mod 7,求x 解：M2357210，M1=105, M2=70, M3=42, M4=30, (Mi=M/mi),可以求得e1=1, e2=1, e3

4、=3, e4=4,所以x=10511701242333045 mod 210173,离散对数,求模下的整数幂 根据欧拉定理，若gcd(a,n)=1,则af(n) 1 mod n。考虑一般am 1 mod n, 如果a,n互素，至少有一个整数m满足这一方程。称满足这一方程的最小正整数m为模n下a的阶。 例：a=7,n=19. 71 7 mod 19, 72 11 mod 19, 73 1 mod 19,所以7模19的阶为3。从幂次为4开始出现循环，循环周期与元素的阶相同,离散对数,定理：设a的阶为m，则ak1mod n的充分必要条件是k是m的倍数。 推论：a的阶整除j(n)。 本原根：a的阶m等

5、于j(n)，a为n的本原根。 如果a是n的本原根，a1,a2,.,a j(n)在模n下互不相同且与n互素。 本原根不唯一。 并非所有元素都有本原根，仅有以下形式的整数才有本原根：2，4，pa,2pa, p是奇素数,离散对数,指标 y=ax(a0,a1)的逆函数称为以a为底的对数，记为x=logay 设p为素数，a是p的本原根，则a0,a1,.,a p-1产生1到p-1中所有值，且每个值只出现一次。对任一b1,p-1，都存在唯一的i(1i p)，使bai mod p。i称为模p下以a为底b的指标，记为i=inda,p(b),离散对数,指标的性质 inda,p(1)=0 inda,p(a)=1 i

6、nda,p(xy)=inda,p(x)+ inda,p(y) mod j(p) inda,p(yr)=rinda,p(y) mod j(p) 后两个性质基于下列结论 若azaq mod p ,a和p互素，则z q mod j (p),离散对数,设p是素数，a是p的本原根。对b1,p-1,有唯一的i 1,p-1,使bai mod p。称i为模p下以a为底b的离散对数，记为 i logab (mod p) 已知a,p,i,求b比较容易，以及a,b,p,求i非常困难,素性检验,引理：如果p为大于2的素数，则方程x21 mod p的解只有x1或x-1 证明: x21 mod p x2 -1 0 mod

7、 p (x+1)(x-1)0 mod p 所以,p|(x+1)或p|(x-1) 或p|(x+1)且p|(x-1)存在k,j，x+1=kp, x- 1=jp2=(k-j)p, 这是不可能的。 引理的逆命题：若方程x21 mod p有唯一解x不为+1或-1，p不是素数,素性检验,Miller-Rabin素性概率检测法 n为待检测数，a为小于n的整数，将n-1表示为二进制形式bkbk-1b0,d赋初值为1，算法核心如下 若返回False,n不是素数,若返回True,有可能是素数。,素性检验,for i=k downto 0 do xd; d(dd) mod n; if d=1 and (x1)and(xn-1) then return False if bi=1 the d(da) mod n if d 1 then return False; return True,素性检验,For循环结束,有dan-1 mod n.由费尔玛定理,若n为素数,d为1.所以d1，则d不是