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

1、1,群的概念,定义 设g是一个非空集合, “”是g是上的一个代数运算, 即 对所有的a, bg, 有abg. 如果g的运算还满足: (g1)结合律:即对所有的a, b, cg, 有 (ab)c=a(bc)(g2) g中存在元素e, 使得对每个ag, 有 ea=ae=a (g3) 对g中每个元素a, 存在元素bg, 使得 ab=ba=e. 则称g“”构成一个群(group), 记为(g,2,注1: (g2)中的元素e 称为群g的单位元(unit element)或恒等元(identity). 群g的单位元是唯一的. 注2: (g3)中的元素b称为元素a的逆元(inverse).元素a的逆元是唯一

2、的,记为a-1. 即有aa-1=a-1a=e,3,有限群,交换群 如果群g的运算还满足: (g4)交换律:即对所有的a, bg, 有ab=ba. 则称g是一个交换群(commutative group),或阿贝尔群(abelian group). g中元素的个数称为群g的阶(order), 记为|g|. 如果|g|是有限数,则称g是有限群(finite group), 否则称g是无限群(infinite group). 例: 整数加群(z,+); 有理数加群(q,+); 实数加群(r,+); 复数加群(c,+). 令q*=q-0, (q*, )是群; q+=qq| q0, (q+, )是群,4

3、,群的概念 例1 设g=1, -1, i, -i, 则(g, ) 是一个有限交换群,5,例2 设mz+, zm=0,1, m-1, 则(zm, ) 是一个有限交换群. 称为模m剩余类加群. 单位元是e=0; azm的逆元a-1= m-a. 特别地: 取m=5, 有z5=0,1,2,3,4,6,有时把交换群(g, )记为(g, +), 称为“加群”. 把运算“”称为“加” 法, 运算结果记为: ab= a+b,称为a与b的“和”; 单位元称为“零元”, 记为“0”; ag的逆元称为g的负元,记为: “- a”, 即有a+(-a)= 0,7,例1 g=1, -1, i, -i, (g, *)是一个

4、有限交换群. 可记为: (g, *)= (g, +), 运算式为: 1+(-1)=-1, 1+i=i, 1+(-i)=-i, (-1)+i=-i, (-1)+(-i)=i, i+(-i)=1, 1+1=1 请问零元是？利用 a+ee+a=a 试求 (-i)+(-i), i+i, (-1)+(-1,8,例2 加群: (z5,)=(z5,+), 其中z5=0,1,2,3,4. 零元0=0,负元为,9,群的概念 有时把群(g, )记为(g, ), 称为“ 乘群”. 把运算“”称为“乘” 法, 运算结果记为: ab= ab, 称为a与b的“积”; 运算符号通常省略, 简记为: ab=ab=ab. 单位

5、元记为: e=1,10,例3 设mz+, zm=0,1, m-1, 则(zm, )不是一个群.元素0无逆元! 0?=1 找不到这样的元素！ 例4 设mz+是素数, zm*= 1,2,m-1, 则 (zm*, )是一个有限交换群. 单位元: e=1; azm的逆元a-1: aa-1=1 (mod m,11,特别地: 取m=5, 有z5*=1,2,3,4, 111 mod 5 所以1的逆元素是1 求出其他元素的逆元素,12,元素a的逆元,13,群的幂 设(g, )是一个群, nz+, ag的n次幂为: an = aaa (n个a) a0 =e, a-n =(a-1)n. 指数法则: 设a,bg,

6、n, mz,则有 (1) anam= an+m; (2) (an)m =anm; (3) 如果g是一个交换群, 则(ab)n= anbn,14,加群的倍数 设(g, +)是一个加群, nz+, ag的n倍为: na= a+a+a (n个a) 0a =0, (-n)a =n(-a). 倍数法则: 设a,bg, n, mz,则有 (1)na +ma =(n+m)a; (2) m(na) =(nm)a; (3) n(a+b) =na+nb,15,群元素的阶 设g是一个群, e是g的单位元, ag, 如果存在正整数r, 使得ar=e,则称a是有限阶的, 否则称a是无限阶的. 如果a是有限阶的, 则把满

7、足ar=e的最小正整数r称为a的阶(order),记为ord a=r. 如果a是无限阶的, 则记ord a,16,计算群(z5*, )每个元素的阶, z5*=1,2,3,4. 解：对于a=2, 有 21=2, 22=22=4, 23=222=8=3, 24=2222=16=1. ord 2=4. 下面，请求出各元素的阶,17,元素a的阶如下,18,例7 计算群(z6, )每个元素的阶, z6=0,1,2,3,4,5. 解:对于a=2, 有 12=2, 22=22=4, 32=222=6=0. ord 2=3,19,设g是一个群, 如果存在ag, 使得 g=a1, a2,=, 则称g是一个循环群

8、(cyclic group), 并称a是的一个生成元(generator). 如果g是一个n阶循环群, 则 g=a1, a2,an=. 提示:计算时请从a1开始,20,如果g是一个n阶循环群, 且元素ag 的阶= 群g的阶, 则a是g的一个生成元. 例8 设mz+, zm=0,1, m-1, 则(zm, ) 是m阶循环群.1是一个生成元,21,特别地: 取m=6, z6=0,1,2,3,4,5的生成元有: 1, 5. 15=5, 25=10=4, 35=15=3, 45=20=2, 55=25=1, 65=30=0. z6=0,1,2,3,4,5=65, 55, 45, 35, 25, 15.

9、 注意: 循环群的生成元不是唯一的,22,循环群 定理 设p是素数, 则(zp*, )是p-1阶循环群. zp*的生成元a称为z的一个模p元根(primitive root,23,群(z5*, )是4阶循环群, z5*=1,2,3,4. 生成元有: 2, 3. 解 对于a=2, 有 21=2, 22=22=4, 23=222=8=3, 24=2222=16=1. z5*=1,2,3,4=24, 21, 23, 22. 请验证生成元3的情形,24,对于a=3, 有 31=3, 32=4, 33=2, 34=1. z5*=1,2,3,4=34, 33, 31, 32,25,循环群 定理设g是一个n

10、阶循环群, 则g恰有(n)个生成元. 如果a是g的一个生成元, 则ar也是g的生成元的充分必要条件是:gcd(n, r)=1,26,例10 求(z12, )的全部生成元. 提示:1是一个生成元,27,解:1是一个生成元. 满足gcd(12, r)=1的r : 1, 5, 7, 11. z12的生成元有: 11=1, 51=5, 71=7, 111=11,28,求出循环群(zp, )和(zp*, )的全部生成元. 从每个群中取出一个生成元,把该群中的全部元素表示成生成元的倍数(或方幂)的形式. 其中 (1) p=7; (2) p=13,29,阿贝尔小传,阿贝尔(n. h. abel)1802年8

11、月5日出生于挪威. 16岁开始学习牛顿、欧拉、拉格朗日和高斯的经典数学著作. 19岁时,他解决了一个让一些著名数学家烦脑了数百年的难题. 他证明了虽然一元二次、三次甚至四次方程都有求根公式, 但是对于一般的五次方程却不存在这样的求根公式. 他对于五次方程求解问题的解决为近世代数的创立做出了基础性的工作,30,此外, 阿贝尔还在椭圆函数论、椭圆积分、阿贝尔积分和无穷级数等方面做出过杰出的贡献. 1829年4月6日, 阿贝尔死于肺结核, 年仅27岁. 1872年, 若尔当(c.jordan)引入了阿贝尔群这一术语, 以纪念这位英年早逝的天才数学家,31,有限环,定义 设r是一个非空集合. 如果在r

12、上定义了两个代数运算, “+”(称为加法)和“” (称为乘法), 并且满足: (r1) (r, +)构成一个交换群; (r2) 乘法结合律: 即对所有的a, b, cr, 有 (ab)c=a(bc); (r3) 乘法对加法的分配律:即对所有的a, b, cr, 有 a(b+c)=ab+ac, (b+c)a=ba+ca, 则称r关于运算“+”和“”构成一个环(ring), 记为(r,+,32,注1: (r, +)是一个交换群, 称为r的加法群. 环r的加法单位元称为环的零元,记为0. 环r的元素a的加法逆元称为a负元, 记为-a. 注2: 如果环r的乘法还满足交换律, 则称r为交换环,33,注3

13、: 如果环r中存在元素e, 使对任意的ar, 有 ae=ea=a, 则称r是一个有单位元的环, 并称e是r的乘法单位元(unit). 如果环r有单位元, 则r的单位元是唯一的. 环r的乘法单位元记为e或1,34,注4: 设环r有单位元e, ar, 如果存在 br,使ab=ba=e, 则称a是r的一个可逆元(invertible element),并称b是a的逆元(inverseelement), 记为b=a-1. 一个环中, 可能有些元素有逆元, 而其它元素没有逆元,35,例4.1.2.1 整数环(z, +, ); 有理数环(q,+, ); 实数环(r,+, ); 复数环(c,+,). 例4.

14、1.2.2 设mz+, zm=0,1, m-1, 则(zm, , ) 是一个有单位元的交换环. 称为模m剩余类环(residue class ring,36,有限域,定义 设(f,+, )是一个环. 如果f有乘法单位元10的, 且每个非零元都是可逆的, 则称(f,+, ) 是一个域(field). 进一步, 如果f是有限集,则称(f,+, ) 是一个有限域(finite field), 也称为伽罗华域(galois field,37,例 有理数域(q,+, ); 实数域(r,+, ); 复数域(c,+, ). 例4.1.2.2 设pz+是素数, zp=0,1, p-1, 则(zp, , ) 是

15、一个有限域,38,定理 (1) 每个有限域的阶一定是素数的幂: pn. 含有pn个元素的有限域记为gf(pn). (2) 任给素数p 和正整数n, 一定存在阶为pn的有限域. (3) 同阶的有限域是同构的. (4) 令gf(pn)*表示gf(pn)的全体非零元的集合, 则gf(pn)*关于乘法是一个pn-1阶循环群,39,含有pn个元素的有限域只有一个. 当n=1时, gf(p)=(zp, , )=fp 称为素域,40,伽罗瓦(. galois), 法国数学家, 1811年10月25日出生于巴黎. 16岁开始自学勒让德、拉格朗日、高斯和柯西等大师的经典数学著作和论文. 18岁时, 他完成了第一

16、篇代数方程的重要论文. 在1828年到1830年之间, 他得到了后来被称为“伽罗瓦理论”的重要结论. 1832年5月30日,伽罗瓦由于政治和爱情的纠葛在决斗中被人射中,次日不幸去世,死时不满21岁,41,伽罗瓦提出的“伽罗瓦域”、“伽罗瓦群”和“伽罗瓦理论” 是近世代数所研究的重要课题, 他的工作是19世纪数学中最杰出的成就之一.伽罗瓦理论是代数学发展中的一个里程碑. 伽罗瓦生前并未获得应有的荣誉, 他投出的研究论文未被接受发表. 直到1846年, 著名数学家刘维尔解读了伽罗瓦的研究手稿, 给出了注释, 才在纯粹与应用数学上发表,42,多项式环与有限域,多项式环的基本性质 设f是一个有限域, 表达式 f(x)=anxn+ an-1xn-1+a1x+a0 (aif, i=0,1, n-1) 称为有限域f上的一个多项(polynomial), x称为未定元(indeterminate,43,多项式的次数(degree): 如果an0,则称f(x)的次数为n, 记为: deg(f(x)=n, deg(0)= -. 首一多项式(monic polynomi