级信息安全数学基础试卷B答案Word下载.doc
《级信息安全数学基础试卷B答案Word下载.doc》由会员分享，可在线阅读，更多相关《级信息安全数学基础试卷B答案Word下载.doc（6页珍藏版）》请在冰点文库上搜索。
1．
（1）。
2．（4）。
3．（3）。
4．
（2）。
5．
（2）。
6．（3）。
7．
（2）。
8．（4）。
9．（4）。
10．（3）
二．填空题：
1．设m是正整数，a是满足a|m的整数，则一次同余式：
axº
b（modm）有解的充分必要条件是（a,m）|b。
当同余式axº
b（modm）有解时，其解数为d＝（a,m）。
2．设m是正整数，则m个数0,1,2,…,m－1中与m互素的整数的个数叫做m的欧拉（Euler）函数，记做j（m）。
3．整数2t＋1和2t－1的最大公因数（2t＋1，2t－1）＝1。
4．设a,b是正整数，且有素因数分解，，则，
。
5．如果a对模m的指数是j（m），则a叫做模m的原根。
6．设m是一个正整数，a是满足（a,m）＝1的整数，则存在整数a¢
，1≤a¢
＜m，使得aa¢
≡1（modm）。
7．Wilson定理：
设p是一个素数，则（p－1）!
≡－1（modp）。
8．（中国剩余定理）设m1,…,mk是k个两两互素的正整数，则对任意的整数b1,…,bk同余式组xº
b1（modm1）
…………
xº
bk（modmk）
有唯一解。
令m＝m1…mk，m＝miMi，i＝1,…,k，则同余式组的解为：
x≡M1¢
M1b1＋…＋Mk¢
Mkbk（modm），
其中Mi¢
Mi≡1（modmi）,i＝1,2,…,k。
9．正整数n有标准因数分解式为，则n的欧拉函数
。
10．设G和G¢
是两个群，f是G到G¢
的一个映射。
如果对任意的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＝4p1p2…ps－1。
显然，每个pi（i＝1,2,…,s）都
不是q的素因数，否则将会导致pi|1，得到矛盾。
如果q是素数，由于
q＝4p1p2…ps－1＝4（p1p2…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>
即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<
令r＝a-bq，则有a=bq+r，0£
唯一性.假设还有一对整数q1,r1也满足：
a=bq1+r1，0£
r1<
（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,j（n））＝1，edº
1（modj（n）），1<
e<
j（n），1£
d<
j（n）。
对任意整数c，1£
c<
n，若aeº
c（modn），则有cdº
a（modn）。
（12分）
因为（e,j（n））＝1，根据2.3定理4，存在整数d，
1≤d<
j（n）,使得
ed≡1（modj（n））
因此，存在一个正整数k使得ed＝1＋kj（n）。
由，a与n＝pq互素知，（a,p）＝1根据Euler定理，
aj（p）≡1（modp）
两端作k（j（n）/j（p））次幂得，akj（n）≡1（modp）
两端乘以a得到a1＋kj（n）≡a（modp）
即aed≡a（modp）
同理，aed≡a（modq）
因为p和q是不同的素数，根据2.1定理12，
aed≡a（modn）
因此，
cd≡（ae）d≡a（modn）
4．证明：
设p和q是两个不相等的素数，证明：
。
（6分）
因为p和q是两个不相等的素数，由Euler定理，，，所以，而，因此。
四．计算题（写出详细计算过程）：
1．用模重复平方法计算12996227（mod37909）。
（6分）
设m=37909,b=12996,令a=1,将227写成二进制，
227=1+2+25+26+27
运用模重复平方法，我们依次计算如下:
（1）n0=1,计算
a0=a×
b≡12996,b1≡b2≡11421（mod37909）
（2）n1=1,计算
a1=a0×
b1≡13581,b2≡b12≡32281（mod37909）
（3）n2=0,计算
a2=a1≡13581,b3≡b22≡20369（mod37909）
（4）n3=0,计算
a3=a2≡13581,b4≡b32≡20065（mod37909）
（5）n4=0,计算
a4=a3≡13581,b5≡b42≡10645（mod37909）
（6）n5=1,计算
a5=a4×
b5≡22728,b6≡b52≡6024（mod37909）
（7）n6=1,计算
a6=a5×
b6≡24073,b7≡b62≡9663（mod37909）
（8）n7=1,计算
a7=a6×
b7≡7775（mod37909）
最后，计算出
12996227≡7775（mod37909）
2．设a＝－1859，b＝1573，运用广义欧几里得除法
（1）计算（a,b）；
（2）求整数s，t使得sa＋tb＝（a,b）。
（8分）
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（mod77）。
（16分）
利用2.4定理1（Euler定理）及中国剩余定理计算。
令x＝21000000,因为77＝7·
11，所以，
计算x＝21000000（mod77）等价于求解同余式组
x＝21000000≡b1（mod7）
x＝21000000≡b2（mod11）
因为Euler定理给出2j（7）≡26≡1（mod7）,
以及1000000＝166666·
6＋4，所以
b1≡21000000≡（26）166666·
24≡2（mod7）。
类似地，因为2j（11）≡210≡1（mod11），
1000000＝100000·
10，所以
b2≡21000000≡（210）1000000≡1（mod11）。
x≡2（mod7）
x≡1（mod11）
令m1＝7,m2＝11,m＝m1·
m2＝77
M1＝m2＝11,M2＝m1＝7
分别求解同余式
M1¢
·
11≡1（mod7），M2¢
7≡1（mod11）
得到M1¢
＝2,M2¢
＝8。
故x≡2·
11·
2＋8·
7·
1≡100≡23（mod77）
因此，2100000000≡23（mod77）。
2007《信息安全数学基础》B试卷第6页共6页
升级会员 