近世代数理论基础13：循环群

作者: 溺于恐 | 来源:发表于2019-02-19 08:47 被阅读22次

近世代数理论基础13：循环群
近世代数理论基础29：代数扩张
近世代数理论基础2：映射
近世代数理论基础1：集合
近世代数理论基础31：可分扩张
近世代数理论基础27：素域
近世代数理论基础32：有限域
近世代数理论基础14：同构定理
近世代数理论基础40：BCH码
近世代数理论基础28：单扩张

循环群

由一个元生成的群称为循环群,对循环群G, $\exists a\in G$ ,使 $G=<a>=\{a^k|k\in Z\}$

注：上述定义的集合不一定含有无穷多个元,可能 $\exists i,j\in Z,i\neq j$ 使 $a^i=a^j$

例：

1.Z关于加法" $+$ "构成一个循环群,由1生成,即 $Z=<1>$

2.整数模m的剩余类加法群 $(Z/mZ,+)$ 是由 $[1]$ 生成的循环群,即 $Z/mZ=<[1]>$

注：

1.循环群在同构的意义下只有两个

2.循环群的子群仍是循环群

3.循环群是最简单的一类群,其中有限循环群比较常用

定理：设群G是由a生成的循环群,则

1.若 $o(a)=m\lt \infty$ ,则 $G\cong (Z/mZ,+)$

2.若 $o(a)=\infty$ ,则 $G\cong (Z,+)$

证明：

$定义\varphi:Z\to G,\varphi(m)=a^m$

$显然\varphi为满射$

$又\varphi(m+n)=a^{m+n}=a^ma^n=\varphi(m)\varphi(n)$

$\therefore \varphi为群同态映射$

$若o(a)=\infty$

$若n\in Ker(\varphi),则\varphi(n)=a^n=e$

$\therefore n=0$

$\therefore Ker(\varphi)=\{0\}$

$由同态基本定理$

$Z=Z/(0)\cong G$

$若o(a)=m$

$则n\in Ker(\varphi)\Leftrightarrow \varphi(n)=a^n=e$

$\Leftrightarrow m|n$

$\therefore Ker(\varphi)=mZ=\{mk|k\in Z\}$

$由同态基本定理$

$Z/Ker(\varphi)=Z/mZ\cong G\qquad\mathcal{Q.E.D}$

定理：设 $G=<a>$ 是循环群, $H\le G$ ,则 $\exists r\in N$ ,使 $H=<a^r>$

证明：

$设e为G的单位元$

$若H=\{e\},则H为循环群$

$若H\neq \{e\}$

$则a^{-k}=(a^{-1})^k\in H$

$令r=min\{k|a^k\in H,k\gt 0\}$

$\forall g\in H,\exists m\in Z使g=a^m$

$由带余除法$

$\exists q,t\in Z满足m=rq+t,0\le t\lt r$

$则a^t=a^m(a^r)^{-1}\in H$

$由r的取法$

$t=0$

$即m=rq$

$\therefore g=(a^r)^q$

$\therefore H=<a^r>\qquad\mathcal{Q.E.D}$

离散对数

$G=<a>=\{e=a^0,a^1,a^2,\cdots,a^{n-1}\}$ ,其中 $n=|G|=o(a)$ ,即 $\forall b\in G$ , $\exists ! 0\le i\lt n$ 使 $b=a^i$ ,称i为以a为底b的离散对数,记作 $log_ab$

注：群中仅有有限个元,故称离散,离散对数在密码学中有重要应用

数论中的经典例子

例：设p是素数, $G=(Z/pZ)^*=\{[1],[2],\cdots,[p-1]\}$ , $G$ 中的乘法定义为 $[a]\cdot [b]=[ab]$ ,易证这是一个群,单位元为 $[1]$ ,且初等数论中已证它是循环群,生成元称为模p的原根

如取p=13,计算 $(Z/13Z)^*$ 中元的阶

解：

$由Lagrange定理$

$\forall a\in G,有a^{|G|}=e$

$\therefore o(a)是|G|的因子$

$又(Z/13Z)^*中有13-1=12个元$

$\therefore 元的阶只可能是1,2,3,4,6,12$

$\because [2^2]=[4]\neq[1]$

$[2^3]=[8]\neq[1]$

$[2^4]=[3]\neq[1]$

$[2^6]=[4]\cdot[3]=[12]\neq [1]$

$\therefore o([2])=12=|G|$

$即G是循环群,[2]为生成元$

$\therefore 可表示为$

$\begin{array}{c|cc}i&0&1&2&3&4&5&6&7&8&9&10&11\\ \hline [2]^i&[1]&[2]&[4]&[8]&[3]&[6]&[12]&[11]&[9]&[5]&[10]&[7]\end{array}$

$\forall [a]\in G,\exists ! 0\le i\lt |G|,使得$

$[a]=[2]^i$

$称i为a关于2的离散对数$

$记作log_2a$

$如[2]^7=[11],log_211=7$

近世代数理论基础13：循环群
循环群由一个元生成的群称为循环群,对循环群G,,使注：上述定义的集合不一定含有无穷多个元,可能使例： 1.Z...
近世代数理论基础29：代数扩张
代数扩张代数扩张定义：设E是域F的一个扩张,若E中任一元都是F上的代数元,则称E为F的一个代数扩张扩张次数 ...
近世代数理论基础2：映射
映射定义给定非空集合A,B,从A到B的映射是指一个对应法则,通过该法则,对于A中任一元a,有B中唯一的一个元b...
近世代数理论基础1：集合
集合定义定义：一些元或研究对象的全体,称为集合例单元集：一个集X仅有一个元素,X={x} 实数集的闭单位区...
近世代数理论基础31：可分扩张
可分扩张可分扩张定义：设F是一个域,E是F的一个代数扩张,为E中的元,若在F上的极小多项式没有重根,则称在F上...
近世代数理论基础27：素域
素域扩域定义：若域F是域E的子域,则称E为F的扩域(扩张),并把这一对域记作注：任一域都是它的子域的一个扩张...
近世代数理论基础32：有限域
有限域由有限个元组成的域称为有限域,又称为伽罗瓦域整数模p的剩余类环是一个有p个元的有限域显然,任一有限域F...
近世代数理论基础14：同构定理
同构定理同态的基本性质设是同态映射,,令为S在映射f下的像集,对,令为集合的原像引理：设是满同态,则有 1....
近世代数理论基础40：BCH码
BCH码纠错码数字信息传输过程中可能受干扰导致出错,为了正确传送信息,采用抗干扰编码的方法,在信息传输之前进行...
近世代数理论基础28：单扩张
单扩张代数元定义：域F上存在不全为0的元,使得,则称为域F上的一个代数元,否则称为F上的一个超越元两类单扩张...

近世代数理论基础13：循环群

循环群

离散对数

数论中的经典例子

相关文章

近世代数理论基础13：循环群

近世代数理论基础29：代数扩张

近世代数理论基础2：映射

近世代数理论基础1：集合

近世代数理论基础31：可分扩张

近世代数理论基础27：素域

近世代数理论基础32：有限域

近世代数理论基础14：同构定理

近世代数理论基础40：BCH码

近世代数理论基础28：单扩张

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

近世代数