第-1讲 数学背景

1、2020/7/1,1,网络与信息系统安全 数学背景,2020/7/1,2,数 论 除数(因子)的概念： 设a,b为两个任意整数，z为全体整数构成的集合，若 b0且 使得a=mb, 称b整除a.记为ba,还称b为a的除数(因子). 注:若a=mb+r且01都可以写成唯一的表达式 aP11P22Ptt，这里P1P2P3Pt 是素数， 其中i0 例：305613117334,2020/7/1,4,最大公约数： 若a,b,kz，如果ka，kb，称k是a和b的公约数。 正整数c称为a和b的最大公约数，如果它满足 c是a和b的公约数。 对a和b的任何一个公约数k有 kc 。 注：1*. 等价的定义形式是：

2、 gcd（a,b）maxk ka，kb 2*. 若gcd（a,b）= 1，称a与b是互素的。 例： gcd（323,221）= 17,2020/7/1,5,最小公倍数： 若a,b,kz，如果ak，bk ，称k是a和b的公倍数。 正整数d称为a和b的最小公倍数，如果它满足 d是a和b的公倍数。 对a和b的任何一个公倍数k有dk。 等价的定义形式是：lcm（a,b）minkak，bk 例： lcm（56,34）= 952,2020/7/1,6,欧拉函数： 设n1若(n)表示比n小而与n互素的正整数的个数。 则(n)为欧拉函数。 以n24为例，比24小而与24 互素的正整数为：1，5，7， 11，1

3、3，17，19，23，因此，我们有(24)8。 性质：1）若p为素数，则(p)p1。 2）若p为素数，则(pk) pk-1(p1) 3）若m与n互素，则(m*n)(m)*(n) 4）若n P11P22Ptt， 则(n),2020/7/1,7,带余除法： az0，可找出两个唯一确定的整数q和r,使 a=qm+r, 0rb a = b*q1+r1 b = r1*q2 +r2 r1 = r2*q3 +r3 。 rn-2 = rn-1*qn +rn rn-1 = rn*qn+1 +rn1 ( rn10) 于是gcd（a,b） rn,2020/7/1,9,例：求gcd（1547, 560）。 解：154

4、7 = 2*560+427 560= 1*427 + 133 427 = 3*133 + 28 133 = 4*28 + 21 21 = 1*21 + 7 21 = 3*7 + 0 于是 gcd（1547, 560） = 7,2020/7/1,10,同余： 设a,b为整数，若mab，则称整数a和b模正整数m同余， 并写ab（mod m）, m称为同余式的模。 性质：1）自反性：对任意整数a有aa（modm） 2）对称性：如果ab(modm)则ba（modm） 3）传递性：如果ab (modm）bc（modm） 则ac(modm) 4）a(mod m)b(mod m)=(ab)(mod m) a

5、(mod m)*b(mod m)=a*b(mod m) 例：通过同余式演算证明5601是56的倍数。 解：53=12513(mod56)，于是有561691(mod56) 对同余式的两边同时升到10次幂，即有56560-1。,2020/7/1,11,全体整数集合z可按模m（m1）分成一些两两不交的等价类。 整数模m同余类共有m个，他们分别为mk+0, mk+1, mk+2, , mk+(m-1); kz，每一个算一类，每一类都可以选一个 代表元，一般选这一类中的最小的非负整数。于是称0, 1, 2, , m-1为标准完全剩余系。 Z模12的标准剩余系为：0,1,2,3,4,5,6,7,8,9,

6、10,11 定理1：设a为整数，若存在整数a，使a a 1（mod m）， 则称a为a对模m的数论倒数。 例：设m5， a 7，则a 3 定理2：若(a，m)=1 ，则对模m ，整数a有数论倒数a。,2020/7/1,12,Format定理： 如果p是素数并且a是正整数, a不是p 的倍数， 则ap-11(mod p) 证明： z*pzp(,p)=1 易见，z*p=1,2,3,(p-1)且因为（a,p）1知 a z*p=a,2a,3a,(p-1)a= z*p，原因是a z*p内的元素 两两不同。他们刚好为1，2，3，（p1）的一个排列。 所以 a*2a*3a* * (p-1)a1*2*3*(p

7、-1)(modp) 由（(p1)！，p）1，所以 ap-11(modp) 注：易见对（a，p）1 有apa(modp) 例：46 mod 7=4096 mod 7=1 47 mod 7=16384 mod 7=4,2020/7/1,13,Euclid定理： 若(a，m)=1，则a (m) 1(mod m) 证明：设小于m而和m互素的正整数为r1,r2,r3,r(m) (1) 他们是模m两两互不同余的。对每一个定数i来说，由于 a和ri都与m互素，所以(ari, m)=1， 所以ari同余于（1）中的某个ri即 ariri(mod m)，1 i (m) 并且当ij时有ari arj(mod m)

8、。于是， 为 的置换。所以有 由(ri, m)=1, 所以 a (m) 1(mod m),2020/7/1,14,同余式解： 设f(x)=an xn+ an-1 xn-1 + + a0为整系数多项式， m为正整数，若存在整数x使同余式f(x) 0(mod m)成立， 则称整数x为同余式的解。 若f(x)为一次方程，则称其为一次同余式 ax b(mod m) 定理3：若(a，m)=1，则同余式ax b(mod m)恰有一个解。 定理4：一次同余式ax b(mod m)， a 0 (mod m)有解的 充要条件是(a，m)b，若有解，解的个数为d=(a，m) 例：解同余式6x 15(mod 33)

9、 解：2x 5(mod 11)，x=5*6 (mod 11)=8 (mod 11) 又x=19，30(mod 11)亦为解,2020/7/1,15,中国剩余定理： 例子：（孙子算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？ 答曰：二十三。 232*70+3*21+2*15(mod 105) （口诀：三人同行七十稀，五树梅花廿一枝， 七子团圆月正半，除百零五便得知。） 问，70，21，15如何得到的？ 原问题为： 求解同余方程组,2020/7/1,16,注意：若x0为上述同余方程组的解，则x0=x0+105*k(kz) 也为上述同余方程组的解。有意义的是，解题口诀提示

10、我们先解下面三个特殊的同余方程组 (1) (2) (3) 的特殊解 =? =? =? 以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)，因为从（1）的模数及条件知， x应是35的倍数，于是可以假设x35y,2020/7/1,17,35y1(mod 3)相当于2y1(mod 3)解出y=2（mod3） 于是x35*2 70(mod105) 类似地得到(2)、(3)方程的模105的解21、15。 于是有 得,2020/7/1,18,中国剩余定理： 设m1,m2,mr两两互素，并记N=m1m2mr，则同余方程组 在模N同余的意义下有唯一解。,2020/7/1,19,平方剩余： 设a zm*如果存在xzm*，使得x2a(mod m)有解， 则称a为模m的平方剩余，否则称a为模m的非平方剩余。 例如： x2a(mod 7)， 当a1，2，4时有解，当a3，5，6时无解。 模运算： (a*b)modm=(a mod m)*(b mod m)(mod m) (a*b) (a*c) modm，则bc modm 成立的 条件是(