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

2019-02-19 本文已影响22人溺于恐

循环群

由一个元生成的群称为循环群,对循环群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$

上一篇下一篇

猜你喜欢

热点阅读