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

姓名 学号 学院 专业 座位号 ( 密 封 线 内 不 答 题 )密封线线_ _ 诚信应考,考试作弊将带来严重后果！ 华南理工大学期末考试信息安全数学基础试卷A答案注意事项：1. 考前请将密封线内填写清楚； 2. 所有答案请直接答在试卷上； 3考试形式：闭卷； 4. 本试卷共 四大题，满分100分，考试时间120分钟。题 号一二三四总分得 分评卷人一 选择题：（每题2分，共20分）1 (2) 。 2 (3)。 3 (1) 。4 (3)。5 (2) 。6 (3) 。 7 (4)。 8 (3) 。 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设m是正整数，若同余式 x2a(mod m)，(a, m)=1 有解，则a叫模m的平方剩余。4设a, b是正整数，且有素因数分解 ，则 ， 。 5如果a对模m的指数是 j (m) ，则a叫做模m的原根。6设m是一个正整数，若 r1, r2, , rj (m)是j (m)个 与 m 互素的整数，并且两两模 m 不同余，则r1, r2, , rj (m)是模m的一个简化剩余系。7Wilson定理：设p是一个素数，则 (p1)!1 (mod p) 。82007年1月18日是星期四，第220070118天是星期 三 。9(中国剩余定理) 设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 。10正整数n有标准因数分解式为 ，则n的欧拉函数 。三证明题 （写出详细证明过程）：（共30分） 1设m是一个正整数，ab（mod m），如果整数d(a, b, m)证明：。 （6分）证明 因为d | (a, b , m) ,所以存在整数 a, b, m使得 ada , bdb , mdm 由ab (mod m) ，知存在整数 k 使得abmk, 即 dadbdmk , 因此，abmk，这就是 ab (mod m) , 或者 3设m是一个正整数，a满足(a, m)1，则存在整数a，1 a m使得 aa1 (mod m)。 （6分）证法一：(存在性证明) 因为(a，m)1, 根据定理3, x 遍历模 m 的一个最小简化剩余系时，ax 也遍历 模 m 的一个简化剩余系。因此，存在整数 xa， 1am 使得aa 属于1 的剩余类， 即aa1 (mod m)。证法二：(构造性证明) 因为(a，m)1, 根据1.3定理5, 运用广义欧几里得除法，存在整数 s，t 使得 satm(a, m)1 因此，令 as (mod m) 满足 (satm)(aatm)aa1 (mod m) 。 3证明Euler定理：设m是大于1的正整数，如果a是满足(a, m)1的整数。则aj (m) 1 (mod m)。 （12分）证明：取 r1, , rj (m) 为模 m 的简化剩余系, 则当整数 a 满足(a, m)1 时, 根据2.3 定理 3， ar1, , arj (m)也为模 m 的一个简化剩余系, 即 ar1, , arj (m)中之一必与且仅与r1, , rj (m)中之一必模 m 同余。根据 2.1 定理 4, 有 ( ar1) (arj (m) r1 rj (m) (mod m)因此, r1 rj (m) (aj (m)1) 0 (mod m)又从(r1 , m)1，(r2 , m)1, , (rj (m) , m)1 及1.4 定理 3 , 可以推出 (r1 rj (m), m)1从而, 根据 2.1 定理8, 得到 aj (m)10(mod m) 即 aj (m)1 (mod m)4证明：设p和q是两个不相等的素数，证明：。（6分）证明：因为p和q是两个不相等的素数，由Euler定理，所以，而，因此。四计算题（写出详细计算过程）：（共30分） 1设m737，a635，利用广义欧几里得除法求整数a，1 a m使得 aa1 (mod m)。 （6分）由广义 欧几里得除法，可找到整数 s224 , t193使得 (224) 635 193 7371 因此，a224513 (mod 737) 使得 635 5131(mod 737)。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运用中国剩余定理和模重复平方法计算31213 (mod 667)。 （16分）运用中国剩余定理及模重复平方法。令x31213，因为66723 29，所以计算 x (mod667)等价于求解同余式组x b1 (mod 23)x b2 (mod 29)由模重复平方法，计算 b131213 (mod 23)n23，b312 ，令a1。将13写成二进制， 1312223运用模重复平方法，依次计算如下：由模重复平方法，计算 b131213 (mod 23)n23，b312 ，令a1。将13写成二进制， 1312223运用模重复平方法，依次计算如下：(1) n01, 计算 a0a b13 , b1 b2 8 (mod 23)(2) n10, 计算 a1 a0 13 , b2 b12 18 (mod 23)(3) n21, 计算 a2a1 b24 , b3 b22 2 (mod 23)(4) n31, 计算 a3a2 b38 (mod 23)所以 b131213 8 (mod 23)类似的计算 b231213 (mod 29)n29，b312 ，令a1。将13写成二进制， 1312223运用模重复平方法，依次计算如下：类似的计算 b231213 (mod 29)n29，b312 ，令a1。将13写成二进制， 1312223运用模重复平方法，依次计算如下：(1) n01, 计算 a0a b22 , b1 b2 20 (mod 29)(2) n10, 计算 a1 a0 22 , b2 b12 23 (mod 29)(3) n21, 计算 a2a1 b213 , b3 b22 7 (mod 29)(4) n31, 计算 a3a2 b34 (mod 29)所以 b231213 4 (mod 29)求解同余式组x 8 (mod 23)x 4 (mod 29)令 m1 23, m2 29, m m1 m2 667 M1 m2 29, M2 m1 23分别求解同余式