数论与代数知识初步上

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笔+色弋二弘