密码学基础群 (循环群,生成元)

格式：ppt
大小：237.00 KB
文档页数：46

下载文档原格式

密码学基础群-(循环群-生成元)

19岁时,他解决了一个让一些著名数学家烦脑了数百年的难题.
他证明了虽然一元二次、三次甚至四次方程都有求根公式, 但是对于一般的五次方程却不存在这样的求根公式.
他对于五次方程求解问题的解决为近世代数的创立做出了基础性的工作.
29
此外, 阿贝尔还在椭圆函数论、椭圆积分、阿贝尔积分和无穷级数等方面做出过杰出的贡献.
16
元素a的阶如下
a
1
2
3
4
a的阶
1
4
4
2
17
例7 计算群(Z6, ⊕)每个元素的阶, Z6={0,1,2,3,4,5}. 解:对于a=2, 有 1×2=2, 2×2=2⊕2=4, 3×2=2⊕2⊕2=6=0. ∴ ord 2=3.
a
0
1
2
3
4
5
Ord a 1
6
3
2
3
6
18
设G是一个群, 如果存在a∈G, 使得 G={a1, a2,…}=<a>, 则称G是一个循环群(cyclic group), 并称a是
5
有时把交换群(G, ∗)记为(G, +), 称为“加群”.
✓ 把运算“∗”称为“加” 法, 运算结果记为: a∗b= a+b,称为a与b的“和”;
✓ 单位元称为“零元”, 记为“0”; ✓ a∈G的逆元称为G的负元,记为: “- a”, 即
有a+(-a)= 0.
6
例1 G={1, -1, i, -i}, (G, *)是一个有限交换群. 可记为: (G, *)= (G, +), 运算式为: 1+(-1)=-1, 1+i=i, 1+(-i)=-i, (-1)+i=-i, (-1)+(i)=i, i+(-i)=1, 1+1=1

密码学中的数学原理

密码学中的数学原理密码学是研究如何在通信过程中保护信息安全的学科，它涉及到许多数学原理和算法。

在密码学中，数学原理起着至关重要的作用，它们为加密和解密提供了坚实的理论基础。

本文将介绍密码学中一些重要的数学原理，包括模运算、RSA算法、离散对数问题等。

一、模运算模运算是密码学中常用的数学运算之一，它在加密算法中扮演着重要的角色。

在模运算中，我们需要计算一个数除以另一个数的余数。

例如，对于整数a和b，a mod b的结果就是a除以b的余数。

模运算在密码学中广泛应用于数据加密和密钥生成过程中，能够保证数据的安全性和可靠性。

二、RSA算法RSA算法是一种非对称加密算法，它是基于大数分解的数学原理。

RSA算法的安全性建立在两个大素数相乘的难解性上。

在RSA算法中，用户生成一对公钥和私钥，公钥用于加密数据，私钥用于解密数据。

RSA算法被广泛应用于数字签名、数据加密等领域，是当前最常用的加密算法之一。

三、离散对数问题离散对数问题是密码学中的一个重要数学难题，它是许多加密算法的基础。

在离散对数问题中，给定一个素数p、一个整数a和一个整数b，要求找到满足a^x ≡ b (mod p)的x值。

离散对数问题的难解性保证了许多加密算法的安全性，如Diffie-Hellman密钥交换算法和椭圆曲线密码算法等。

四、椭圆曲线密码算法椭圆曲线密码算法是一种基于椭圆曲线数学原理的加密算法，它具有高效性和强安全性的特点。

椭圆曲线密码算法利用椭圆曲线上的点运算来实现数据加密和数字签名，被广泛应用于移动通信、物联网等领域。

椭圆曲线密码算法是当前密码学领域研究的热点之一，具有很高的研究和应用价值。

五、费马小定理费马小定理是密码学中常用的数学原理之一，它可以用来验证素数和进行模幂运算。

费马小定理表明，对于任意素数p和整数a，a^(p-1) ≡ 1 (mod p)。

费马小定理在RSA算法、Miller-Rabin素性测试等算法中发挥着重要作用，是密码学中不可或缺的数学工具之一。

信息安全专业密码学课程体系的建设

第 3 期2018 年 3 月 10 日计算机教育Computer Education中图分类号：G642124文章编号：1672-5913(2018)03-0124-04信息安全专业密码学课程体系的建设侍伟敏，周艺华，杨宇光，姜楠（北京工业大学计算机学院，北京 100142）摘要：密码学课程体系的建设是信息安全专业密码学教学科研工作的核心和基础。

文章针对目前信息安全专业密码学课程体系存在的不足，并根据各门密码类具体课程的定位及前修后续关系，提出从密码学基础、密码学算法、密码学应用和密码学实践4个不同层面开设相关密码课程，为信息安全专业密码学课程体系提出一些建议。

关键词：信息安全；密码学；课程体系0 引言随着互联网的快速发展，信息安全日益受到重视，特别是斯诺登事件之后，世界各国更是加强了信息安全的建设工作[1]。

国内有80多个高校开设了信息安全本科专业，北京工业大学信息安全专业以计算机科学与技术一级学科、信息安全北京市重点（交叉）学科为支撑学科，以“卓越工程师培养计划”[2]为目标进行信息安全本科专业人才的培养。

密码学是信息安全专业的基础课程，它是研究密码学编码和密码学分析的综合性应用科学，是保证信息系统的保密性、认证性、完整性和不可否认性等属性的重要工具[3-4]。

其中，各种加密和认证技术是实现网络安全环境中如电子政务和电子商务等系统的必要手段[5]。

然而，作为信息安全专业重要的基础课程，密码学的课程体系建设是否完善直接影响后续专业课程的教学质量和学生对信息安全专业的整体把握。

1 密码学课程体系存在的问题目前北京工业大学信息安全专业仅开设密码学数学基础课程和密码学课程，要想构建完善的密码学课程体系还存在以下不足。

1）密码学数学基础课程开设少。

密码学涉及丰富的数学知识，主要包括代数、组合论、初等数论、概率论、随机过程、图论、数理统计、信息论、计算复杂性等[6]。

目前信息安全专业仅开设了高等数学、线性代数、概率论与数理统计、集合与图论课程，而对于公钥密码算法涉及的群、环、域，椭圆曲线，格运算等内容都没有包含，因此，需要开设相应的课程来弥补以上内容。

第二章密码学基础

2020/3/18
15
三、密码分析
截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。
密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。
2020/3/18
第二章：密码学基础
一、密码学的基本概念二、密码体制分类三、密码分析
2020/3/18
1
一、密码学的基本概念
密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支，
密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问
密码分析学(Cryptanalytics)，研究分析破译密码的学问。
2020/3/18
5
保密系统模型
搭线信道（主动攻击）非法接入者
C’
搭线信道（被动攻击）
m‘
密码分析员
信源
m
加密器
M
c Ek1 (m)
解密器
m
m Dk2 (c)
接收者
k1
密钥源 K1
密钥信道
k2
密钥源 K2
2020/3/18
6
保密系统应当满足的要求
系统即使达不到理论上是不可破的，即
pr{m’=m}=0，也应当为实际上不可破的。就是说，
2020/3/18
8
安全认证系统应满足下述条件
意定的接收者能够检验和证实消息的合法性和真实性。
消息的发送者对所发送的消息不能抵赖。
除了合法消息发送者外，其它人不能伪造合法的消息。
而且在已知合法密文c和相应消息m下，要确定加密密

公钥密码学中的三大难解数学问题

公钥密码学中的三⼤难解数学问题1.⼤整数因数分解问题Ⅰ）给定两个素数p,q,计算乘积p·q=n很容易；Ⅱ）给定⼤整数n，求n的素因素p,q使得n=p·q⾮常困难.例1p=20000000000000002559,q=80000000000000001239是两个安全素数，它们的乘积n=p·q=160000000000000229500000000000003170601.但要分解这个n⾮常困难.2.离散对数问题已知有限循环群G={g∧k∣k=0,1,2,...}及其⽣成元g和阶n=∣G∣.Ⅰ）给定整数a，计算元素g∧a=h很容易；Ⅱ）给定元素h，计算整数x，0≤x≤n,使得g∧x=h⾮常困难.例2 p=12000000000000002559是⼀个安全素数，F_p=Z/pZ是⼀个有限域，F*_p=F_p\{0}是⼀个乘法循环群，其⽣成元g=11.给定整数a=2030428,可以快速计算g∧a≡1134889584997235257（modp）.但要求整数x，使得g∧x≡1134889584997235257⾮常困难.3.椭圆曲线离散对数问题已知有限域F_p上的椭圆曲线点群E(F_p)={(x,y)∈F_p×F_p∣y²=x³+ax+b,a,b∈F_p}∪{O}，点P=(x,y)的阶为⼀个⼤素数.Ⅰ）给定整数a，计算整数x，使得xP=(x_a,y_a)=Q很容易；Ⅱ）给定点Q，计算整数x，使得xP=Q⾮常困难.例3 P=10823是⼀个素数，有限域F_p=Z/pZ上的椭圆曲线点群E(F_p)={(x,y)∈F_p×F_p∣y²=x³+3x+7}∪{O}，∣E(F_p)∣=100482=2·3·16747.E(F_p)的⽣成元为P_0=(1,8811).点P=6P_0=(62046,14962)的阶为素数16747.Ⅰ)给定a=1007，计算aP=(80726,17229)=Q很容易；Ⅱ）给定点Q=(80726,17229)，求整数x使得xP=Q很困难.摘⾃陈恭亮《简明信息安全数学基础》（⾼等教育出版社）——摘⾃陈恭亮《简明信息安全数学基础》。

密码学数学基础第六讲群(1)

例2 在群< Z , + >中，
30 = 0
在群 < Z3 , ⊕ >中，
20 = 0 23 = 2 ⊕ 2 ⊕ 2 = 0
2−3 = (2−1 )3 = 13 = 0
35 = 3 + 3 + 3 + 3 + 3 = 15
3−5 = (3−1 )5 = (−3)5 = −15
定理1 中的幂运算性质如下：定理群<G，*>中的幂运算性质如下：，中的幂运算性质如下
四、子群及其如果H关于的非空子集，定义设<G，*>为群，H是G的非空子集，如果关于，为群 G中的运算构成群，则称是G的子群，记作 H ≤ G。若H 中的运算*构成群的子群，中的运算构成群，则称H是的子群的子群，的真子集，的真子群，是G的子群，且是的真子集，则称是G的真子群，记的子群且是G的真子集则称H是的真子群作H < G 。例1 的子群。 nZ = {nZ | n ∈ N }是整数加群 < Z , + > 的子群。的真子群。当 n ≠ 1 时，nZ是Z的真子群。是的真子群定义2 也是G的子群的平凡子群。定义 G和{e}也是的子群，称为的平凡子群。和也是的子群，称为G的平凡子群
定理2 为群， ∈ ，是整数，定理设<G，*>为群，a∈G，且|a|＝r。设k是整数，，为群＝。是整数当且仅当r|k。则 a k = e当且仅当。定理3 为群，与其逆元a 定理设< G，*>为群，则群中任何元素与其逆元 -1具，为群则群中任何元素a与其逆元有相同的阶。有相同的阶。

数学中的群论与抽象代数知识点

数学中的群论与抽象代数知识点引言：数学是一门广阔而深奥的学科，其中群论与抽象代数作为数学的重要分支，对于理解和研究其他数学领域具有重要的作用。

本文将介绍群论与抽象代数的基本概念、性质以及其在数学中的应用。

一、群论与抽象代数的基本概念1. 群的定义群是一个集合，具有二元运算和满足一定条件的性质。

群的定义包括封闭性、结合律、单位元、逆元等关键概念。

2. 子群子群是一个群的子集，并且保持了群的运算和性质。

子群具有封闭性、单位元、逆元等性质。

3. 循环群循环群是由一个元素生成的群，这个元素称为生成元。

循环群具有特殊的结构和性质。

4. 交换群交换群，又称为阿贝尔群，其群运算满足交换律。

交换群在数学和物理领域的应用非常广泛。

二、群的基本性质与定理1. 基本性质群具有封闭性、结合律、单位元和逆元的性质。

这些性质使得群成为一个有序的代数结构。

2. 拓展性质群的运算满足取消律、唯一性和可乘性等性质，这些性质进一步扩展了群的应用范围。

3. 拉格朗日定理拉格朗日定理是群论中的重要定理，它确定了子群与群的阶之间的关系，并具有广泛的应用。

4. 加法群与乘法群加法群是指群的二元运算为加法，乘法群是指群的二元运算为乘法。

加法群和乘法群在不同的数学分支中有不同的应用。

三、抽象代数的应用领域1. 数论数论是研究整数性质和整数运算的数学分支，群论与抽象代数在数论中有着广泛的应用，如素数分布、同余关系等。

2. 几何学几何学研究空间中的形状、结构和变换，抽象代数可以用来描述和研究几何中的对称性、平移、旋转等。

3. 计算机科学计算机科学中的密码学、编码理论等领域，都离不开群论和抽象代数的基础概念和方法。

结论：群论与抽象代数作为数学的重要分支，对于理解和研究其他数学领域具有重要的作用。

本文介绍了群论与抽象代数的基本概念、性质及在数学中的应用。

深入学习和理解群论与抽象代数的知识，能够帮助我们更好地理解和应用数学。

随着数学研究的不断深入，群论与抽象代数的作用与意义还将继续扩展和发展。

应用密码学习题答案4

《应用密码学》习题和思考题答案第4章密码学数学引论4－1 编写一个程序找出100~200间的素数。

略4－2 计算下列数值：7503mod81、(－7503)mod81、81mod7503、(－81)mod7503。

解：7503mod81＝51(－7503)mod81＝3081mod7503＝81(－81)mod7503＝74224－3 证明：（1）[]))(m od (m od )(m od )(m od m b a m m b m a ⨯=⨯（2）[][])(m od ))(m od ())(m od (m od )(m m c a m b a m c b a ⨯+⨯=+⨯证明：（1）设(mod )a a m r =，(mod )b b m r =，则a a r jm =+（j 为某一整数），b b r km =+（k 为某一整数）。

于是有：[](mod )(mod )mod ()(mod )a b a m b m m r r m ⨯=()()()()()()()2()(mod )mod mod mod a b a b a b a b a b m r jm r km m r r r km r jm kjm m r r m ⨯=++=+++= 于是有：[]))(m od (m od )(m od )(m od m b a m m b m a ⨯=⨯（2）设(mod )a a m r =，(mod )b b m r =，(mod )c c m r =，则a a r jm =+（j 为某一整数），b b r km =+（k 为某一整数），c c r im =+（i 为某一整数）。

于是有：[]()()()()[]()()22()mod (mod )(mod )mod mod a b c a b c a b a a a c b c a b a c a b c m r jm r km r im m r jm r km r im m r r r im r km r r r jm kjm r jm ijm m r r r r m⎡⎤⨯+=++++⎡⎤⎣⎦⎣⎦⎡⎤=++++⎣⎦=+++++++=+[]()()()()()[]()(mod )()(mod )(mod )mod mod mod mod a b a c a b a c a b m a c m m r jm r km m r jm r im m m r r r r m⨯+⨯=+++++⎡⎤⎣⎦=+于是有：[][])(m od ))(m od ())(m od (m od )(m m c a m b a m c b a ⨯+⨯=+⨯4－4 编写一个程序，用扩展的欧几里德算法求gcd(4655,12075)和550－1mod1723。

密码习题及部分参考答案..

一、密码学概述部分：1、什么是密码体制的五元组。

五元组（M,C,K,E,D）构成密码体制模型，M代表明文空间；C代表密文空间；K代表密钥空间；E代表加密算法；D 代表解密算法2、简述口令和密码的区别。

密码：按特定法则编成，用以对通信双方的信息进行明、密变换的符号。

换而言之，密码是隐蔽了真实内容的符号序列。

就是把用公开的、标准的信息编码表示的信息通过一种变换手段，将其变为除通信双方以外其他人所不能读懂的信息编码，这种独特的信息编码就是密码。

口令：是与用户名对应的，用来验证是否拥有该用户名对应的权限。

密码是指为了保护某种文本或口令,采用特定的加密算法,产生新的文本或字符串。

区别：从它们的定义上容易看出；当前，无论是计算机用户，还是一个银行的户头，都是用口令保护的，通过口令来验证用户的身份。

在网络上，使用户口令来验证用户的身份成了一种基本的手段。

3、密码学的分类标准：⏹按操作方式可分为：替代、置换、复合操作⏹按使用密钥的数量可分为：对称密钥（单密钥）、公开密钥（双秘钥）⏹按对明文的处理方法可分为：流密码、分组密码4、简述柯克霍夫斯原则（及其特点和意义。

？）即使密码系统中的算法为密码分析者所知，也难以从截获的密文推导出明文或密钥。

也就是说，密码体制的安全性仅应依赖于对密钥的保密，而不应依赖于对算法的保密。

只有在假设攻击者对密码算法有充分的研究，并且拥有足够的计算资源的情况下仍然安全的密码才是安全的密码系统。

一句话：“一切秘密寓于密钥之中”Kerckhoffs原则的意义：⏹知道算法的人可能不再可靠⏹设计者有个人爱好⏹频繁更换密钥是可能的，但无法频繁更换密码算法（设计安全的密码算法困难）5、密码攻击者攻击密码体制的方法有三种分别是：⏹穷举：尝试所有密钥进行破译。

（增大密钥的数量）⏹统计分析：分析密文和明文的统计规律进行破译。

（使明文和密文的统计规律不一样）⏹解密变换：针对加密变换的数学基础，通过数学求解找到解密变换。

应用密码学习题答案

第4章密码学数学引论4－1 编写一个程序找出100~200间的素数。

略4－2 计算下列数值：7503mod81、(－7503)mod81、81mod7503、(－81)mod7503。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

20
特别地: 取m=6, Z6={0,1,2,3,4,5}的生成元有: 1, 5. 1×5=5, 2×5=10=4, 3×5=15=3, 4×5=20=2, 5×5=25=1, 6×5=30=0.
∴ Z6={0,1,2,3,4,5}={6×5, 5×5, 4×5, 3×5, 2×5, 1×5}.
环R的元素a的加法逆元称为a负元, 记为-a. 注2: 如果环R的乘法还满足交换律, 则称R为
交换环.
32
注3: 如果环R中存在元素e, 使对任意的a∈R, 有 a∗e=e∗a=a,
则称R是一个有单位元的环, 并称e是R的乘法单位元(unit). 如果环R有单位元, 则R的单位元是唯一的. 环R 的乘法单位元记为e或1.
请问零元是？利用 a+e＝e+a=a 试求 (-i)+(-i), i+i, (-1)+(-1).
7
例2 加群: (Z5,⊕)=(Z5,+), 其中Z5={0,1,2,3,4}. 零元0=0,负元为:
元素x 0
1
2
3
4
负元-x 0
4
3
2
1
8
群的概念 ✓ 有时把群(G, ∗)记为(G, ⋅), 称为“ 乘群”. ✓ 把运算“∗”称为“乘” 法, 运算结果记为: a∗b=
37
定理 (1) 每个有限域的阶一定是素数的幂: pn. 含有pn个元素的有限域记为GF(pn). (2) 任给素数p 和正整数n, 一定存在阶为pn的有限
域. (3) 同阶的有限域是同构的. (4) 令GF(pn)*表示GF(pn)的全体非零元的集合, 则
GF(pn)*关于乘法是一个pn-1阶循环群.
成元的充分必要条件是:gcd(n, r)=1.
25
例10 求(Z12, ⊕)的全部生成元. 提示:1是一个生成元.
26
解:1是一个生成元. 满足gcd(12, r)=1的r : 1, 5, 7, 11. ∴ Z12的生成元有: 1×1=1, 5×1=5, 7×1=7,
11×1=11.
27
14
群元素的阶设G是一个群, e是G的单位元, a∈G, 如果
存在正整数r, 使得ar=e,则称a是有限阶的, 否则称a是无限阶的. 如果a是有限阶的, 则把满足ar=e的最小正整数r称为a的阶(order),记为ord a=r. 如果a是无限阶的, 则记ord a =∞.
15
计算群(Z5*, ⊗)每个元素的阶, Z5*={1,2,3,4}. 解：对于a=2, 有 21=2, 22=2⊗2=4, 23=2⊗2⊗2=8=3, 24=2⊗2⊗2⊗2=16=1. ∴ ord 2=4. 下面，请求出各元素的阶
∴ Z5*={1,2,3,4}={24, 21, 23, 22}. 请验证生成元3的情形
23
对于a=3, 有 31=3, 32=4, 33=2, 34=1. ∴ Z5*={1,2,3,4}={34, 33, 31, 32}.
24
循环群定理设G是一个n阶循环群, 则G恰有φ(n)
个生成元. 如果a是G的一个生成元, 则ar也是G的生
例: 整数加群(Z,+); 有理数加群(Q,+); 实数加群(R,+); 复数加群(C,+).
令Q*=Q-{0}, (Q*, ×)是群; Q+={q∈Q| q>0}, (Q+, ×)是群.
3
群的概念
例1 设G={1, -1, i, -i}, 则(G, ×) 是一个有限交换群.
元素a
1
-1
13
加群的倍数设(G, +)是一个加群, n∈Z+, a∈G的n倍为:
na= a+a+…+a (n个a) 0a =0, (-n)a =n(-a). 倍数法则: 设a,b∈G, n, m∈Z,则有 (1)na +ma =(n+m)a; (2) m(na) =(nm)a; (3) n(a+b) =na+nb.
33
注4: 设环R有单位元e, a∈R, 如果存在 b∈R,使a∗b=b∗a=e,
则称a是R的一个可逆元(invertible element), 并称b是a的逆元(inverseelement), 记为 b=a-1.
一个环中, 可能有些元素有逆元, 而其它元素没有逆元.
34
例4.1.2.1 整数环(Z, +, ×); 有理数环(Q,+, ×); 实数环(R,+, ×); 复数环(C,+,×).
5
有时把交换群(G, ∗)记为(G, +), 称为“加群”.
✓ 把运算“∗”称为“加” 法, 运算结果记为: a∗b= a+b,称为a与b的“和”;
✓ 单位元称为“零元”, 记为“0”; ✓ a∈G的逆元称为G的负元,记为: “- a”, 即
有a+(-a)= 0.
6
例1 G={1, -1, i, -i}, (G, *)是一个有限交换群. 可记为: (G, *)= (G, +), 运算式为: 1+(-1)=-1, 1+i=i, 1+(-i)=-i, (-1)+i=-i, (-1)+(i)=i, i+(-i)=1, 1+1=1
38
含有pn个元素的有限域只有一个. 当n=1时, GF(p)=(Zp, ⊕, ⊗)=Fp 称为素域.
39
伽罗瓦(É. Galois), 法国数学家, 1811年10月25 日出生于巴黎. 16岁开始自学勒让德、拉格朗日、高斯和柯西等大师的经典数学著作和论文. 18岁时, 他完成了第一篇代数方程的重要论文.
a∗b=b∗a=e. 则称G关于运算“∗”构成一个群(group), 记为(G, ∗).
1
注1: (G2)中的元素e 称为群G的单位元(unit element)或恒等元(identity). 群G的单位元是唯一的.
注2: (G3)中的元素b称为元素a的逆元(inverse). 元素a的逆元是唯一的,记为a-1. 即有a∗a-1=a-1∗a=e
1829年4月6日, 阿贝尔死于肺结核, 年仅27岁.
1872年, 若尔当(C.Jordan)引入了阿贝尔群这一术语, 以纪念这位英年早逝的天才数学家.
30
有限环
定义设R是一个非空集合. 如果在R上定义了两个代数运算, “+”(称为加法)和“∗” (称为乘法), 并且满足:
(R1) (R, +)构成一个交换群; (R2) 乘法结合律: 即对所有的a, b, c∈R, 有
16
元素a的阶如下
a
1
2
3
4
a的阶
1
4
4
2
17
例7 计算群(Z6, ⊕)每个元素的阶, Z6={0,1,2,3,4,5}. 解:对于a=2, 有 1×2=2, 2×2=2⊕2=4, 3×2=2⊕2⊕2=6=0. ∴ ord 2=3.
a
0
1
2
3
4
5
Ord a 1
6
3
2
3
6
18
设G是一个群, 如果存在a∈G, 使得 G={a1, a2,…}=<a>, 则称G是一个循环群(cyclic group), 并称a是
10
特别地: 取m=5, 有Z5*={1,2,3,4}, 1×1＝1 mod 5 所以1的逆元素是1 求出其他元素的逆元素
11
元素a的逆元
元素a
1
2
3
4
逆元a-1
1
3
2
4
12
群的幂设(G, ⋅)是一个群, n∈Z+, a∈G的n次幂为:
an = a⋅a⋅…⋅a (n个a) a0 =e, a-n =(a-1)n. 指数法则: 设a,b∈G, n, m∈Z,则有 (1) an⋅am= an+m; (2) (an)m =anm; (3) 如果G是一个交换群, 则(a⋅b)n= an⋅bn.
注意: 设p是素数, 则(Zp*, ⊗)是p-1阶循环群.
Zp*的生成元a称为Z的一个模p元根 (primitive root).
22
群(Z5*, ⊗)是4阶循环群, Z5*={1,2,3,4}. 生成元有: 2, 3. 解对于a=2, 有 21=2, 22=2⊗2=4, 23=2⊗2⊗2=8=3, 24=2⊗2⊗2⊗2=16=1.
求出循环群(Zp, ⊕)和(Zp*, ⊗)的全部生成元. 从每个群中取出一个生成元,把该群中的全部元素表示成生成元的倍数(或方幂) 的形式. 其中 (1) p=7; (2) p=13.
28
阿贝尔小传
阿贝尔(N. H. Abel)1802年8月5日出生于挪威.
16岁开始学习牛顿、欧拉、拉格朗日和高斯的经典数学著作.
(a∗b)∗c=a∗(b∗c); (R3) 乘法对加法的分配律:即对所有的a, b, c∈R, 有
a∗(b+c)=a∗b+a∗c, (b+c)∗a=b∗a+c∗a, 则称R关于运算“+”和“∗”构成一个环(ring), 记为(R,+, ∗).
31
注1: (R, +)是一个交换群, 称为R的加法群. 环R的加法单位元称为环的零元,记为0.
在1828年到1830年之间, 他得到了后来被称为 “伽罗瓦理论”的重要结论.
1832年5月30日,伽罗瓦由于政治和爱情的纠葛在决斗中被人射中,次日不幸去世,死时不满21 岁.
进一步, 如果F是有限集,则称(F,+, ∗) 是一个有限域(finite field), 也称为伽罗华域 (Galois field).

密码学基础群 (循环群,生成元)

合集下载