第4章-数学理论基础课件.ppt
《第4章-数学理论基础课件.ppt》由会员分享,可在线阅读,更多相关《第4章-数学理论基础课件.ppt(137页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第4章数学理论基础 第4章数学理论基础 4.1素数素数 4.2模运算及模运算及Euler定理定理 4.3群、群、域及环域及环 4.4多项式环、多项式环、域及群域及群 4.5线性空间及子空间线性空间及子空间 第4章数学理论基础 4.14.1素数素数4.1.14.1.1基本概念基本概念1.1.素数定素数定义义正整数分为素数、合数与1。一个除了能够被1和它本身整除之外,不能被其他任何整数整除的整数,称为素数,也称之为质数。比如2、3、5、7、13、4999都是素数。一般素数用p表示。一个整数除了能够被1和它本身整除之外,还能够被其他整数整除,那么该整数称之为合数。第4章数学理论基础 如果数a能够被b
2、整除,称b是a的一个因子,或称a有一个因子b,记作 ba(41)如果b是素数,称a有素因子b。设整数n2,有整数a1,a2,an和d,并且有 da1,da2,dan(42)那么称d为a1,a2,an的公因子,公因子中最大的一个称之为最大公因子,通常记a、b的最大公因子为 gcd(a,b)(43)第4章数学理论基础 例如gcd(36,24)=12,gcd(1008,1260,882,1134)=126。设整数n2,有整数a1,a2,an和m,并且有 a1m,a2m,anm(44)那么称m为a1,a2,an公倍数,公倍数中最小的一个称之为最小公倍数。显然,公倍数有无穷多个。记a,b的最小公倍数为
3、lcm(a,b)(45)例如lcm(12,18)=36,lcm(198,240,360)=7920。第4章数学理论基础 那么,可以容易地得到结果:如果两个整数a1,b1,有gcd(a,b)=1,就称为a、b互素。第4章数学理论基础 2.2.特殊素数特殊素数素数中有一些特殊的种类,因具有独特的结构易于攻击者分析,一般在密码算法中应该避免使用。1)孪生素数孪生素数指差值为2的两个素数。因为除2之外,任何素数都不为偶数,当然其差必须大于等于2。例如:3和5,5和7,11和13,29和31,71和73,101和103等。第4章数学理论基础 2)梅森素数把形如Mp=2p-1的素数称为梅森(MMersen
4、ne)素数。例如当p=2,3,5,7,13,17,19,31,61,89,107,127等时,Mp就是梅森素数。梅森素数的获取在计算机出现之前是非常困难的,自计算机出现之后情况有所改观。1999年,美国一个青年在网络上利用计算机得到了第38个梅森素数,这也是当时发现的最大的一个素数,它是M6972593=26972593-1,随后,又有人得到了第39个梅森素数,即M13466917。第4章数学理论基础 3)强素数 所谓强素数,是指两个素数p和q,它们满足以下特性:(1)gcd(p-1),(q-1)应该较小;(2)(p-1)有大的素因子p,(q-1)也有大的素因子q;(3)(p1)和(q1)都有
5、大的素因子;(4)(p+1)和(q+1)都应有大的素因子;(5)(p1)2,(q1)2都应该是素数。做这样的规定,是因为对于当n=pq时,要分解n使用某些特殊的因子分解方式是无效的。当然,对于目前较新的因子分解成果,有无强素数条件限定对其分解效率改变不大。第4章数学理论基础 4.1.2 素数的分布素数的分布 素数的分布极不均匀,素数越大,分布越稀疏。假设正整数中只有k是个素数,设为p1,p2,pk。令np1p2pk+1,则n1。如果n是素数,则显然与p1,p2,pk都不相同,这与只有k个素数的假设相矛盾。如果n不是素数,则一定有一个素因子,i1,2,否则由于pp1p2pk以及pn,所以p1,这
6、与p是素数相矛盾。故p与p1,p2,pk都不相同,这与只有k个素数的假设相矛盾。因此,素数有无穷多个。第4章数学理论基础 设x0,(x)为不大于x的素数的个数,则(46)根据式(46),当x充分大时,有(47)第4章数学理论基础 第4章数学理论基础 4.2模运算及模运算及Euler定理定理 4.2.1基本模运算基本模运算如果a是整数,n是正整数,则定义a除以n所得的余数为a模n。记作amodn(48)设a、b、m都是整数,如果m|(a-b),则称a和b模m同余,记作ab(modm)(49)同余在数论中是一个最基本的概念,可使用模运算来定义。例如:152(mod13),734(mod23),21
7、-9(mod10)。第4章数学理论基础 1模运算符的性质模运算符的性质(1)(a mod n)=(b mod n)等价于ab(mod n);(2)如果n|(a-b),那么ab(mod n);(3)ab(mod n)等价于ba(mod n);(4)ab(mod n)和bc(mod n)等价于ac(mod n)。模运算符的性质可以根据模定义直接得到,这里只证明第(2)条。如果n|(a-b),那么存在某个k使得(a-b)=kn,可知a=b+kn。因此,(a mod n)=(b+kn除以n的余数)=(b除以n的余数)=(b mod n)。由模定义知,(amodn)运算将所有的整数映射到0,1,n-1组
8、成的集合。于是出现了能否限制在这个集合上进行算术运算的问题。答案是肯定的,而这种技术被称为模算术。第4章数学理论基础 2.2.模算术的性质模算术的性质(1)(amodn)+(bmodn)modn=(a+b)modn;(2)(amodn)-(bmodn)modn=(a-b)modn;(3)(amodn)(bmodn)modn=(ab)modn。以上性质的证明非常简单,从其定义就可以直接得到。这里只证明第(1)条。第4章数学理论基础 定义(a mod n)=ra,(b mod n)=rb,于是存在整数j和k,使得a=ra+jn,b=rb+kn。那么有:(a+b)mod n=(ra+jn+rb+kn
9、)mod n =(ra+rb+(k+j)n)mod n =(ra+rb)mod n =(a mod n)+(b mod n)mod n 定义比n小的非负整数集合为Zn,则这个集合称为剩余集或模n的剩余类,即 Zn=0,1,(n-1)或 Zn=a Z1an-1 式中:Z表示全体整数。第4章数学理论基础 设模n的剩余类中与n互素的集合为Z*n,则(411)特别是当n为素数时,有Z*n=Zn。第4章数学理论基础 3.3.模运算的性质模运算的性质模运算满足交换律、结合律、分配律,并存在加法逆元,以及在加法与乘法运算下的恒等性。(1)交换律:(2)结合律:(w+x)+ymod n=w+(x+y)mod
10、n(wx)ymod n=w(xy)mod n 第4章数学理论基础(3)分配律:w(x+y)mod n=(wx)+(wy)mod n(4)恒等性质:(0+w)mod n=w mod n(1w)mod n=w mod n (5)存在加法逆元:对于Zn中的任意w,存在一个z,使得:w+z0(mod n)称z为w的加法逆元,并记作-w,且-w,z=-w第4章数学理论基础 4同余的性质同余的性质(1)若ab(mod m),cd(mod m),则acbd(modm),acbd(mod m);(2)若acbc(modm),gcd(c,m)=1,则ab(mod m);(3)若acbc(modm),gcd(c,
11、m)=d,则ab(mod(md);(4)若ab(modm),k0,则akbk(modnk);(5)若ab(modm),d|gcd(a,b,m),则a/db/d(modn/d);(6)若ab(modm),d|m,则ab(modd);(7)若ab(modm),则gcd(a,m)=gcd(b,m)。第4章数学理论基础 5.模模n求逆元的算法求逆元的算法设n和u都是整数,且un,n0。若存在一个整数v,0vn,使 成立,则u模n的逆元就是v。第4章数学理论基础 第4章数学理论基础【例41】求13模35的逆元。解解因为 所以13模35的逆元为(-8)mod3527。第4章数学理论基础 第4章数学理论基础
12、【例42】计算322 mod 12。解解 第4章数学理论基础 4.2.24.2.2EulerEuler函数及相关定理函数及相关定理定理定理41(中国剩余定理)设m1,m2,mr是两两互素的正整数,a1,a2,ar是整数,则同余方程组为 xai(modmi)(i=1,2,,r)(413)模M=m1,m2,mr有惟一解:(414)式中:Mi=M/mi,yi=M-1imod mi(i=1,2,r)。第4章数学理论基础【例43】求解求解 第4章数学理论基础 再计算yi:第4章数学理论基础 则 设n是一个正整数,定义(415)为Euler函数。Euler函数是定义在正整数集合上的函数。显然,(n)为小于
13、n且与n互素的非负整数的个数。由定义可以立即得出,如果p是一个素数,则(p)p-1,(1)=1是显然的。第4章数学理论基础 定理定理42如果n1和n2互素,则(416)证明证明对任意的0 xn1n2,设(0r1n1)(4-17)(4-18)r1和r2实际上就是用n1和n2分别除x所得的余数。显然,给定x,则可以惟一确定r1和r2。反过来,给定r1和r2,则根据中国剩余定理可以惟一确定x。因此,x与数对(r1和r2)是一一对应的。第4章数学理论基础 因为n1和n2互素,所以x与n1和n2互素,当且仅当x与n1和n2都互素。x与n1和n2都互素当且仅当r1与n1互素并且r2与n2互素。因此,与n1
14、和n2互素的数x的个数等于数对(r1,r2)的个数,其中r1与n1互素,r2与n2互素。因为与n1互素的数r1的个数为(n1),与n2互素的数r2的个数为(n2),所以与n1 n2 互素的数x的个数为(n1)(n2),即(n1n2)=(n1)(n2)。证毕 第4章数学理论基础 定理定理43如果(419)式中:为素数;为正整数,则(420)定理定理44(Euler定理)设x和n都是正整数,如果gcd(x,n)=1,则(421)第4章数学理论基础 证明证明设(n)k;r1,r2,rk(0r1,r2,rkn)互不相同且都与n互素。因为x与n互素,所以xr1,xr2,xrk也都与n互素。如果则必然有(
15、423)这与假设相矛盾。因此,xr1,xr2,xrk模n两两不同余,即(424)第4章数学理论基础 于是,因为r1,r2,rk都与n互素,所以xk1(mod n)。证毕证毕Euler定理的另一种有用的表达形式为 (425)(426)第4章数学理论基础 推论41(Fermat定理)设x和p都是正整数。如果p是素数且gcd(x,p)1,则(427)定理定理45(Fermat定理)设x和p都是正整数。如果p是素数,则(428)证明证明因为p是素数,所以x或者与p互素,或者是p的倍数。如果x与p互素,则由推论41知结论显然成立。如果x是p的倍数,则xp也是p的倍数。因此,xp x(mod p)0(mo
16、d p),则结论也成立。证毕证毕 第4章数学理论基础 定理定理46设n是一个正整数,Zn=0,1,2,n-1,对于uZn,存在vZn使得uv modn=1的充分必要条件是(429)证明证明(1)必要性。显然,对任意bZn存在整数q,使得0bu-qn1,即对任意bZn,都有bu mod n1。因此,如果存在vZn使得uv mod n=1,则必然有gcd(u,n)1。第4章数学理论基础(2)充分性充分性。假设gcd(u,n)=1,则存在整数a和b使得(431)于是,au mod n=1(432)令v=a mod n则(433)证毕证毕 第4章数学理论基础 4.3群、域及环群、域及环 第4章数学理论
17、基础 在群定义中,G的运算“”可以是通常的加法或乘法。若为乘法,则常称e为单位元;若为加法,单位元常记为0,而逆元记为-a。在以后不致引起错误的情况下,运算符“”省略不写,即把ab写作ab。群中元素的个数称之为群的阶或元数。如果群的元数为有限值,则称为有限群;否则称为无限群。在群G中,对任意a,bG都有ab=ba,则称G为Abel群、交换群、加法群或可换群。第4章数学理论基础 一个非空集合S,仅仅满足群定义中的条件(1)和条件(2),即运算满足封闭性和结合律,则称S为半群(Semigroup)。一个非空集合M,仅仅满足群定义中的条件(1)、条件(2)和条件(3),即运算满足封闭性和结合律,并且
18、有单位元,则称M为含幺半群(Monoid)、弱群或类群。第4章数学理论基础 【例44】证明非空集合0,1是的一个群。已知运算法则是(434)第4章数学理论基础 第4章数学理论基础 (3)因为00,1,且 则0,1集合中存在单位元e0;(4)因为集合0,1中的元素“0”和“1”,都有 则“0”和“1”都存在逆元素,“0”的逆元素就是“0”本身;“1”的逆元素就是“1”本身。由于在运算法则下,集合0,1满足群定义中的四个条件,按群的定义可得0,1集合是运算法则的一个群。第4章数学理论基础 又因为0,1集合在运算法则下满足交换律,即 则由定义可知,集合0,1是运算法则的交换群。同理可证下列结论:(1
19、)全体整数按照通常的加法可构成群,并且是Abel群、无限群。而在通常的乘法运算法,全体整数不构成群,因为除1外,其他元素都没有逆元,它只能构成含幺半群。同样,全体偶数在加法运算下构成群,而在乘法运算下不构成群。全体实数在加法运算下构成群;而除0元素外的全体实数在乘法运算下构成群。第4章数学理论基础(2)Zn在模n的加法下构成群,群的阶为n。(3)Z*n在模n的乘法下构成群,群的阶为(n)。(4)所有n阶矩阵的全体M,在矩阵的加法运算下构成群,其单位元为0矩阵;在矩阵的乘法运算下,若为满秩矩阵则构成群;否则不构成群。第4章数学理论基础 2.2.群的主要特性群的主要特性群的主要特征有以下两点。(1
20、)一个群的单位元是惟一的,每一个群元素的逆元素也是惟一的。证明证明若e和e都是群G的单位元,则e和e必定又都是群G中的元素。当把e看做单位元,e看做另一元素时,有ee=e。当把e看做单位元;e看做另一元素时,又有ee=e,由群定义中的条件(3)有(4-35)第4章数学理论基础 所以e和e不可能是群G中两个不同元素。这就证明了单位元的惟一性。下面证明逆元的惟一性。若gG,且g具有逆元素:g1-1和g-12,根据群的定义,有(436)第4章数学理论基础(2)设G是运算法则的一个群,若g1G,g2G,则(437)证明证明根据群的定义,有(438)所以群G中任意两个元素g1和g2在指定运算法则下的运算
21、值g1 g2的逆元素(g1 g2)-1等于逆元素g-12和g-11在运算法则下的运算值g-12g-11。第4章数学理论基础 4.3.2子群及陪集子群及陪集1.基本概念基本概念设集合G是运算法则的一个群,H是群G的一个非空子集。如在运算法则下,集合H也构成一个群,则非空子集H称为群G的一个子群。记作 。显然,任何群G都有两个子群:群G本身和仅仅由单位元构成的群。通常称这两个子群为平凡子群。除平凡子群之外的其他子群为真子群。例如:所有偶数在加法下构成的群是所有整数构成的加法群的子群。实际上,非空子集H在运算法则下只要满足以下两个独立条件,就符合子群定义的条件。第4章数学理论基础(1)具有封闭性。若
22、h1H,h2H,且有(439)(2)子集H中存在一个单位元e。若hH,则必有eH,则有(440)下面介绍为什么只要满足式(439)和式(440)两个独立条件,非空子集H就是群G在运算法则下的一个子群。(1)若h1H,h2H,h3G,因H是G的子集,所以必有h1G,h2G,h3G。由于G是运算法则的一个群,所以必有(441)第4章数学理论基础(2)因为集合G是运算法则的一个群,所以G中必存在一个单位元e。集合H是群G的非空子集,由式(440)可知,H中又存在一个单位元e。根据群的单位元的惟一性,非空子集中的单位元e就是群G的单位元。这就是说,群G中的单位元e一定在其子群H之中,或子群H中的单位元
23、e一定就是群G中的单位元e。第4章数学理论基础(3)若hH,因H是G的子集,所以必有hH。又因G是运算法则的一个群,则h在G中必有逆元素h-1,即有(442)由式(440),有eH;由式(439),即非空子集H的封闭性,必有h-1H。这就是说,非空子集H中任一元素h的逆元素h-1都在H之中,或者说,非空子集H中任一元素h在H中都存在逆元素h-1。第4章数学理论基础 所以运算法则的群G的非空子集H只要满足在运算法则下的式(439)和式(440)两个独立条件,就能满足运算法则的群的四个条件和群G的子群的条件。下面介绍陪集的概念。设集合H=e,h2,h3,h2k是群G=g1,g2,g3,g2n的子群
24、,gi是群G中的一个元素,但gi不是子群H中的元素,即gi G,gi,把 第4章数学理论基础 称为子群H在群G中的一个“左陪集”,把 称为子群H在群G中的一个“右陪集”。“左陪集”和“右陪集”中的第一个元素 称为“陪集首”。若群G是运算法则的交换群,那么“左陪集”和“右陪集”一定相同。即(446)(444)(445)(443)这时,“左陪集”和“右陪集”通称为“陪集”。第4章数学理论基础 2.2.子群的主要性质子群的主要性质子群有以下三个主要性质。(1)运算法则群G中所有元素均可由其子群H中的元素表示。这个特性说明,群G=g1,g2,g3,g2n的所有元素gi(i=1,2,2n)可由子群H=e
25、,h2,h3,h2k的所有元素hi(i=1,2,2k;h1=e)及子群H的若干个陪集(或“左陪集”或“右陪集”)表示。第4章数学理论基础(2)群G中的两个元素g1和g2在子群H的同一陪集之中的充要条件是(447)证明必要性。设群G中两个元素g1和g2在子群H的同一陪集之中。令该陪集的陪集首为gi,则(448)由式(437),得 第4章数学理论基础 充分性。设g1和g2是群G中的两个元素,且有(450)则有(451)(452)(453)令g1所在陪集的陪集首为gi,且在子群H中的元素hj的同一列,即令(454)第4章数学理论基础 由式(453),得(qj,k)(455)所以g1和g2所在陪集的陪
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 理论基础 课件
限制150内