首页>电子书>安全与解密>信息安全数学基础(许春香)_信息安全数学基础许春香,信息安全数学基础

信息安全数学基础(许春香)_信息安全数学基础许春香,信息安全数学基础

e21303  在  2021-01-11 14:07:04  上传  3.58 MB 信息安全数学基础许春香
内容:整数与同余,群,循环群和群的结构,环、多项式环与有限域,同余式,平方剩余,原根与离散对数。共8个章节,130余页。
信息安全技术的核心是容码学,信息安全数学基础是学习客码学所必需的数学基础知
识,包括近世代数和初等数论。由于信息安全技术在现代社会的快速发展和广泛应用,信息
安全数学基础也得到了普遍重视。
信宸安全数学基础包含的都是抽象的数学内容,它概多,结论(定理)多,而且概念
般都没有物理意义,这对习惯微积分等物理意义明确的数学课程的工科读者来说是一个挑
战。我们编骂本书时只选取最基本、最必需的内容,力图使用简单清晰的语言,使之尽量符
合工科数学课程的风格。我们认为,只要反复研习,再抽象的内容也能变得具体起来,变得
容易把握。
近世代数与初等数论本来是两门课程,以前只为数学专业开设,一般是在学习近世代数
之煎学习数论,把数论作为学习近世代数的基础课程。信息安全数学基础把它们融合成-门
课程,这就存在它们能不能够融合和怎么融合两个问题。近世代数与初等数论是相关性很强
的两门课程,例如,整除与同余既是数论的开端,也是近世代数的先导预备知识。再如,某
些结论(费马定理等)既可由近世代数导出,也可由数论导出,因此这两门课程的融合是可
能的,而且融合也是它们共同作为信息安全技术数学基础的客观需要。因为对于信息安全技
术领域的读者来说,分别完整学习近世代数和初等数论两门课程内容显得过多,耗时耗力
没有必要,而在一门课程里同时包会近世代数和初等数论中的少要内容,既满足要求,又高
效实用。
如何融合近世代数和初等数论?我们有两种选择:第一,按传统的思路,先引入数论
再引入近世代数,在了解剩余类、剩余系、原根等概念的基础上学习近世代数的群、环、域。
第二,先引入近世代数,再弓入数论,先建立群、环、域的框架,再在此基础上学习数论
尽置将数论的内容纳入群、环、的框架中。这两种选择各有其合理之处。数论先于近世代
数发展起来,因此前者符合其自然发屐过程。数论的很好掌握也有助于近世代数的学习。而
后者的融合性好,将两部分内容汇合成一个整体,很好地克服了前者数论和代数“两张皮”
的不足。此外,第一个选择在数论部分结束时开始近世代数部分,代数部分概念多且抽象
内容已经过半,而与之前联系不紧密的新概念突然如潮涌来,这很不符合一般学习习惯。数
论部分概念相对少一些,而且易于理解,因此放在后面更有利于读者学习。需要指出的是
当把近世代数和初等数论作为独立课程学习时,初等数论作为先导课程学习要更为合理
我们在编写本书的过程中采取的是第二种选择,即先建立群、环、城的框架,再引入数
论。在数论部分,我们尽量将群、环、域的结论应用到数论之中。例如,由群的结论直接得
到欧拉定理等,但为了使读者从多个角度更好地理解,我们同时也给出了数论的直接描述。
实际上本书只是我们在讲授信忌安全数学基础课程经验基础上的一个尝试,如何编写出符合

信息安全技术发展需求的信忠安全数学基础教材仍然是一个值得探讨的课题。
建议读者在通过本书学习信息安全数学基础时把握好以同余为基石的脉络:同余剩
余类(群)—剩余类环—一剩余系(特别是简化剩余系)一同余式,这条脉络尽管不能
认为是本书的主线,但可以串起本书的大部分核心内容,把握好它对于从总体上掌握好该门
课程非常有帮助。
本书可作为信息安全专业本科生、研究牛教材,还可以供信息安全技术领域科研人员参
考。
笔者衷心感谢我国著名的怒码学专家肖国镇教授,是他把笔者带入密码学领域,笔者今
天才能够进行本书的编写工作。同时衷心感谢郝玉洁老师和曾艺老师,没有她们的大力推动
本书不可能呈现在读者面前最后衷心感谢电子科技大学计算机学院领导和同事们在信息安
全数学基础教学和本书编写中绐予的支持和帮助。
许春香周俊辉
2008.1

y

第1章整除与同余
1.1整除.
,2
1.2素数...
13同余
ah口“
习题.
13
第2章群
2.1群的定义…
甲·甲香·日甲日『·『甲要甲甲。伊翻
22子群…
●曹看省中·晋首即。即
导垂即早国『司q票
21
23同构和同态…
23
24变换群与置换群………
28
习题
自自··。自·b手P自自自自。中非
34
第3章循环群、群的结构
31循环群
38
32剩余类群
42
3.3子群的陪集.
43
3.4正规了群、商群.
习题…
p
自非自·
第4章环
4.1环与子环
….52
42整环、除环、域…...-….
5
4.3环的同态、理想
57
44商环、素理想和最大理想
习题
●bP■
5
第5章多项式环与有限域
5.1多项式环
、4自曲。·
70
5.2多项式剩余类坏
74
53有限域
76
习题.
79
第6章同余式
6.1剩余系
82
62同余式概念与一次同余式
司,『中l。中鲁由a罪●44司自看P;看甲D■1鲁申,b。。。垂面甲看4司·哥卡D导命·。D司●
88

63中国剩余定理
64素数模同余式
…,95
以题.
99
第7章平方剩余
7.1平方剩余
…104
7.2勒让德符号
108
73雅可比符号
…………,14
习题
117
第8章原根与离散对数
8.1指数与原根
122
8.2原根的存在性.
中q。甲甲『旷。即切中即■·即甲目下矿目曾·”甲即即冒。冒曾『下下非即v日即餐冒甲目
聊■q日■■甲甲冒看
127
83离散对数…
129
习题
‘···4·····自···4····
132
参考文献…
133

inforM

整除与同余

整除和同佘是学习后面章节的基础.整除、素数等概念在初等数学中就曾经涉及,但我
们这里要进行更加系统和深入的讨论
○1.1整除
定义1设a,b是任意两个整数,其中b40,如果存在一个整数q,使a=φb,则我们
称b整除a,或a被b整除,记为ba,此时称b是a的因子,a是b的倍数
例12|10,10100.
例2设a是整数,a≠0,则a|0
整除有下列基本性质:
1)如果ba且ab,则b=a或b=-a
(2)如果ab且bc,则ac
(3)如果c|a且cb,则cwa+vb,其中l,ν是整数
证明:(1)因为ba,则存在整数q,使
a=g1b
又因为ab,则存在整数q2,使
b
=4
购贴于是
狼就都
a=q16=9291a,
解所以我们有q291=1,由于q,q2是整数,则
液彩
q2=41
或④=q1=-1

b=a或b
(2)因为ab,则存在整数q,使
b= gia
又因为bc,则存在整数q2,使
C
于是
b=4
其中q=q1q2
故a|c
(3)仿照(1)、(2)的证明很容易证得
当两个整数不能整除时,我们有带余除法:
对于a,b两个整数,其中b≠0,则
霎r称为a被b除得到的余数显然当厂=0时,6
a=bgtr, 0
例3(1)a=-37,b=5,则
37=(-8)5+3,r=3.

(2)a=41,b=-5,则

41=(-8)×(-5)+1,r=1.
定义2(1)设a,b是两个整数,如果整数c|a且c|b,则c称为a,b的公因子
(2)设c>0是两个不全为零的整数a,b的公因子,如果a,b的任何公因子都整除
则c称为a,b的最大公因子,记为c=(4,b)
由最大公因子的定义立即有:
(a,b)=(-a,b=(a,-b)=(-a,-b
例42,5,10是20,30的公因子.20,30的最大公因子(20,30)=10
求最大公因子的一般方法是使用下面的欧几里得除法(又称辗转相除法).
设a,b是两个正整数,记r=a,n=b,于是我们有:
f=4t1+r2,0≤
q22+r3,0≤
耗素额
In-2=9n-Irn-1+In,0 s In < rn-I
rn-1=qnr
(a, 6)
欧几里得除法的原理如下:
由上述除法过程可看出,rn整除rn-1,rn2,…,r2,η1,r,所以rn是a,b的公因子

如果d是a,b的任意公因子,从上面除法的第一行向下可以看出,d整除ro,n1,则d
整除r2
n-2,/n-1
故rn是最大公因
(a, b

例5(1)a=888,b=312,求(a,b)

(2)a=-3824,b=1837,求(a,b)


解:①
888=2×312+264

312=1×264+48
264=5×48+24
48=2×24
故(888,312)=24
-3824,1837)=(3824,1837)
824=2×1837+150
1837=12×150+37
150=4×37+2
37=18×2+1
得(3824,1837)=1,故(-3824,183
定理1设4,b是两个不全为零的整数,则存在两个整数v,v,使
(a, b=ua+vb
证明:设Z是全体整数集合.做一个如下集合:

rat
ZI
S中的元素显然大于等于0
设d是S中的最小正整数,则d可表示为a,b的组合,没
d=ua+vb
现在我们证明d|a且dlb
做带余除法
a=q+r,0≤
于是
a-gd=a-qlua+vb)=(1-qu)a-yvb
这说明r也可表示为a,b的组合,则r∈S.由于d是S中的最小正整数,所以只有
0.故dla.同理dlb
设c是a,b的任意公因子,由cla和cb得c|d=a+.故d是a,b的最大公因子,
证毕
定理1表明a,b的最大公因子可以表示为a,b的组合.实际上,从欧几里得除法求最
大公因子的过程也可以看出(a,b可表示为a,b的组合
可表示为r
b的组
y3可表示为r1,r2的组合,
rn可表示为r2=1,rn2的组合,
所以mn=(a,b)可表示为a,b的组合
例6将a=888,b=312的最大公因子表示为(a,b)=a+vb
解利用欧几里得除法求最大公因子的过程可以解出

888=2×312+264
312=1×264+48
264=5×48+24
我们有
264888-2×312
48=312-264=312-(888-2×312)=-888+3×312
24=264-5×48=(888-2×312)-5×(-888+3×312)=6×888-17×312
故(888,312)=24=6X888-17×312
定义3设a,b是两个不全为0的整数,如果(a,b)=1,则称a,b互素
推论a,b素的充分必要条件是:存在M,ν,使
a+v=1
信息安全数学基础
证阴:必要条件是定理1的特例,只需讦充分条件
如果存在M,v,使
a+w=1
则由(a,b)
(ua+vb),
得(a,b)1,所以(a,b)=1
例7由例5知a=-3824,b=1837互素,求u,ν,使wa+w=1
我要下载
意见反馈 联系客服 返回顶部

登录注册找回密码

Vaptcha启动中...

Vaptcha启动中...

充值账单订单冲正

*扫码按套餐金额一次性付款立即点击“确认”按钮

*充值提示成功,请重新登录账户生效

*充值问题联系Q或邮箱最迟24小时内答复

*充值问题先尝试【订单冲正】自助解决

*无法解决Q421644184或Q邮箱,支付宝订单平台账号

*推荐用chrome浏览器访问本站,禁用360浏览器

啥都没有哦

*输入正确支付宝订单号,2021开头的,点“确认”按钮

*有疑问请及时联系Q 421644184或此Q对应的邮箱

*提供支付宝支付订单号截图及平台用户名

*推荐用chrome浏览器访问本站,禁用360浏览器

在线咨询 x
如果您有任何疑问
点击咨询