2007级信息安全数学基础试卷-B-答案.doc

姓名 学号 学院 专业 座位号 ( 密 封 线 内 不 答 题 )密封线线_ _ 诚信应考,考试作弊将带来严重后果！ 华南理工大学期末考试信息安全数学基础试卷B答案注意事项：1. 考前请将密封线内填写清楚； 2. 所有答案请直接答在试卷上； 3考试形式：闭卷； 4. 本试卷共 四大题，满分100分，考试时间120分钟。题 号一二三四总分得 分评卷人一 选择题：（每题2分，共20分）1 (1) 。 2 (4)。 3 (3) 。4 (2)。5 (2) 。6 (3) 。7 (2)。 8 (4) 。 9 (4)。10 (3) 二 填空题：（每题2分，共20分） 1设m是正整数，a是满足a | m的整数，则一次同余式：ax b (mod m)有解的充分必要条件是 (a , m)|b 。当同余式ax b (mod m) 有解时，其解数为 d(a , m) 。2设m是正整数，则m个数0, 1, 2, , m1中 与 m 互素的整数的个数 叫做m的欧拉(Euler)函数，记做j (m)。 3整数2t1和2t1的最大公因数(2t1，2t1) 1 。4设a, b是正整数，且有素因数分解 ，则 ， 。 5如果a对模m的指数是 j (m) ，则a叫做模m的原根。6设 m 是一个正整数，a是满足 (a , m) 1 的整数，则存在整数a，1am ，使得aa1 (mod m)。7Wilson定理：设p是一个素数，则 (p1)!1 (mod p) 。8(中国剩余定理) 设m1, , mk是k个两两互素的正整数，则对任意的整数b1, , bk 同余式组 x b1 (mod m1) x bk (mod mk)有唯一解。令mm1mk，mmiMi，i1,k，则同余式组的解为： x M1 M1b1 Mk Mk bk (mod m) ，其中 Mi Mi 1 (mod mi) , i1 , 2 , k 。9正整数n有标准因数分解式为 ，则n的欧拉函数 。10设G和G 是两个群，f是G到G 的一个映射。如果对任意的a, bG，都有 f(ab)=f(a)f(b) ，那么，f 叫做G到G 的一个同态。三证明题 （写出详细证明过程）：（共30分） 1证明：形如4k+3的素数有无穷多个。 （6分）证明 分两步证明。 先证形如4k3的正整数必含形如4k3的素因数。 由于任一奇素数只能写成4n1或4n3的形式，而 (4n11)(4n21)16n1n24n14n21 4(4n1n2n1n2)1,所以把形如4n1的数相乘的积仍为4n1形式的数。因此，把形如4k3的整数分解成素数的乘积时，这些素因数不可能都是4n1的形式的素数，一定含有4n3形式的素数。 其次，设 N 是任一正整数，并设 p1, p2 , , ps是不超过N的形如4k3的所有素数。令q4p1 p2 ps1。显然，每个pi (i1, 2, , s)都不是 q 的素因数，否则将会导致 pi |1，得到矛盾。如果 q 是素数，由于q4p1 p2 ps14(p1 p2 ps1)3，即 q 也是形如4k3的素数，并且显然q pi (i1, 2, , s)，从而 q N 。即q是形如4k3的大于N的素数。 如果 q 不是素数，由第一步证明知q含有形如4k3的素因数p，同样可证p pi (i1, 2, , s)，从而 p N 。即p 是形如4k3的大于N的素数。由于N是任意的正整数，因此证明了形如4k3的素数有无穷多个。 2设a, b是两个整数，其中b0。则存在唯一一对整数q, r 使得a = bq + r，0 r b。 （6分）证明：存在性. 考虑整数序列： , -3b, -2b, -b, 0, b, 2b, 3b, 序列的各项把实数轴划分成长度为b的区间，a一定落在其中的一个区间中。因此，存在一个整数q使得 qb a (q+1)b， 即 0 a-bq b。令 ra-bq，则有 a = bq + r，0 r b。唯一性. 假设还有一对整数q1, r1 也满足： a = bq1 + r1，0 r1 b。 (2)(1)和(2)两式相减得 b(q - q1) - (r - r1)。 (3)当 q q1时，(3)式左边的绝对值大于等于b，而右边的绝对值小于b，得到矛盾。故q q1， r r1。 3设p，q是两个不同的奇素数，npq，a是与pq互素的整数。整数e和d满足(e, j (n)1，ed 1 (mod j (n)，1 e j (n)，1 d j (n)。证明：对任意整数c，1 c n，若ae c (mod n)，则有cd a (mod n)。 （12分）证明：因为(e, j (n) 1，根据2.3定理4，存在整数d，1d j (n) , 使得 ed1(mod j (n) 因此，存在一个正整数 k 使得 ed1k j (n) 。由， a 与n pq 互素知，(a, p)1根据Euler定理， aj (p)1 (mod p)两端作 k(j (n) / j (p) 次幂得， ak j (n)1 (mod p)两端乘以 a 得到 a1k j (n)a (mod p)即 a eda (mod p)同理， aeda (mod q)因为 p 和 q 是不同的素数，根据2.1定理12， aeda (mod n)因此， c d(ae)da (mod n)4证明：设p和q是两个不相等的素数，证明：。（6分）证明：因为p和q是两个不相等的素数，由Euler定理，所以，而，因此。四计算题（写出详细计算过程）：（共30分） 1用模重复平方法计算12996227 (mod 37909)。 （6分）设 m=37909, b=12996, 令a=1, 将227写成二进制， 227=1+2+25+26+27 运用模重复平方法，我们依次计算如下:(1) n0=1,计算 a0= ab12996 , b1b211421 (mod 37909) (2) n1=1 , 计算 a1=a0b113581 , b2b1232281 (mod 37909)(3) n2=0 ,计算 a2=a113581 , b3b2220369(mod 37909)(4) n3=0 , 计算 a3=a213581 , b4b3220065(mod 37909)(5) n4=0 , 计算 a4=a313581 , b5b4210645(mod 37909)(6) n5=1 , 计算 a5=a4b522728 , b6b526024(mod 37909)(7) n6=1 , 计算 a6= a5b624073 , b7b629663(mod 37909)(8) n7=1,计算 a7= a6b77775 (mod 37909)最后，计算出 12996 2277775 (mod 37909)2设a1859，b1573，运用广义欧几里得除法(1) 计算(a, b)； (2) 求整数s，t使得satb(a, b)。 （8分）7371635102， 102737 1635 635 6 102 23， 23 635 6102 10242310， 10102 423 232103， 323 210 10331， 110 33110 33 (102 423)3(23 210) 1027 236 10 1027 236 (102 423) 7 10231 23 7 10231 (635 6103) 193 102 31 635 193 (737 1635) 31 635 193 737 224635所以 s 193， t 224，使得 193 737(224) 6351。3运用中国剩余定理和欧拉定理计算21000000 (mod 77)。 （16分）利用 2.4 定理 1 (Euler定理)及中国剩余定理计算。 令 x 21000000 , 因为 77 7 11，所以，计算 x 21000000 (mod 77) 等价于求解同余式组 x 21000000 b1 (mod 7) x 21000000 b2 (mod 11)因为 Euler 定理给出2j (7) 26 1 (mod 7) ,以及1000000 166666 64，所以 b1 21000000 (26)166666 24 2 (mod 7)。类似地，因为 2j (11) 210 1 (mod 11)， 1000000100000 10，所以 b2 21000000(210)1000000 1 (mod 11)。 x 2 (mod 7) x 1 (mod 11)令 m1 7, m2 11, m m1 m2 77 M1 m2 11, M2 m1 7分别求解同余式 M1 111 (mod 7)，M2 71 (mod 11)得到 M12 , M28。故 x2 11 28 7 1100 23(mod 77)因此，2100000000 23（mod 77)。2007信息安全数学基础B试卷第 6 页 共 6 页