近世代數(shù)理論基礎(chǔ)13：循環(huán)群

循環(huán)群

由一個(gè)元生成的群稱(chēng)為循環(huán)群,對(duì)循環(huán)群G,\exists a\in G,使G=<a>=\{a^k|k\in Z\}

注：上述定義的集合不一定含有無(wú)窮多個(gè)元,可能\exists i,j\in Z,i\neq j使a^i=a^j

例：

1.Z關(guān)于加法"+"構(gòu)成一個(gè)循環(huán)群,由1生成,即Z=<1>

2.整數(shù)模m的剩余類(lèi)加法群(Z/mZ,+)是由[1]生成的循環(huán)群,即Z/mZ=<[1]>?

注：

1.循環(huán)群在同構(gòu)的意義下只有兩個(gè)

2.循環(huán)群的子群仍是循環(huán)群

3.循環(huán)群是最簡(jiǎn)單的一類(lèi)群,其中有限循環(huán)群比較常用

定理：設(shè)群G是由a生成的循環(huán)群,則

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為群同態(tài)映射

若o(a)=\infty

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

\therefore n=0

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

由同態(tài)基本定理

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\}

由同態(tài)基本定理

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

定理：設(shè)G=<a>是循環(huán)群,H\le G,則\exists r\in N,使H=<a^r>

證明：

設(shè)e為G的單位元

若H=\{e\},則H為循環(huán)群

若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}

離散對(duì)數(shù)

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,稱(chēng)i為以a為底b的離散對(duì)數(shù),記作log_ab

注：群中僅有有限個(gè)元,故稱(chēng)離散,離散對(duì)數(shù)在密碼學(xué)中有重要應(yīng)用

數(shù)論中的經(jīng)典例子

例：設(shè)p是素?cái)?shù),G=(Z/pZ)^*=\{[1],[2],\cdots,[p-1]\},G中的乘法定義為[a]\cdot [b]=[ab],易證這是一個(gè)群,單位元為[1],且初等數(shù)論中已證它是循環(huán)群,生成元稱(chēng)為模p的原根

如取p=13,計(jì)算(Z/13Z)^*中元的階

解：

由Lagrange定理

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

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

又(Z/13Z)^*中有13-1=12個(gè)元

\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是循環(huán)群,[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

稱(chēng)i為a關(guān)于2的離散對(duì)數(shù)

記作log_2a

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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容