信息安全数学基础参考试卷.doc

《信息安全数学基础》参考试卷
一．选择题(在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内，多选不给分)： （每题2分，共20分）
1．576的欧拉函数值j (576) ＝ (　　 )。
(1) 96， (2) 192， (3) 64， (4) 288。
2．整数kn和k(n+2)的最大公因数(kn , k(n+2))=(　　 　)。
(1) 1或2，                                       (2) | kn |，
(3) | n | 或 | kn |，                    (4) | k | 或2| k | 。
3．模10的一个简化剩余系是 ( )。
(1) 1, 2, 3, 4, 5, 6, 7, 8, 9, 10， (2) 11, 17, 19 , 27
(3) 11, 13, 17, 19， (4) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9。
4．29模23的逆元是 ( )。
(1) 2， (2) 4，
(3) 6， (4) 11。
5．设 m1，m2是两个正整数，x1遍历模m1的完全剩余系，x2遍历模m2的完全剩余系，若( )遍历m1m2的完全剩余系。
(1) (m1，m2)=1，则m1x1＋m2x2 (2) m1和m2是素数，则m1x1＋m2x2
(3) (m1，m2)=1，则m2x1＋m1x2 (4) m1和m2是素数，则m2x1＋m1x2
6．下面的集合和运算构成群的是 ( ) 。
(1) <N，＋> （N是自然数集，“＋”是加法运算）
(2) <R，×> （R是实数集，“×”是乘法运算）
(3) <Z，＋> （Z是整数集，“＋”是加法运算）
(4) <P（A），∩> （P(A)＝{U | U是A的子集}是集合A的幂集，“∩”是集合的交运算）
7．下列各组数对任意整数n均互素的是 ( ) 。
(1) 3n+2与2n，(2) n－1与n2＋n＋1，(3) 6n+2与7n， (4) 2n+1与4n+1。
8．一次同余式234x ≡ 30（mod 198）的解数是 ( )。
(1) 0， (2) 6，
(3) 9， (4) 18。
9．Fermat定理：设p是一个素数，则对任意整数a有 ( )。
(1) a j (p)＝a (mod p)， (2) a j (p)＝1 (mod a)，
(3) a p ＝a (mod p)， (4) a p＝1 (mod p)
10．集合F上定义了“＋”和“ · ”两种运算。如果( )，则<F, “＋”,“ · ”>构成一个域。
(1) F对于运算 “＋”和 “ · ”构成环，运算“＋”的单位元是e，且F\{e}对于 “ · ”构成交换群
(2) F对于运算 “＋”构成交换群，单位元是e；F\{e}对于运算“ · ”构成交换群
(3) F对于运算“＋”和运算“ · ”都构成群
(4) F对于运算“＋”构成交换群，单位元是e；F\{e}对于运算“ · ”构成交换群；运算 “＋”和 “ · ”之间满足分配律

二． 填空题(按题目要求，将正确描述填在 上)：（每题2分，共20分）
1．设a, b是正整数，且有素因数分解 ，，则(a, b)＝ ，
[a, b]＝ 。
2．模5的3的剩余类C3(mod 5)写成模15的剩余类的并为：
C3(mod 5) = 。
3． 整数a，b满足(a，b)=1，那么对任意正整数n，都有(an， bn) =__________。
4．120, 150, 210, 35的最小公倍数[120, 150, 210, 35] = 。
5．模8的绝对值最小完全剩余系是 。
6．设n是一个正整数，整数e满足1＜e＜j (n)且 ，则存在整数d，1≤d＜j (n)，使得ed≡1 (mod j (n))。
7．Wilson定理：设p是一个素数，则 。
8．P(A)是集合A的幂集，“Å”为集合的对称差运算。P(A)对于运算“Å”的单位元是 ，A的逆元是 。
9．设m，n是互素的两个正整数，则j ( m，n) = 。
10．设集合A有n个元素，则集合A×A有__________个元素，集合A上的不同运算有___________种。

三．证明题 （写出详细证明过程，共4小题，30分）
1．(1) 证明：形如6k＋5的正整数必含6k＋5形式的素因数。
(2) 证明：形如6k+5的素数有无穷多个。 （10分）

2．设a, b是任意两个不全为零的整数，证明
(1) 若m是任一正整数，则(am, bm) = (a, b)m。
(2) 若非零整数d满足d|a，d|b，则。 （8分）

3．设m是正整数，a≡b (mod m)，如果整数d满足d | (a, b , m)，则有

。 （6分）

4．证明：如果m和n是互素的大于1的整数，则mj(n)＋nj(m) ≡1 (mod mn)。
（6分）

四．计算题（写出详细计算过程，共2小题，30分）
1．设a＝8142，b＝11766，运用广义欧几里得除法
(1) 计算(a, b)； (2) 求整数s，t使得sa＋tb＝(a, b)。 （15分）

2．计算31000000 (mod 1771)。 （15分）
《信息安全数学基础》试卷第 4 页 共 4 页