循环群基本定理为循环群中循环子群的存在性提供了保证。
在有限域上多项式的数论变换 (NTT) 以及 ZK-STARKs 中的 FRI 操作的上下文中，我们需要阶（元素数量）为 2 的幂的乘法子群。循环群基本定理使我们能够快速确定特定的有限域是否具有该阶的乘法子群。
我们将首先介绍以下预备知识，然后再深入探讨循环群基本定理：
子群的定义
群或子群的阶
乘法群中元素的幂
循环子群、循环群及其生成元
1. 子群的定义
给定一个群 G G G G G G H H H G G G H H H G G G 子群 。换句话说，如果我们将范围限制在 H H H G G G H H H 封闭 的，因此每当我们对 H H H H H H
子群示例
模 8 整数加法构成一个群 Z 8 = ( { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } , + ) \mathbb{Z}_8 = (\{0, 1, 2, 3, 4, 5, 6, 7\}, +) Z 8 = ({ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } , + ) H 1 = ( { 0 , 2 , 4 , 6 } , + ) H_1=(\{0, 2, 4, 6\}, +) H 1 = ({ 0 , 2 , 4 , 6 } , + ) H 2 = ( { 0 , 4 } , + ) H_2=(\{0, 4\}, +) H 2 = ({ 0 , 4 } , + ) Z 8 \mathbb{Z}_8 Z 8 H 3 = ( { 0 , 2 } , + ) H_3=(\{0, 2\}, +) H 3 = ({ 0 , 2 } , + ) ( 2 + 2 ) ∉ H 3 (2+2) \not \in H_3 ( 2 + 2 ) ∈ H 3
2. 群或子群的阶
群 G G G 阶 （用 ∣ G ∣ |G| ∣ G ∣
群和子群的阶示例
考虑上例中的群 Z 8 \mathbb{Z}_8 Z 8 Z 8 \mathbb{Z}_8 Z 8 ∣ Z 8 ∣ = 8 |\mathbb{Z}_8| = 8 ∣ Z 8 ∣ = 8 H = ( { 0 , 2 , 4 , 6 } , + ) H = (\{0, 2, 4, 6\}, +) H = ({ 0 , 2 , 4 , 6 } , + ) ∣ H ∣ = 4 |H| = 4 ∣ H ∣ = 4
3. 乘法群中元素的幂
如果 g ∈ G g \in G g ∈ G g g g ⟨ g ⟩ \langle g\rangle ⟨ g ⟩ { g i : i ∈ Z } \{g^i: i\in\mathbb{Z}\} { g i : i ∈ Z } G = { 1 , 2 , 3 , 4 , 5 , 6 } G =\{1, 2, 3, 4, 5, 6\} G = { 1 , 2 , 3 , 4 , 5 , 6 } G G G 3 3 3
3 的幂 = ⟨ 3 ⟩ = { 3 0 , 3 1 , 3 2 , 3 3 , 3 4 , 3 5 , 3 6 , … } . \begin{aligned} \text{3 的幂} = \langle 3\rangle = \{3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6, \dots\}.
\end{aligned} 3 的幂 = ⟨ 3 ⟩ = { 3 0 , 3 1 , 3 2 , 3 3 , 3 4 , 3 5 , 3 6 , … } .
因为：
3 0 = 1 , 3 1 = 3 , 3 2 = 9 ≡ 2 , 3 3 = 9 ∗ 3 ≡ 2 ∗ 3 ≡ 6 , 3 4 = 9 ∗ 9 ≡ 2 ∗ 2 ≡ 4 , 3 5 = 9 ∗ 9 ∗ 3 ≡ 2 ∗ 2 ∗ 3 ≡ 12 ≡ 5 , 3 6 = 9 ∗ 9 ∗ 9 ≡ 2 ∗ 2 ∗ 2 ≡ 8 ≡ 1. \begin{aligned} &3^0 = 1,\\ &3^1 = 3,\\ &3^2 = 9 \equiv 2,\\ &3^3 = 9 * 3 \equiv 2 * 3 \equiv 6,\\ &3^4 = 9 * 9 \equiv 2 * 2 \equiv 4,\\ &3^5 = 9 * 9 * 3 \equiv 2 * 2 * 3 \equiv 12 \equiv 5,\\ &3^6 = 9 * 9 * 9 \equiv 2 * 2 * 2 \equiv 8 \equiv 1.
\end{aligned} 3 0 = 1 , 3 1 = 3 , 3 2 = 9 ≡ 2 , 3 3 = 9 ∗ 3 ≡ 2 ∗ 3 ≡ 6 , 3 4 = 9 ∗ 9 ≡ 2 ∗ 2 ≡ 4 , 3 5 = 9 ∗ 9 ∗ 3 ≡ 2 ∗ 2 ∗ 3 ≡ 12 ≡ 5 , 3 6 = 9 ∗ 9 ∗ 9 ≡ 2 ∗ 2 ∗ 2 ≡ 8 ≡ 1.
3 7 3^7 3 7
3 7 = 3 6 ∗ 3 ≡ 1 ∗ 3 ≡ 3 ( m o d 7 ) . 3^7 = 3^6 * 3 \equiv 1 * 3 \equiv 3 \pmod{7}. 3 7 = 3 6 ∗ 3 ≡ 1 ∗ 3 ≡ 3 ( mod 7 ) .
因此，⟨ 3 ⟩ = { 1 , 2 , 3 , 4 , 5 , 6 } \langle 3\rangle = \{1, 2, 3, 4, 5, 6\} ⟨ 3 ⟩ = { 1 , 2 , 3 , 4 , 5 , 6 } i > 6 i>6 i > 6 3 i 3^i 3 i
练习 ：找出由元素 4 4 4
任意元素的幂构成一个子群
设 g g g G G G g g g
⟨ g ⟩ = { g i : i ∈ Z } , \langle g\rangle = \{g^i: i\in\mathbb{Z}\}, ⟨ g ⟩ = { g i : i ∈ Z } ,
是 G G G
证明。 见附录
4. 循环子群、循环群及其生成元
设 g g g G G G ⟨ g ⟩ = { g i : i ∈ Z } \langle g\rangle = \{g^i: i\in\mathbb{Z}\} ⟨ g ⟩ = { g i : i ∈ Z } g g g G G G G = { 1 , 2 , 3 , 4 , 5 , 6 } G =\{1, 2, 3, 4, 5, 6\} G = { 1 , 2 , 3 , 4 , 5 , 6 } 2 2 2
⟨ 2 ⟩ = { 2 0 = 1 , 2 1 = 2 , 2 2 = 4 , 2 3 = 1 , 2 4 = 2 , 2 5 = 4 , 2 6 = 1 } = { 1 , 2 , 4 } \langle 2 \rangle = \{2^0=\boxed{1}, 2^1=\boxed{2}, 2^2=\boxed{4},2^3=\boxed{1},2^4=\boxed{2},2^5=\boxed{4},2^6=\boxed{1}\}=\{1, 2, 4\} ⟨ 2 ⟩ = { 2 0 = 1 , 2 1 = 2 , 2 2 = 4 , 2 3 = 1 , 2 4 = 2 , 2 5 = 4 , 2 6 = 1 } = { 1 , 2 , 4 }
练习 ：找出由元素 6 6 6
循环群的定义
设 g g g G G G G = ⟨ g ⟩ G = \langle g\rangle G = ⟨ g ⟩ G G G g g g G G G
循环群与生成元示例
考虑模 7 的非零整数乘法群 G = { 1 , 2 , 3 , 4 , 5 , 6 } G =\{1, 2, 3, 4, 5, 6\} G = { 1 , 2 , 3 , 4 , 5 , 6 } ⟨ 3 ⟩ = G \langle 3 \rangle = G ⟨ 3 ⟩ = G G G G 3 3 3 G G G
注意 ⟨ 2 ⟩ = { 1 , 2 , 4 } ≠ G \langle 2 \rangle = \{1, 2, 4\}\neq G ⟨ 2 ⟩ = { 1 , 2 , 4 } = G 2 2 2 不是 G G G 2 2 2 G G G
练习 ：判断 5 5 5 G G G
循环群的生成元不一定唯一 循环群至少有一个生成元，但生成元不必是唯一的。换句话说，一个循环群可以有多个生成元，其中任何一个都能生成整个群。对于循环子群也是如此。
正如你在上面的示例和练习中所见，元素 3 3 3 5 5 5 G = { 1 , 2 , 3 , 4 , 5 , 6 } G =\{1, 2, 3, 4, 5, 6\} G = { 1 , 2 , 3 , 4 , 5 , 6 } 生成元 。
再举个例子，考虑模 5 的非零整数乘法群，即 { 1 , 2 , 3 , 4 } \{1, 2 ,3, 4\} { 1 , 2 , 3 , 4 } 2 2 2 3 3 3
2 0 = 1 , 3 0 = 1 , 2 1 = 2 , 3 1 = 3 , 2 2 = 4 , 3 2 = 4 , 2 3 = 3 , 3 3 = 2. \begin{aligned}
&2^0 =1,\qquad\qquad\qquad\qquad 3^0 =1,\\
&2^1 =2,\qquad\qquad\qquad\qquad 3^1 =3,\\
&2^2 =4,\qquad\qquad\qquad\qquad 3^2 =4,\\
&2^3 =3,\qquad\qquad\qquad\qquad3^3 =2.\\
\end{aligned} 2 0 = 1 , 3 0 = 1 , 2 1 = 2 , 3 1 = 3 , 2 2 = 4 , 3 2 = 4 , 2 3 = 3 , 3 3 = 2.
有限循环群基本定理
有限循环群基本定理提出了三个断言。设 G G G H H H G G G
H H H H H H H H H G G G H H H G G G G G G 如果 G G G q q q k k k q q q k k k 必然存在 且唯一 。事实上，我们可以直接找到它的生成元：如果 g g g G G G g q k g^\frac{q}{k} g k q k k k k k k ⟨ g q k ⟩ \langle g^\frac{q}{k} \rangle ⟨ g k q ⟩
与拉格朗日定理的联系 有限循环群基本定理的断言 (2) 对任何有限群 G G G G G G 拉格朗日定理 (Lagrange’s Theorem) 。
为简便起见，我们将简称为循环群基本定理，并默认我们讨论的是有限群。
使用循环群基本定理的示例
让我们使用模 7 的乘法群 G = { 1 , 2 , 3 , 4 , 5 , 6 } G = \{1,2,3,4,5,6\} G = { 1 , 2 , 3 , 4 , 5 , 6 } g = 3 g = 3 g = 3
阶为 1 的子群
根据循环群基本定理，我们知道 G G G k = 1 k = 1 k = 1 3 6 1 ≡ 1 ( m o d 7 ) 3^{\frac{6}{1}} \equiv 1\pmod{7} 3 1 6 ≡ 1 ( mod 7 ) 1 1 1
阶为 2 的子群
现在让我们找出大小为 2 的子群。我们知道它存在，因为 2 能整除 6。在这里，我们有 g = 3 g = 3 g = 3 q = 6 q = 6 q = 6 k = 2 k = 2 k = 2 g q k = 3 6 2 = 3 3 ≡ 6 ( m o d 7 ) g^{\frac{q}{k}} = 3^{\frac{6}{2}} = 3^3 \equiv 6\pmod{7} g k q = 3 2 6 = 3 3 ≡ 6 ( mod 7 ) 6 6 6 { 1 , 6 } \{1, 6\} { 1 , 6 }
阶为 3 的子群
由于 3 能整除 6，因此存在一个阶为 3 的子群。此外，元素 3 q k = 3 6 3 = 3 2 ≡ 2 ( m o d 7 ) 3^{\frac{q}{k}} = 3^{\frac{6}{3}} = 3^{2} \equiv 2\pmod{7} 3 k q = 3 3 6 = 3 2 ≡ 2 ( mod 7 ) ⟨ 2 ⟩ = { 2 0 , 2 1 , 2 2 } = { 1 , 2 , 4 } \langle 2\rangle = \{2^0, 2^1, 2^2\} =\{1, 2, 4\} ⟨ 2 ⟩ = { 2 0 , 2 1 , 2 2 } = { 1 , 2 , 4 }
阶为 4 和 5 的子群
不存在阶为 4 和 5 的子群，因为这些数字不能整除 6。
阶为 6 的子群
由于 6 能整除 6，因此存在一个阶为 6 的子群。此外，3 q k = 3 6 6 = 3 1 = 3 3^{\frac{q}{k}} = 3^{\frac{6}{6}} = 3^{1} = 3 3 k q = 3 6 6 = 3 1 = 3
⟨ 3 ⟩ = { 1 , 2 , 3 , 4 , 5 , 6 } = G . \langle 3 \rangle =\{1, 2, 3, 4, 5, 6\} = G. ⟨ 3 ⟩ = { 1 , 2 , 3 , 4 , 5 , 6 } = G .
练习 ：考虑模 11 的乘法群，其元素为 G = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } G = \{1,2,3,4,5,6,7,8,9,10\} G = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 }
找出该群的一个生成元。
该群有一个阶为 5 的子群，因为 5 能整除 G G G
有限域中阶为 k k k
我们可以在有限域中找到特定阶的乘法子群。首先，让我们看看有限域的定义：
根据定义，一个域 ( F , + , ∗ ) (\mathbb{F}, + , *) ( F , + , ∗ )
加法群 ：( F , + ) (\mathbb{F}, +) ( F , + ) 乘法群 ：( F ∗ , ∗ ) (\mathbb{F^*}, *) ( F ∗ , ∗ ) F ∗ = F ∖ { 0 } \mathbb{F}^* = \mathbb{F}\setminus\{0\} F ∗ = F ∖ { 0 }
请注意，F q \mathbb{F}_q F q q q q F q ∗ \mathbb{F}^*_q F q ∗ F q \mathbb{F}_q F q q − 1 q-1 q − 1
在接下来的定理中，我们将会看到每个有限域必定包含一个阶为 q − 1 q - 1 q − 1 0 0 0
定理 1：乘法群 F q ∗ \mathbb{F}^*_q F q ∗ q − 1 q-1 q − 1
如果 F q \mathbb{F}_q F q q q q 有限域 ，那么其乘法群 F q ∗ \mathbb{F}^*_q F q ∗ q − 1 q-1 q − 1
从有限域的定义可以直接得出 F q ∗ \mathbb{F}^*_q F q ∗ q − 1 q-1 q − 1
由于证明乘法群的循环性将超出本文的范围，我们将以此作为已知事实。
循环群存在生成元，因此我们知道存在某个 g ∈ F q ∗ g\in \mathbb{F}^*_q g ∈ F q ∗
F q ∗ = { 1 , g 1 , g 2 , … , g q − 2 } = ⟨ g ⟩ . \mathbb{F}^*_q = \{1, g^1, g^2, \dots, g^{q-2}\} = \langle g \rangle. F q ∗ = { 1 , g 1 , g 2 , … , g q − 2 } = ⟨ g ⟩ .
有限域中的本原元（生成元）
在域论中，有限域 F q \mathbb{F}_q F q 本原元 （primitive element）就是该域乘法群的生成元。定理 1 中的元素 g g g F q \mathbb{F}_q F q
下面的 Python 代码使用了 galois 库来识别 F 7 \mathbb{F}_7 F 7
Copy import galois GF = galois.GF( 7 ) primitive_elements = GF .primitive_elements print ( "Primitive elements:" , primitive_elements) # Primitive elements: [3 5] # Alternatively, find a single primitive element # suitable when there are a lot of primitive elements primitive_element = GF .primitive_element print ( "A primitive element:" , primitive_element) # A primitive element: 3 练习 ：使用 Python 找出域 F 11 \mathbb{F}_{11} F 11
推论 1：测试阶为 k k k
一个有用的推论是，通过列出 q − 1 q-1 q − 1 F 41 \mathbb{F}_{41} F 41 F 41 ∗ \mathbb{F}_{41}^* F 41 ∗ F 41 ∗ \mathbb{F}_{41}^* F 41 ∗
再举个例子，考虑域 F 17 \mathbb{F}_{17} F 17 F 17 ∗ \mathbb{F}_{17}^* F 17 ∗ F 17 ∗ \mathbb{F}_{17}^* F 17 ∗ F 17 \mathbb{F}_{17} F 17
要找到给定大小乘法子群的生成元，我们可以利用上述基本定理的断言 (3)。F q ∗ \mathbb{F}_{q}^* F q ∗ q − 1 q-1 q − 1 g g g k k k g g g g q − 1 k g^\frac{q-1}{k} g k q − 1
综合示例
考虑有限域 F 17 = { 0 , 1 , 2 , … , 16 } \mathbb{F}_{17} =\{0, 1, 2, \dots, 16\} F 17 = { 0 , 1 , 2 , … , 16 } k k k F 17 \mathbb{F}_{17} F 17 k k k
由于乘法子群 F 17 ∗ \mathbb{F}_{17}^* F 17 ∗ q − 1 = 17 − 1 = 16 q-1=17-1=16 q − 1 = 17 − 1 = 16
这些子群都是循环的，因此每个子群至少有一个生成元。根据定理的断言 (3)，我们知道每个子群的生成元由 g q − 1 k g^\frac{q-1}{k} g k q − 1 g g g k k k
因此，为了生成这些子群，第一步是找出 F 17 ∗ \mathbb{F}_{17}^* F 17 ∗ F 17 \mathbb{F}_{17} F 17
F 17 ∗ \mathbb{F}^*_{17} F 17 ∗ 回顾定理 1，F 17 ∗ \mathbb{F}^*_{17} F 17 ∗ 是一个循环群 。为了证明 F 17 ∗ \mathbb{F}^*_{17} F 17 ∗ 3 3 3 3 3 3
3 0 = 1 , 3 1 = 3 , 3 2 = 9 , 3 3 ≡ 9 ∗ 3 ≡ 10 , ( 27 − 17 = 10 ) 3 4 ≡ 10 ∗ 3 ≡ 13 , ( 30 − 17 = 13 ) 3 5 ≡ 13 ∗ 3 ≡ 5 , ( 39 − 2 ∗ 17 = 5 ) 3 6 ≡ 5 ∗ 3 ≡ 15 , 3 7 ≡ 15 ∗ 3 ≡ 11 , ( 45 − 2 ∗ 17 = 11 ) 3 8 ≡ 11 ∗ 3 ≡ 16 , ( 33 − 17 = 16 ) 3 9 ≡ 16 ∗ 3 ≡ 14 , ( 48 − 2 ∗ 17 = 14 ) 3 10 ≡ 14 ∗ 3 ≡ 8 , ( 42 − 2 ∗ 17 = 8 ) 3 11 ≡ 8 ∗ 3 ≡ 7 , ( 24 − 17 = 7 ) 3 12 ≡ 7 ∗ 3 ≡ 4 , ( 21 − 17 = 4 ) 3 13 ≡ 4 ∗ 3 ≡ 12 , 3 14 ≡ 12 ∗ 3 ≡ 2 , ( 36 − 2 ∗ 17 = 2 ) 3 15 ≡ 2 ∗ 3 ≡ 6 , 3 16 = 6 ∗ 3 ≡ 1 , ( 18 − 17 = 1 ) . \begin{aligned}
&3^0 = \boxed{1},\\
&3^1 = \boxed{3},\\
&3^2 = \boxed{9},\\
&3^3 \equiv 9 * 3 \equiv \boxed{10},\space\space (27 - 17 = 10)\\
&3^4 \equiv 10 * 3\equiv \boxed{13},\space\space(30 - 17 = 13)\\
&3^5 \equiv 13 * 3 \equiv \boxed{5},\space\space(39 - 2*17 = 5)\\
&3^6 \equiv 5 * 3 \equiv \boxed{15},\\
&3^7 \equiv 15 * 3 \equiv \boxed{11},\space\space(45 - 2*17 = 11)\\
&3^8 \equiv 11 * 3 \equiv \boxed{16},\space\space(33 - 17 = 16)\\
&3^9 \equiv 16 * 3 \equiv \boxed{14},\space\space(48 - 2*17 = 14)\\
&3^{10} \equiv 14 * 3 \equiv \boxed{8},\space\space(42 - 2*17 = 8)\\
&3^{11} \equiv 8 * 3 \equiv \boxed{7},\space\space(24 - 17 = 7)\\
&3^{12} \equiv 7 * 3 \equiv \boxed{4},\space\space(21 - 17 = 4)\\
&3^{13} \equiv 4 * 3 \equiv \boxed{12},\\
&3^{14} \equiv 12 * 3 \equiv \boxed{2},\space\space(36 - 2*17 = 2)\\
&3^{15} \equiv 2 * 3 \equiv \boxed{6},\\
&3^{16} = 6 * 3 \equiv \boxed{1},\space\space(18 - 17 = 1).
\end{aligned} 3 0 = 1 , 3 1 = 3 , 3 2 = 9 , 3 3 ≡ 9 ∗ 3 ≡ 10 , ( 27 − 17 = 10 ) 3 4 ≡ 10 ∗ 3 ≡ 13 , ( 30 − 17 = 13 ) 3 5 ≡ 13 ∗ 3 ≡ 5 , ( 39 − 2 ∗ 17 = 5 ) 3 6 ≡ 5 ∗ 3 ≡ 15 , 3 7 ≡ 15 ∗ 3 ≡ 11 , ( 45 − 2 ∗ 17 = 11 ) 3 8 ≡ 11 ∗ 3 ≡ 16 , ( 33 − 17 = 16 ) 3 9 ≡ 16 ∗ 3 ≡ 14 , ( 48 − 2 ∗ 17 = 14 ) 3 10 ≡ 14 ∗ 3 ≡ 8 , ( 42 − 2 ∗ 17 = 8 ) 3 11 ≡ 8 ∗ 3 ≡ 7 , ( 24 − 17 = 7 ) 3 12 ≡ 7 ∗ 3 ≡ 4 , ( 21 − 17 = 4 ) 3 13 ≡ 4 ∗ 3 ≡ 12 , 3 14 ≡ 12 ∗ 3 ≡ 2 , ( 36 − 2 ∗ 17 = 2 ) 3 15 ≡ 2 ∗ 3 ≡ 6 , 3 16 = 6 ∗ 3 ≡ 1 , ( 18 − 17 = 1 ) .
3 17 3^{17} 3 17
3 17 = 3 16 ∗ 3 ≡ 1 ∗ 3 = 3. 3^{17} = 3^{16} * 3 \equiv 1 * 3 = 3. 3 17 = 3 16 ∗ 3 ≡ 1 ∗ 3 = 3.
你可以看到，对于所有的 i ≥ 17 i \ge 17 i ≥ 17 3 i 3^i 3 i 3 0 , 3 1 , 3 2 , … , 3 16 3^0, 3^1, 3^2, \dots, 3^{16} 3 0 , 3 1 , 3 2 , … , 3 16 ⟨ 3 ⟩ = { 1 , 2 , … , 16 } = F 17 ∗ \langle 3 \rangle = \{1, 2, \dots, 16\} = \mathbb{F}^*_{17} ⟨ 3 ⟩ = { 1 , 2 , … , 16 } = F 17 ∗
这个生成元可以通过 Python 代码中的 galois.primitive_elements 找到。
Copy import galois GF = galois.GF( 17 ) primitive_element = GF .primitive_element print ( "A primitive element:" , primitive_element) # A primitive element: 3 在 F 17 ∗ \mathbb{F}^*_{17} F 17 ∗ k k k
假设我们想确定在有限域 F q = F 17 \mathbb{F}_q = \mathbb{F}_{17} F q = F 17 k = 4 k=4 k = 4 F q \mathbb{F}_q F q q − 1 q-1 q − 1 F 17 \mathbb{F}_{17} F 17 F 17 ∗ \mathbb{F}_{17}^* F 17 ∗ q − 1 = 17 − 1 = 16 q-1 = 17-1 = 16 q − 1 = 17 − 1 = 16
回顾有限循环群基本定理，因为 k k k q − 1 q-1 q − 1 g q − 1 k g^{\frac{q-1}{k}} g k q − 1 ⟨ g q − 1 k ⟩ \langle g^{\frac{q-1}{k}}\rangle ⟨ g k q − 1 ⟩
g q − 1 k = 3 16 4 = 3 4 ≡ 13 ( m o d 17 ) . g^{\frac{q-1}{k}} = 3^{\frac{16}{4}} = 3^4 \equiv 13\pmod{17}. g k q − 1 = 3 4 16 = 3 4 ≡ 13 ( mod 17 ) .
因此，13 是 F 17 ∗ \mathbb{F}^*_{17} F 17 ∗
⟨ 13 ⟩ = { 13 0 = 1 , 13 1 = 13 , 13 2 ≡ 16 , 13 3 ≡ 4 , 13 4 ≡ 1 , 13 5 ≡ 13 , … } . \langle 13 \rangle = \{13^0 = \boxed{1}, 13^1 = \boxed{13}, 13^2\equiv\boxed{16}, 13^3\equiv\boxed{4}, 13^4\equiv\boxed{1}, 13^5\equiv\boxed{13}, \dots\}. ⟨ 13 ⟩ = { 1 3 0 = 1 , 1 3 1 = 13 , 1 3 2 ≡ 16 , 1 3 3 ≡ 4 , 1 3 4 ≡ 1 , 1 3 5 ≡ 13 , … } .
明确地说，该子群为 { 1 , 13 , 16 , 4 } \{1, 13, 16, 4\} { 1 , 13 , 16 , 4 }
练习： 计算阶为 2 2 2 8 8 8
总结
目标是在域 F q \mathbb{F}_q F q k k k
如果 G = ⟨ g ⟩ = { g i : i ∈ Z } G = \langle g\rangle = \{g^i: i\in\mathbb{Z}\} G = ⟨ g ⟩ = { g i : i ∈ Z } G G G g g g G G G
如果 F q \mathbb{F}_q F q q q q 有限域 ，则 ( F q ∗ , . ) (\mathbb{F}^*_q, .) ( F q ∗ , . ) q − 1 q-1 q − 1
循环群基本定理指出，有限域 F q \mathbb{F}_q F q k k k k k k q − 1 q-1 q − 1 g q − 1 k g^{\frac{q-1}{k}} g k q − 1 g g g F q ∗ \mathbb{F}^*_q F q ∗
附录
我们将验证 ⟨ g ⟩ \langle g \rangle ⟨ g ⟩ G G G
单位元 ：因为 1 = g 0 1 = g^0 1 = g 0 1 ∈ ⟨ g ⟩ 1 \in \langle g \rangle 1 ∈ ⟨ g ⟩
封闭性： 假设 a , b ∈ ⟨ g ⟩ a, b \in \langle g \rangle a , b ∈ ⟨ g ⟩ n , m n, m n , m a = g n a = g^n a = g n b = g m b = g^m b = g m
a b = g n g m = g n + m . ab = g^ng^m = g^{n+m}. ab = g n g m = g n + m .
因为 n + m ∈ Z n+m\in\mathbb{Z} n + m ∈ Z a b ∈ ⟨ g ⟩ ab\in \langle g \rangle ab ∈ ⟨ g ⟩
逆元： 假设 a ∈ ⟨ g ⟩ a\in \langle g \rangle a ∈ ⟨ g ⟩ m m m a = g m a = g^m a = g m
a − 1 = ( g m ) − 1 = g − m . a^{-1} = (g^m)^{-1} = g^{-m}. a − 1 = ( g m ) − 1 = g − m .
因为 − m ∈ Z -m\in\mathbb{Z} − m ∈ Z a − 1 ∈ ⟨ g ⟩ a^{-1} \in \langle g \rangle a − 1 ∈ ⟨ g ⟩
练习
F 31 \mathbb{F}_{31} F 31
F 5 \mathbb{F}_{5} F 5
F 51 \mathbb{F}_{51} F 51