数论与代数知识初步上_第1页
数论与代数知识初步上_第2页
数论与代数知识初步上_第3页
已阅读5页,还剩16页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第二讲数论与代数知识初步(上)现代密码系统中,消息都是事先转换成数 值进行加密传输。密码过程是一些输入输 岀都是数值的数学操作,建立,分析,攻 击这些算法需要数学工具。其中在实践中 应用最为成功的数学理论当然是数论和代 数,特别是同余理论。本讲提要整数的基本概念1整除性定义1对于整数心0, b0我们说°整除b,如果存在一个整数 k使得b =ka,我们把a叫做b的因数,b叫做d的倍数,记为alb。 如果这个比不存在,我们说a不整除记为必。性质1(1)对于任意°工0, aK), aa,对于任意b,llb。(2) 如果alb, b I c,贝!jalc。(3) 如果alb, al

2、e,贝a I (sb+tc),这里s和f是任意整数。 证明.显而易见。(2) 由定义存在和满足b = ka, c = lb,所以有c = kla。(3) 由定义可写出b = kxa, c = k2a,所以sb+tc =+tk2)a即 alsb+Tc。定理1 设Q, b是两个整数,其也>0,则存在两 个唯一的整黝及厂,使得a = bq+r, 0<r <b成立。2素数定义2 个大于1的正整数,如果它的正因数只有1和 它本身,就叫做素数,否则就叫做合数。定理2素数的个数是无穷的。证明如果素数的个数是有限的可令卩=2,戸=3,,pk 是全体素数。再令二卩几仇+1,知其必为合数, 而P

3、不可为",2,,几之中任意一个整除,必然存在 其它素数(为什么,请思考),因此,与素数的个数是 有限的假设矛盾。定理3存在无穷多个形如4-1的素数。2素数(续)定理4对于任意给定整数c°,不存在整系数多项 (x) = anx11 + an_xxnx H1- axx + a0 (an 0,n> 0),使得兀取所有的整数时,/(x)都表示素数。200以内的素数:23 57 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127131 137 139 149

4、 151 157 163 167 173 179 1 191 193 197 1992素数(续)定理5(素数数量定理如果乃(兀)表示小于x的所有素数,则有X、龙(兀)2,也就是说当YTOO时,比率龙(x)/(x/lnx)-> 1。lnx在各种密码应用中经鞭求使用300f立左右的十进制素数 通过定理戲们可以估计兀(1O300) 龙(10299)2lnl O300In 10299"3x10297,因此,足够使用。3最大公约数定义3设a,色,陽是个不全为零的整数。整数是 它们之中每一个的因数那么d就叫如。2,,色的一个 公因数。整数2,。2,,的公因数中最大的一 4s叫最大 公因数,

5、记作(如幻,a)若(如们,曾)= 1,就说 Q,,互素。定理6设a, b, c是任意三个不全为零白靈数,且a = bq + c,其中q是整数,则(。,b) = (b,c)o3最大公约数(续)Euclidear法的表述不失一般性假定任意z0, b0有a = bq、+ 斤,0< 斤 <bb = rxq2+rvO<r2<rx斤-r23 +< 厶 < r2 %3 = n-lQn-l + 匚1,° < 乙1 < %一2 rn-2 = -xQn + 力 ° < 乙 < 乙一1 乙一1 =乙么+1 +乙+1,乙+1=0。定理7任

6、意q >0, Z?>0,贝临,b)就是上述过程中最后 一个不等于零的余数,即(q, b) = rno3最大公约数(续)定理8若任给整数i0, b>0,则存在两个整数n, n 使得a, Id) - ma-nbo例子1计算(1180482)o1180=2-482+216482=2 216+50216=4-50+1650 = 3-16+216=28 + 0。因此,(1180482)= 2o可以看到余数都经历了:余数-除数T被除数T忽略的过程。3最大公约数(续)根据定理7我们还可以得到递推公式:xj = qm + xj-2X = -% 儿 i + S% 儿=-£儿一1 +

7、儿一2 贝!+byn = (q, b)o因I 止匕,兀=1, 2,兀=4xo + 召=9,=3x3 + Jr? = 29。同样有儿=71,所LU1180(-29) + 482-71=2 = (1180480。这一过程被称为扩uclideaM法。3最大公约数(续)定理9若° I be,b) = 1,贝临 I Co设 > 2,,(心2,_1)=比_1,(比_1,曾)= /那么有下面的定理。 定理1皓a”勺''a”(">2)是个正整数,贝|定理11若如 勺,an(n > 2)是个正整数,则存在整数,£使得axxx + a2x2 anxn

8、4最小公倍数定义4设Q,,是n(- 2)个不为o的整数。若/是这 个数中每一个的倍数,那么加就叫这H个数的一个公倍 数。在dp。夕,暫的一切公倍数中最小的正整数叫做最 小公倍数,记作如dy,色。定理12设5是任意的两个整数,则(1)0,b的所有公倍数就是Q,切的所有倍数。b=ab(。,b)4最小公倍数(续)设 > 2, % > 0, a。>(), an > 0, a, a0 = m2, m2, a3 = m3, ,他_2,色_1=他_1,叫_1,an = mn,那么有下面的定理。 定理13若勺,陽是(2)个正整数,贝I5整数唯一分解定理定理14设Q是任一大于 1的整数,

9、贝山的除1以外的最小 正因数g是素数,并且是合数时,q < yao引理1若P是一素数,Q是任一整数,则旬la或(p, Q) lo弓I理2若p是素数,pab,贝ipapbo5整数唯一分解定理(续)、算术基本定理说明,任意大于1的整数能够唯一写成 a = p: p?p:, e >O(i = l,k),其中Pt < Pj(i < J) 是素数。因此,对于。>0和b>0,且a = P:P,-p?,a. >O(Z = 1,.-, k b = pPp.p 龙(心 1,,k), 有aa,6 = P(乜禹).£ 畀勺 $),b = p'ra,p;哄4血).p驚J0)。由 于x + y = max(x,y) + min(x, y),所以,ab = a, b(a, b 即q,b=ab(d,ob)6一次不定方程二元一次不定方程是指ax- a2y = n, (3)其中如a2, 是给定的整数,°禺2工°。定理16方程(3)有整数解的充分必要条件是(如 a2) I no定理17设(如 色)=1,则方程(3)的全部解可表示为x = x()+ a2t, y = y0 -其中,儿为方程(3)的一组解,/为任意整数。6 一次不定方程(续)定理18设s2, S元一次不定方程°內+°2笔+色弋二弘

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论