密码学数学基础习题集.doc
《密码学数学基础习题集.doc》由会员分享，可在线阅读，更多相关《密码学数学基础习题集.doc（60页珍藏版）》请在冰点文库上搜索。
北京电子科技学院
《密码学数学基础》习题集
信息安全系密码教研室
2015年10月
目
录
第一章带余除法...................................................................................................3
一、整数的最大公因子及其表示..................................................................3
二、多项式的最大公因子及其表示..............................................................7
三、标准分解和最小公倍数..........................................................................9
四、其他类型题............................................................................................11
第二章
同余方程...............................................................................................12
一、同余性质（剩余系）............................................................................12
二、模幂运算................................................................................................14
三、模逆运算................................................................................................16
四、一次同余方程求解................................................................................18
第三章原根计算.................................................................................................26
一、阶、原根、指数....................................................................................26
二、阶的计算................................................................................................30
三、原根的计算............................................................................................32
四、综合........................................................................................................36
第四章二次剩余.................................................................................................38
第五讲
群...........................................................................................................49
一、群的概念................................................................................................49
二、循环群的生成元求解（可求原根）.........................................................49
三、子群及其陪集........................................................................................50
四、置换群上的计算....................................................................................53
五、群同态....................................................................................................54
第六章
环的性质...............................................................................................55
一、环的概念................................................................................................55
二、商环........................................................................................................57
第七章
域上计算...............................................................................................58
第一章带余除法
重点概念：
最大公因子、辗转相除法、标准分解式
重点内容：
用辗转相除法求解最大公因子及其表示。
一、整数的最大公因子及其表示
1.（288，392）＝
8
，
2.设a=1435,b=3371，计算（a,b）。
答：
3371=2?
1435+501
1435=2?
501+433
501=433+68
433=6?
68+25
68=2?
25+18
25=18+7
18=2?
7+4
7=4+3
4=3+1
3=3?
1
所以（1435,3371）=1
3.用辗转相除法求整数x，y，使得1387x-162y=（1387,162）。
答：
用辗转相除法，如下表计算：
x
-y
q
1387
1
0
162
0
1
8
91
1
-8
1
71
-1
9
1
20
2
-17
3
11
-7
60
1
9
9
-77
1
2
-16
137
4
1
73
-625
x=73，y=625,（1387,162）=1.
4.计算：
（27090,21672,11352）。
答：
（27090,21672,11352）=（4386,10320,11352）=（4386,1548,2580）
=（1290,1548,1032）=（258,516,1032）=（258,0,0）=258。
5.用辗转相除法计算以下数组的最大公因子。
（1）（1046,697）
（2）（20301044）
解：
（1）1046=1´697+349
697=1´349+348
349=1?
348+1
348=348?
1
因此（1046,697）=1
（2）
2030=1?
1044+986
1044=1?
986+58
986=17?
58
因此（20301044）=58
6.用辗转相除法计算以下数组的最大公因子
（1）（2104,2720,1046）
（2）（27090,21672,11352）
解：
（1）先求出（2104,2720）的公因子d1，再求（d1,1046）的公因子d2，d2即为最
终要求的公因子。
因此：
2720=1?
2104+616
2104=3?
616+256
616=2?
256+104
256=2?
104+48
104=2?
48+8
48=6?
8
因此（2104,2720）=8，再求（8,1046），
1046=130?
8+6，
，
8=1?
6+2
6=3?
2
因此（2104,2720,1046）=2
（2）先求出（27090,21672）的公因子d1，再求（d1,11352）的公因子d2，d2即为
最终要求的公因子。
因此：
27090=1?
21672+5418
21672=4?
5418
因此（27090,21672）=5418，再求（5418,11352），
11352=2?
5418+516
5418=10?
516+258
516=2?
258
因此（27090,21672,11352）=258
7.用辗转相除法求以下数组的最大公因子，并把它表示为这些数的整系数线性组
合。
（1）1387,162
（2）2046,1620
解：
（1）用列表法可求出（1387,162）的公因子及相应的系数组合，如表1所示：
表1求（1387,162）的公因子及相应系数
u
v
q
1387
1
0
162
91
71
20
11
9
2
0
1
-1
2
-7
9
-16
1
-8
9
-17
60
-77
137
8
1
1
3
1
1
4
1
73
-625
2
0
由上表可得：
（1387,162）=1=1387?
73+162?
（-625）。
（2）用列表法可求出（2046,1620）的公因子及相应的系数组合，如表2所示：
表2求（2046,1620）的公因子及相应的系数组合
u
v
q
2046
1
0
1620
426
342
84
6
0
1
-3
4
-19
1
-1
4
-5
24
1
3
1
4
14
0
由上表可得：
（2046,1620）=6=1387?
（-19）+162?
24。
8.计算4389，5313，399的最大公因子，并把它表示为这些数的整系数线性组
合。
解：
先求4389与5313的最大公因子，如下表3，公因子为213。
再求213
与399的最大公因子，如表4，公因子为21。
表3求4389与5313的最大公因子
表4求213与399的最大公因子
u
v
q
u
v
q
5313
1
0
399
1
0
4389
924
693
231
0
1
-4
5
1
-1
5
-6
1
4
1
3
231
168
63
42
0
1
-1
3
1
-1
2
-5
1
1
2
1
0
21
-4
7
2
0
又由表3、4可分别得到如下两式：
231=5313?
5+4389?
（-6）
21=399?
（-4）+231?
7
（1）
（2）
将
（2）式的231用
（1）式等式右边代替并化解可得如下式：
21=399?
（-4）+5313?
35+4389?
（-42）
所以得到4389，5313，399的最大公因子为21，及其相应系数组合为-42，35，
-4。
二、多项式的最大公因子及其表示
1、求有理数域上多项式的最大公因式（f（x）,g（x）），其中
f（x）=x5+x4+x2+2x+1,
g（x）=x4+x3+x2+2x+1.
答：
用辗转相除法计算如下
x5+x4+x2+2x+1=x（x4+x3+x2+2x+1）-x3-x2+x+1
x4+x3+x2+2x+1=-x（-x3-x2+x+1）+（2x2+3x+1）
-x3-x2+x+1=
1
2
x（2x2+3x+1）+
3x3
44
843x3
3344
因此（f（x）,g（x））=x+1
2、求有理数域上多项式的最大公因式（f（x）,g（x）），并计算u（x）,v（x），使得
（f（x）,g（x））=u（x）f（x）+v（x）g（x），其中
f（x）=x5+x3+x2+1,
g（x）=x4+x2+x-1.
答：
由列表法可求出（f（x）,g（x））的公因子及相应系数组合，如表5所示：
表5求（f（x）,g（x））的公因子及相应的系数组合
u（x）
v（x）
q+
2x2+3x+1=（x+）（
+）=（2x+1）（x+1）
x5+x3+x2+1
1
0
x4+x2+x-1
x+1
0
1
1
-x
x
x3-x2+2x-1
0
因此（f（x）,g（x））=x+1=
（1）（x5+x3+x2+1）+（-x）（x4+x2+x-1）
m（x）=1
v（x）=-x
3、求二元域上多项式的最大公因式（f（x）,g（x）），其中
f（x）=x5+x3+x2+1,
g（x）=x4+x2+1.
答：
用辗转相除法计算如下
x5+x3+x2+1=x（x4+x2+1）+x2+x+1
x4+x2+1=（x2+x+1）（x2+x+1）
因此（f（x）,g（x））=x2+x+1
4、f（x）,g（x）?
F2[x]且有
f（x）=x6+x5+x4+x3,
g（x）=x5+x2+x+1.
求m（x）和n（x），使得（f（x）,g（x））=m（x）f（x）+g（x）n（x）。
答：
由列表法可求出（f（x）,g（x））的公因子及相应系数组合，如表6所示：
表6求（f（x）,g（x））的公因子及相应的系数组合
u（x）
v（x）
q
x6+x5+x4+x3
1
0
x5+x2+x+1
0
1
x+1
x4+1
x2+1
1
x
x+1
x2+x+1
x
x2+1
0
因此（f（x）,g（x））=x2+1=x（x6+x5+x4+x3）+（x2+x+1）（x5+x2+x+1）
m（x）=x
v（x）=x2+x+1
5.求有理数域上多项式的最大公因式（f（x）,g（x）），其中
f（x）=x5+x4+x2+2x+1,
g（x）=x4+x3+x2+2x+1.
答：
（f（x）,g（x））=x+1。
6.求有理数域上多项式的最大公因式（f（x）,g（x）），并计算u（x）,v（x），使得
（f（x）,g（x））=u（x）f（x）+v（x）g（x），其中
f（x）=x5+x3+x2+1,
g（x）=x4+x2+x-1.
答：
x+1=f（x）-xg（x）。
三、标准分解和最小公倍数
1.[288，392]＝14112
。
2．12600的标准分解式是_
2332527
。
3.547是_
___.（填“素数”或“合数”）。
3528的标准分解式是_2^3*3^2*7^2___。
4.计算以下数组的最小公倍数。
（1）[1046,697]
（2）[20301044]
（3）[195,72,90]
（4）[2104,2720,1046]，
解：
（1）由第2题计算得（1046,697）=1，因此[1046,697]=1046?
697=729062。
（2）由第2题计算得（20301044）=58，因此[20301044]=2030?
1044?
58=36540。
（3）由辗转相除法可计算得（195,72,90）=3，因此
[195,72,90]=195?
72?
90?
3=4680
（4）由第3题计算得（2104,2720,1046）=2，因此
[2104,2720,1046]=2104?
2720?
1046?
2=374133280。
5.求正整数a,b，使得a+b=120,（a,b）=24,[a,b]=144。
答：
由a+b=120及ab=（a,b）[a,b]=24?
144=3456解得a=48b,=
a=72,b=48。
6.设a,b是正整数，证明：
（a+b）[a,b]=a[b,a+b]。
7或2
答：
只须证（a+b）
abb（a+b）
（a,b）（b,a+b）
，即只须证（b,a+b）=（a,b）此式显然。
7.写出下列数的的标准分解式。
（1）
22345680
（2）166896912
（3）22345680
解：
（1）
22345680=24?
3?
5?
7?
47?
283。
4
4
8.判断561与967是否为素数。
解：
由3|561，所以561不是素数，由2,3,
是素数。
967
，，
=a
（2）166896912=2?
3?
7?
13?
19?
2011。
（3）22345680=2?
3?
5?
7?
47?
283。
殛都不能整除967，所以967
四、其他类型题
1.证明：
若m-p?
mn+pq，则m-p?
mq+np。
答：
由恒等式mq+np=（mn+pq）-（m-p）（n-q）及条件m-p?
mn+pq可
知m-p?
mq+np。
2.证明：
任意给定的连续39个自然数，其中至少存在一个自然数，使得这个
自然数的数字和能被11整除。
答：
在给定的连续39个自然数的前20个数中，存在两个自然数，它们的个
位数字是0，其中必有一个的十位数字不是9，记这个数为a，它的数字和为s，
则a,a+1,L,a+9,a+19的数字和为s,s+1,L,s+9,s+10，其中必有一个能
被11整除。
3.设a，b是正整数，证明：
（a+b）[a,b]=a[b,a+b]。
答：
只
升级会员 