第二章 数学基础 45p.pptVIP

第二章 数学基础 2.1 群,环,域介绍(group,ring,field) 带余除法 同余(congruence) 剩余类及其性质 计算复杂度 a，b是整数 加法的复杂度 O(max(size(a),size(b))) 乘法的复杂度 O(size(a)size(b) ) 带余除法的复杂度O(size(b)size(q))(或O(size(a)size(b) )). 多项式时间算法 素性检验 引理：如果p为大于2的素数，则方程x2≡1 mod p的解只有和x≡1和x≡-1 证明: x2≡1 mod p ? x2 -1 ≡0 mod 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=jp?2=(k-j)p, 这是不可能的。 引理的逆命题：若方程x2≡1 mod p有唯一解x不为+1或-1，p不是素数 素性检验 Miller-Rabin素性概率检测法 n为待检测数，a为小于n的整数，将n-1表示为二进制形式bkbk-1…b0,d赋初值为1，算法核心如下 for i=k downto 0 do {x?d; d?(d×d) mod n; if d=1 and (x≠1)and(x≠n-1) then return False if bi=1 the d?(d×a) mod n } if d ≠1 then return False; return True 若返回False,n不是素数,若返回True,有可能是素数。 素性检测 For循环结束,有d≡an-1 mod n.由费尔玛定理,若n为素数,d为1.所以d≠1，则d不是素数 n-1≡-1 mod n,所以x ≠1和x ≠n-1指x2≡1 mod n 有非±1的根,n不是素数 该算法对s个不同的a，重复调用，如果每次都返回true，则n是素数的概率大于等于1-2-s 模运算 设n是一正整数,a是整数,若 a=qn+r, 0≤rn, 则a mod n=r 若(a mod n)=(b mod n),称为a,b模n同余，记为a≡b mod n 称与a模n同余的数的全体为a的同余类，记为[a]，a称为这个同余类的代表元素 模运算 同余的性质 若n|(a-b)，则a≡b mod n (a mod n) ≡(b mod n),则a≡b mod n a≡b mod n，则b≡a mod n a≡b mod n， b≡c mod n，则a≡c mod n 求余运算a mod n将a映射到集合{0,1,…,n-1},求余运算称为模运算 模运算 模运算的性质 [(a mod n)+(b mod n)] mod n=(a+b) mod n [(a mod n)-(b mod n)] mod n=(a-b) mod n [(a mod n)×(b mod n)] mod n=(a×b) mod n 模运算 例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法 模运算 若x+y=0 mod n, y为x的加法逆元。每一元素都有加法逆元 若对x，有xy=1 mod n，称y为x的乘法逆元。在上例中，并非所有x都有乘法逆元 定义Zn={0,1,..,n-1}为模n的同余类集合。 模运算 Zn上模运算的性质 交换律 （x+w) mod n=(w+x) mod n (x×w) mod n=(w×x) mod n 结合律 [(x+w)+y] mod n=[x+(w+y)] mod n [(x×w) ×y] mod n=[x×(w×y)] mod n 分配律 [w×(x+y)] mod n=[w×x+w×y)] mod n 模运算 单位元 (0+w) mod n=w mod n (1×w) mod n=w mod n 加法逆元：对w∈Zn,有z∈Zn，满足w+z=0 mod n, z为w的加法逆元，记为z=-w。 加法的可约律 (a+b)≡(a+c) mod n, 则b≡c mod n 对乘法不一定成立，因为乘法逆元不一定存在。 模运算 定理:设a∈Zn,gcd(a,n)=1,则a在Zn有逆元 证明思路： 用反证法证明a和Zn中任何两个不同的数相乘结果都不相同 从1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1 mod n 设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律 (a×b)=(a×c) mod