《密码学数学基础》习题集.docx
《《密码学数学基础》习题集.docx》由会员分享,可在线阅读,更多相关《《密码学数学基础》习题集.docx(155页珍藏版)》请在冰点文库上搜索。
《密码学数学基础》习题集
北京电子科技学院
《密码学数学基础》习题集
信息安全系密码教研室
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)10461697349
6971349348
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)
μ(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.
求μ(x)和ν(x),使得(f(x),g(x))=μ(x)f(x)+g(x)ν(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)
μ(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,,a+9,a+19的数字和为s,s+1,,s+9,s+10,其中必有一个能
被11整除。
3.设a,b是正整数,证明:
(a+b)[a,b]=a[b,a+b]。
答:
只须证(a+b)
ab
(a,b)
=a
b(a+b)
(b,a+b)
,即只须证(b,
a+b)=(a,b),此式显然。
4.求正整数a,b,使得a+b=120,(a,b)=24,[a,b]=144。
答:
由a+b=120及ab=(a,b)[a,b]=24⨯144=3456解得a=48,b=72
或a=72,b=48。
5.计算2050与3768的二进制表示和十六进制表示。
解:
2050的二进制表示:
2050=(100000000010)2
2050的十六进制表示:
2050=(802)16
3768的二进制表示:
3768=(111010111000)2
3768的十六进制表示:
3768=(EB8)16
6.证明6|n(n+1)(2n+1),其中n为任意整数。
证明:
n(n+1)(2n+1)=n(n+1)(n-1+n+2)=(n-1)n(n+1)+n(n+1)(n+2);
(n-1),n,(n+1)是连续三个整数,