……………………………………密………………………………………………封………………………………………线……………………………………线……………………………………… 学院 专业 座位号 诚信应考,考试作弊将带来严重后果！ 华南理工大学期末考试 《信息安全数学基础》试卷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, … , m－1中 与 m 互素的整数的个数 叫做m的欧拉(Euler)函数，记做? (m)。 3．整数2t＋1和2t－1的最大公因数(2t＋1，2t－1)＝ 1 。 ?s?1?2p2?ps,?i?0,i?1,2,?,s，4．设a, b是正整数，且有素因数分解 a?p1min(?2,?2)(a,b)?p1min(?1,?1)?p2?L?psmin(?s,?s)b?p1p2?ps,?i?0,i?1,2,?,s，则 ， _____________ ________ 姓名 学号 ( 密 封 线 内 不 答 题 ) ?1?2?smax(?s,?s)max(?1,?1)max(?2,?2) [a , b ] ? p 1 ? p 2 ? L ? p s 。 5．如果a对模m的指数是 ? (m) ，则a叫做模m的原根。 6．设 m 是一个正整数，a是满足 (a , m) ＝1 的整数，则存在整数a?，1≤a?＜m ，使得aa?≡1 (mod m)。 7．Wilson定理：设p是一个素数，则 (p－1)!≡－1 (mod p) 。 8．(中国剩余定理) 设m1, …, mk是k个两两互素的正整数，则对任意的整数b1, …, bk 同余式组 x ? b1 (mod m1) … … … … x ? bk (mod mk) 有唯一解。令m＝m1…mk，m＝miMi，i＝1,…,k，则同余式组的解为： x ≡ M1? M1b1＋…＋ Mk? Mk bk (mod m) ， 其中 Mi? Mi ≡1 (mod mi) , i＝1 , 2 ,…, k 。
?k?1?pk9．正整数n有标准因数分解式为 n?p1，则n的欧拉函数
1111n (1 ? ( n ) ? n ? (1 ? ) ? ? )(1 ? ) L (1 ? ) 。 ppppn1k10．设G和G? p是两个群，f是G到G?2 的一个映射。如果对任意的a, b∈G，都有 f(ab)=f(a)f(b) ，那么，f 叫做G到G? 的一个同态。
三．证明题 （写出详细证明过程）：（共30分）
1．证明：形如4k+3的素数有无穷多个。 （6分）
证明 分两步证明。
先证形如4k＋3的正整数必含形如4k＋3的素因数。 由于任一奇素数只能写成4n＋1或4n＋3的形式，而 (4n1＋1)(4n2＋1)＝16n1n2＋4n1＋4n2＋1
＝4(4n1n2＋n1＋n2)＋1, 所以把形如4n＋1的数相乘的积仍为4n＋1形式的数。 因此，把形如4k＋3的整数分解成素数的乘积时， 这些素因数不可能都是4n＋1的形式的素数，一定含有 4n＋3形式的素数。
其次，设 N 是任一正整数，并设
p1, p2 , … , ps是不超过N的形如4k＋3的所有素数。 令q＝4p1 p2 … ps－1。显然，每个pi (i＝1, 2, …, s)都 不是 q 的素因数，否则将会导致 pi |1，得到矛盾。 如果 q 是素数，由于
q＝4p1 p2 … ps－1＝4(p1 p2 … ps－1)＋3，即 q 也是 形如4k＋3的素数，并且显然q ? pi (i＝1, 2, …, s)， 从而 q > N 。即q是形如4k＋3的大于N的素数。 如果 q 不是素数，由第一步证明知q含有形如4k＋3
的素因数p，同样可证p ? pi (i＝1, 2, …, s)，从而 p > N 。
即p 是形如4k＋3的大于N的素数。由于N是任意的正整数，因此证明了 形如4k＋3的素数有无穷多个。
2．．设a, b是两个整数，其中b>0。则存在唯一一对整数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。
令 r＝a-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是两个不同的奇素数，n＝pq，a是与pq互素的整数。整数e和d满足(e, ? (n))＝1，ed ? 1 (mod ? (n))，1 < e < ? (n)，1 ? d< ? (n)。
证明：对任意整数c，1 ? c< n，若ae ? c (mod n)，则有cd ? a (mod n)。 （12分）
证明：
因为(e, ? (n)) ＝1，根据定理4，存在整数d， 1≤d< ? (n) , 使得
ed≡1(mod ? (n)) 因此，存在一个正整数 k 使得 ed＝1＋k ? (n) 。
由， a 与n＝ pq 互素知，(a, p)＝1根据Euler定理， a? (p)≡1 (mod p) 两端作 k(? (n) / ? (p)) 次幂得， ak ? (n)≡1 (mod p)
两端乘以 a 得到 a1＋k ? (n)≡a (mod p) 即 a ed≡a (mod p) 同理， aed≡a (mod q)
因为 p 和 q 是不同的素数，根据定理12， aed≡a (mod n) 因此，
c d≡(ae)d≡a (mod n)
4．证明：设p和q是两个不相等的素数，证明：pq?1?qp?1?1(modpq)。 （6分）
证明：因为p和q是两个不相等的素数，由Euler定理，q所以
p?1?1?modp?，pq?1?1?modq?，
pq?1?qp?1?1?modp?,pq?1?qp?1?1?modq?，而?p,q??1，因此
pq?1?qp?1?1?modpq?。
四．计算题（写出详细计算过程）：（共30分）
1．用模重复平方法计算12996227 (mod 37909)。 （6分） 设 m=37909, b=12996, 令a=1, 将227写成二进制， 227=1+2+25+26+27
运用模重复平方法，我们依次计算如下: (1) n0=1,计算
a0= a×b≡12996 , b1≡b2≡11421 (mod 37909) (2) n1=1 , 计算
a1=a0×b1≡13581 , b2≡b12≡32281 (mod 37909) (3) n2=0 ,计算
a2=a1≡13581 , b3≡b22≡20369(mod 37909) (4) n3=0 , 计算
a3=a2≡13581 , b4≡b32≡20065(mod 37909)
(5) n4=0 , 计算
a4=a3≡13581 , b5≡b42≡10645(mod 37909) (6) n5=1 , 计算
a5=a4×b5≡22728 , b6≡b52≡6024(mod 37909) (7) n6=1 , 计算
a6= a5×b6≡24073 , b7≡b62≡9663(mod 37909) (8) n7=1,计算
a7= a6×b7≡7775 (mod 37909) 最后，计算出
12996 227≡7775 (mod 37909)
2．设a＝－1859，b＝1573，运用广义欧几里得除法
(1) 计算(a, b)； (2) 求整数s，t使得sa＋tb＝(a, b)。737＝1?635＋102， 102＝737－ 1?635
635 ＝6? 102 ＋23， 23＝ 635 － 6?102 102＝4?23＋10， 10＝102－ 4?23 23＝2?10＋3， 3＝23－ 2?10 10＝3?3＋1， 1＝10－ 3?3 1＝10－ 3?3
＝(102－ 4?23)－3(23－ 2?10) ＝102－7 ? 23＋6 ? 10
＝ 102－7 ? 23＋6 (102－ 4?23) ＝7 ? 102－31? 23
＝ 7 ? 102－31? (635－ 6?103) ＝193 ? 102 －31? 635
＝193 ?(737－ 1?635) －31? 635 ＝193 ?737－ 224?635 所以 s＝ 193， t＝ －224，使得
193 ? 737＋(－224) ? 635＝1。
3．运用中国剩余定理和欧拉定理计算21000000 (mod 77)。 利用 定理 1 (Euler定理)及中国剩余定理计算。 令 x ＝21000000 , 因为 77 ＝7 · 11，所以， 计算 x ＝21000000 (mod 77) 等价于求解同余式组
（8分）16分）
（
2007级信息安全数学基础试卷-B-答案
