第二章数学基础45p

第二章 数学基础,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的素数，则方程x21 mod p的解只有和x1和x-1 证明:x21 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=jp2=(k-j)p, 这是不可能的。 引理的逆命题：若方程x21 mod p有唯一解x不为+1或-1，p不是素数,素性检验,Miller-Rabin素性概率检测法 n为待检测数，a为小于n的整数，将n-1表示为二进制形式bkbk-1b0,d赋初值为1，算法核心如下for i=k downto 0 doxd;d(d×d) mod n;if d=1 and (x1)and(xn-1) then return Falseif bi=1 the d(d×a) mod nif d 1 then return False;return True 若返回False,n不是素数,若返回True,有可能是素数。,素性检测,For循环结束,有dan-1 mod n.由费尔玛定理,若n为素数,d为1.所以d1，则d不是素数 n-1-1 mod n,所以x 1和x n-1指x21 mod n 有非±1的根,n不是素数 该算法对s个不同的a，重复调用，如果每次都返回true，则n是素数的概率大于等于1-2-s,模运算,设n是一正整数,a是整数,若a=qn+r, 0r<n, 则a mod n=r 若(a mod n)=(b mod n),称为a,b模n同余，记为ab mod n 称与a模n同余的数的全体为a的同余类，记为a，a称为这个同余类的代表元素,模运算,同余的性质 若n|(a-b)，则ab mod n (a mod n) (b mod n),则ab mod n ab mod n，则ba mod n ab mod n， bc mod n，则ac 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 加法逆元：对wZn,有zZn，满足w+z=0 mod n, z为w的加法逆元，记为z=-w。 加法的可约律(a+b)(a+c) mod n, 则bc mod n对乘法不一定成立，因为乘法逆元不一定存在。,模运算,定理:设aZn,gcd(a,n)=1,则a在Zn有逆元证明思路： 用反证法证明a和Zn中任何两个不同的数相乘结果都不相同 从1得出a×Zn=Zn,因此存在xZn,使a×x=1 mod n 设p为素数，Zp中每一个非零元素都与p互素，因此有乘法逆元，有乘法可约律(a×b)=(a×c) mod n, b=c mod n,最大公约数欧几里德算法（euclidean algorithm),欧几里德算法的复杂度O(size(a)size(b) 扩展的欧几里德算法（extended euclidean algorithm)可以求出x,y 使得事实上，有(P134)扩展的欧几里德算法的复杂度是O(size(a)size(b) 整数分解,离散对数,求模下的整数幂 根据欧拉定理，若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等于j(n)，a为n的本原根。 如果a是n的本原根，a1,a2,.,a j(n)在模n下互不相同且与n互素。 本原根不唯一。 并非所有元素都有本原根，仅有以下形式的整数才有本原根：2，4，pa,2pa, 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非常困难,半群(semigroup)集合的二元运算整数集,有理数集,实数集,复数集关于数的普通加法和乘法是二元运算;剩余类Z/mZ的加法和乘法是二元运算;结合律集合有满足结合律的二元运算就是半群.整数集,有理数集,实数集,复数集关于数的普通加法和乘法构成半群;剩余类Z/mZ关于加法和乘法都构成半群.含有单位元(neutral element)的半群称为幺半群(monoid),整数集,有理数集,实数集,复数集关于数的普通加法和乘法构成幺半群;剩余类Z/mZ关于加法和乘法都构成幺半群.元素的可逆性(invertible),群(group)Galois与群每个元皆有逆元的幺半群是群交换群(Abel群),Abel群的运算可以称为加法,单位元称为零元整数集,有理数集,实数集,复数集关于数的普通加法构成Abel群;有理数集,实数集,复数集中的非零元组成的集合关于数的普通乘法构成Abel群;群的有限性群-阶(order)(G,.)有消去律(cancellation)群元的幂运算及其性质剩余类Z/mZ关于加法构成群关于乘法不是群,剩余类环环的定义:含幺环, 可换环整数集,有理数集,实数集,复数集关于数的普通加法和乘法构成含幺可换环;剩余类Z/mZ关于加法和乘法构成含幺可换环.环的单位元群(unit group of a ring),零因子整数环无零因子整环:无零因子的可换含幺环Z/mZ m是合数有零因子,m是素数无零因子域:每个非零元都可逆的整环,剩余类环的可除性Z/mZ,当m是素数时是域 .Z/mZ中加法和乘法及除法的复杂度:加法的复杂度是O(size(m),乘法和除法的复杂度是O(size2(m),其中除法可用扩展的欧几里德算法.,剩余类环Z/mZ的单位元群,子群及陪集群G的子集H称为G的子群，若H关于G的运算也构成群.:由g生成的子群循环群:G=加群Z有两个生成元1和-1;有限群G有 个生成元. 陪集(coset):H是G的子群,a是G的一个元,称为a关于H的陪集.Lagrange定理: H是G的子群,则H的阶整除G的阶.,群元的阶(order)g是群G的一元，称 为g的阶.g的阶记为g阶的性质:,Fermat小定理,2.3 剩余类环Z/mZ中的快速幂乘 计算ae mod m是现代密码学的一个核心部件. 平方-乘算法(square-and-multiply algorithm)思想:一个例子673mod 100,伪码平方-乘算法的复杂度是size(e)size2(m),2.4 中国剩余定理,如果已知某个数关于一些量量互素的数的同余类集，就可以重构这个数 定理(中国剩余定理)：设m1,m2,mk是两两互素的正整数， 则一次同余方程组对模M有唯一解,又称：孙子定理,中国“孙子算经”中“物不知其数”问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何 程大位著“算法统要”中解法：三人同行七十稀，五树梅花廿一枝，七子团圆正月半，除百零五便得知,中国剩余定理,中国剩余定理可以将一个很大的数x表示为一组较小的数(a1,ak) 例：x1 mod 2, x2 mod 3, x3 mod 5 x5 mod 7,求x 解：M2×3×5×7210，M1=105, M2=70, M3=42, M4=30, (Mi=M/mi),可以求得e1=1, e2=1, e3=3, e4=4,所以x=105×1×170×1×242×3×330×4×5 mod 210173,计算中国剩余定理得复杂度是size2(m) 利用中国剩余定理有时可以简化计算思想：Z/mZ （Z/m1Z, Z/mnZ)具有同构关系。,2.5 群元阶的计算结果1：结果2：n是正整数，gn=1，并且对于n的每一个素因子p，都有 ， 则g的阶是n。,2.6 有限域 环R上的多项式多项式的加法与乘法,环上多项式的加法需O(max(deg(f),deg(g)+1)次环加法；环上多项式的乘法需O(deg(f)+1)(deg(g)+1)次环加法与环乘法运算。 RX关于上述加法与乘法构成一个含单位元的交换环,域上的多项式FX不含零因子；f，gFX，deg(fg)=deg(f)+deg(g) 域上多项式的带余除法域上多项式的除法需O(deg(q)+1)(deg(g)+1)次域运算。,有限域的构造,2.7 Zp的结构1.Zp是阶为p-1的循环群 2.p-1=2q的Zp 的本原元的寻找(1)任取一元g(2)若g2与gq1modp,则g为本原元.,