密码学学习笔记——筑基篇·卷二（群论）

群论

代数结构(algebraic structure)

$(G,🐱,🥒\dots$)

$G指非空集合，\underbrace{🐱, 🥒 ,\dots}_{二元运算(需要两个运算数)}$

$\begin{align} 封闭性：\forall\ a,b & \in G, \\ a🐱b & \in G\\a 🥒 b & \in G\\ \dots \\集合中任意两个元素运算&的结果仍然是这个集合里的元素\end{align}$

代数结构必须满足封闭性

群(Group)

定义：若 $(G,*)$ 是一个群，则它满足以下性质：

封闭性：$ \forall a,b\in \mathbb{G}, a*b \in \mathbb{G}$
结合律： $\forall a,b,c\in \mathbb{G}, a*(b*c)=(a*b)*c$
单位元(幺元,identity)： $\exists e\in \mathbb{G} , \forall a\in \mathbb{G} , a*e=e*a=a$

定理1：群里的单位元是唯一的
逆元(inverse)： $\exists b\in \mathbb{G} , a*b=b*a=e$
$a的逆元记为a^{-1},即a^{-1}=b,b^{-1}=a，\\单位元以自身为逆元$

定理2:每个元素都有唯一的逆元

例：

$(\mathbb{Z},+)$
封闭性：整数相加还是整数
结合律：整数相加满足加法结合律
单位元：0 (任何整数加0都等于它本身)
逆元：整数的相反数
是群😊

$(\mathbb{Q},\times)$
封闭性：有理数相乘还是有理数
结合律：有理数相乘满足乘法结合律
单位元：1 (任何有理数乘1都等于它本身)
逆元：有理数的倒数(0除外)
不是群😭
$(\mathbb{Q}\setminus\{0\},\times)$就是群了

$(\mathbb{Z_p^},\times)$
封闭性：相乘再模p，还是$\mathbb{Z_p^}$里的元素
结合律：模运算下乘法满足乘法结合律
单位元：1
逆元：乘法逆元
是群😊

“$(\mathbb{G},*)$是一个群”,通常简写作：“$\mathbb{G}$是一个群”

例：简称“$\mathbb{Z}_p^*$ 是一个群”,默认运算为“模$p$下的乘法”

一些概念

有限群：$\mathbb{G}$是有限集，比如 $(\mathbb{Z}_p^*,X)$称$\mathbb{G}$里元素个数为群$\mathbb{G}$的“阶”,记为$|\mathbb{G}|$

无限群：$\mathbb{G}$是无限集，比如$(\mathbb{Z},+)$、$(\mathbb{Q}\setminus\{0\},\times)$，群$\mathbb{G}$的“阶”为无限阶

单位元、逆元

封闭性$\Rightarrow$左单位元=右单位元=单位元
结合律$\Rightarrow$左逆元=右逆元=逆元

平凡群：群里只有一个元素时，称为“平凡群”。唯一元素就是单位元。

如:$(\{1\},\times)$
封闭性：1$\times$1=1
结合律：乘法结合律
单位元：1
逆元：1$\times$1=1

群的性质

(消去律) $a*b=a*c\Rightarrow b=c$
方程$a*x=b\ 有唯一解下\in \mathbb{G}$
$(a*b)^{-1}=b^{-1}*a^{-1}$
$(a^{-1})^{-1}=a$

阿贝尔群（abelian group）

又称交换群(commutative group)

定义：如果对于群$\mathbb{G}$中的任意元素$a,b\in \mathbb{G}$,都有 $a*b=b*a$ ，则称$\mathbb{G}$为阿贝尔群。

定理：群$\mathbb{G}$是阿贝尔群，当且仅当，$\forall a,b\in \mathbb{G}$,有 $(a*b)^2=a^2*b^2$

定理：群$\mathbb{G}$是阿贝尔群，$\forall a,b\in \mathbb{G}$,有 $(a*b)^t=a^t*b^t$

群的简记符号

t个a一起运算，简记为 $a^t:a*a*\dots*a$
并不表示t和a之间的运算，t是整数，a是群里的元素

$a^{-t}: (a^{-1})^t=a^{-1}*a^{-1}*\cdots*a^{-1}$

$(a^t)^m=a^{tm}$

$a^t*a^m=a^{t+m}$

$(a^{-1})^t=(a^t)^{-1}$

子群(subgroup)

定义：设 $(\mathbb{G},*)$ 是群，$\mathbb{H}$是$\mathbb{G}$的非空子集，如果 $(\mathbb{H},*)$ 是一个群，则称 $(\mathbb{H},*)$ 是 $(\mathbb{G},*)$ 的子群。

$\mathbb{G}的子群$

平凡子群： $(\{e\},*)、(\mathbb{G},*)$
非平凡子群： $(\mathbb{H},*)$ 且 $\mathbb{H}\neq \{ e\} , G$ (又称真子群)

阿贝尔群的子群也一定是阿贝尔群

子群的单位元

定理：$\mathbb{H}$是群$\mathbb{G}$的子群，$e\in \mathbb{G}$是单位元，则$e$ 也是子群$\mathbb{H}$的单位元。(省流：群的单位元也是其子群的单位元)

子群的逆元

定理：$\mathbb{H}$是群$\mathbb{G}$的子群，$a\in \mathbb{H}$是单位元，,则 $a^{-1}\in \mathbb{H}$(省流:元素在子群中,其逆元也必在该子群中)

判断子群

判断子群(1)

定理：$\mathbb{H}$是群$\mathbb{G}$的非空子集，对于任意 $a,b\in \mathbb{H}$,都有 $a*b^{-1}\in \mathbb{H}$ ,则$\mathbb{H}$是 $\mathbb{G}$ 的子群。

判断子群(2)

定理：$\mathbb{H}$是群$\mathbb{G}$的非空子集，如果$\mathbb{H}$是有限集，而且$\mathbb{G}$的运算在$\mathbb{H}$上满足封闭性，则$\mathbb{H}$是$\mathbb{G}$的子群。(*省流：$\mathbb{H}$是有限集、封闭，便是子群)

构造子群

方法1

定理：$\mathbb{G}$是阿贝尔群，$m\in\mathbb{Z}$,
则$\mathbb{G}^m:=\{a^m\mid a\in \mathbb{G}\}$是$\mathbb{G}$的子群。

$\mathbb{(Z_n^{*}})^2是\mathbb{Z_n^{*}}的子群$ $\mathbb{(Z_n^{*}})^m是\mathbb{Z_n^{*}}的子群$

方法2

定理：$\mathbb{G}$是阿贝尔群，$m\in\mathbb{Z}$,
则$\mathbb{G}\{m\}:=\{a\in \mathbb{G}\mid a^m=e\}$是$\mathbb{G}$的子群。

例:$\mathbb{Z_n}\{m\}=\mathbb{Z_n}\{d\}=\frac nd\mathbb{Z_n}\quad d=gcd(m,n),且构造的子群只有d个元素$

方法3

定理： $\begin{aligned}&\text{设}G\text{是群,}a\in G\text{,则}\\&<a>:=\{a^z\mid z\in Z\}\text{是由}a\text{生成的}G\text{的子群。}\end{aligned}$

子群构造子群

定理1：$\mathbb{H}_1$和$\mathbb{H}_2$是阿贝尔群$\mathbb{G}$的子群，则$\mathbb{H}:=\mathbb{H}_1\mathbb{H}_2$也是$G$的子群。
$H:=\mathbb{H}_1\mathbb{H}_2:=\{a_1*a_2|a_1\in \mathbb{H}_1,a_2\in \mathbb{H}_2\}$

扩展：以上定理中的2个子群扩展至任意多个子群，结论依然成立

定理2：$\mathbb{H}_1$和$\mathbb{H}_2$是群$\mathbb{G}$的子群，则$\mathbb{H}:=\mathbb{H}_1\cap \mathbb{H}_2$
也是$\mathbb{G}$的子群。(省流：子群的交集是子群)
$\mathbb{H}:=\mathbb{H}_1\cap \mathbb{H}_2:=\{a\mid a\in \mathbb{H}_1,a\in \mathbb{H}_2\}$

扩展：以上定理中的2个子群扩展至任意多个子群，结论依然成立

子群的并集未必是子群

定理3：$\mathbb{H}_1$和$\mathbb{H}_2$是群$\mathbb{G}$的非平凡子群，

则$\mathbb{G}:\neq\mathbb{H}_1\cup \mathbb{H}_2$

整数群的子群

定理1：$\mathbb{H}$是$\mathbb{Z}$的子群，则存在唯一的非负整数 $m$,使得$\mathbb{H}=\boldsymbol{m}\mathbb{Z}$

$\begin{aligned}m \mathbb{Z}&:=\{mz\mid z\in\mathbb{Z}\}\\&=\{0,\pm m,\pm2m,...\}\end{aligned}$

定理2：$m_1和m_2\text{是非负整数,则 }m_2|m_1\text{,当且}仅当,m_1\mathbb{Z}\subseteq m_2\mathbb{Z}。$

定理3：

$\mathbb{H}是\mathbb{Z_n}的子群,\\ 1.存在n的唯一正因子 m,使得H=m\mathbb{Z_n}.\ \\x不是n的因子 \Rightarrow x\mathbb{Z_n}=m\mathbb{Z_n},\quad\exists m\mid n.\ \\2.m_1和m_2是n的正因子,则 m_2|m_1,当且仅当,m_1\mathbb{Z}\subseteq m_2\mathbb{Z}。$

正规子群(normal subgroup)

定义：$设\mathbb{N}是群\mathbb{G}的子群，如果对于\forall a\in \mathbb{G},都有a\mathbb{N}=\mathbb{N}a,称\mathbb{N}为\mathbb{G}的正规子群$

阿贝尔群的子群都是正规子群

现在不懂没关系，往下你就知道了：正规子群本身是商群的一个元素，叫作平凡陪集，包含群的单位元，本身还是商群的单位元，被分类到N的元素，必然是同态核里的元素，自然映射的同态核就是正规子群N

陪集(coset)

定义：$\mathbb{H}$ 是群$\mathbb{G}$的子群，$a\in \mathbb{G}$,则

$a\mathbb{H}:=\{a*h|h\in \mathbb{H}\}$

称为 $\mathbb{H}$ 关于$a$在$\mathbb{G}$中的左陪集 (left cost)。同理，

$\mathbb{H}a:=\{h*a|h\in \mathbb{H}\}$

称为 $\mathbb{H}$ 关于$a$在$\mathbb{G}$中的右陪集 (right cost)。

陪集：$[a]_\mathbb{H}$
左陪集：$a\mathbb{H}$
右陪集：$\mathbb{H}a$

左右陪集相等不能说明满足交换律，只能说明对于右陪集的一个元素存在左陪集的一个元素使得两者相等

$b=ah或a=bh，\exists h\in \mathbb{H}\\a,b会被分类到同一个陪集$

$a\equiv b \pmod {\mathbb{H}}:a和b在同一个(由\mathbb{H}构造的)陪集里$

$\iff b\equiv a\pmod{\mathbb{H}}$

$\iff b \equiv a*h,\exists\ h\in \mathbb{H}$

$\iff b\in [a]_{\mathbb{H}}$

$\iff [a]_\mathbb{H}=[b]_\mathbb{H}$

性质

$a\in [a]_\mathbb{H}$
$[e]_\mathbb{H}=\mathbb{H}(平凡陪集)$
$a\in \mathbb{H}\iff[a]_\mathbb{H}=\mathbb{H}$
$[a]_\mathbb{H}=[b]_\mathbb{H}\Leftrightarrow a^{-1}*b\in \mathbb{H}\text{ (或 }b^{-1}*a\in \mathbb{H})$

$a\equiv b\pmod {\mathbb{H}}:a和b在同一个(由\mathbb{H}构造的)陪集里\\\iff b=a*h,\exists h\in \mathbb{H}\\\iff b\in [a]_\mathbb{H}$

$\begin{aligned} \ [a]_{n\mathbb{Z}}& =\{b\in \mathbb{Z}\mid b\equiv a\pmod{n}\} \\ &=\{b\in \mathbb{Z}\mid b=a+nz,z\in \mathbb{Z}\} \\ &=\{b\in \mathbb{Z}\mid b\equiv a\pmod{n}\} \\ &=[a],[a]\in\mathbb{Z}_n \end{aligned}$

$·\equiv ·\pmod {\mathbb{H}}是等价关系$

自反性
对称性
传递性

性质：任意两个陪集$[a]_\mathbb{H}$和$[b]_\mathbb{H}$之间存在双射，任意陪集$[a]_\mathbb{H}$和子群$\mathbb{H}$是等势的

阿贝尔群的陪集

性质1：$\mathbb{H}是阿贝尔群\mathbb{G}的子群，对于\forall a\in \mathbb{G}，有a\mathbb{H}=\mathbb{H}a\ ([a]_\mathbb{H})$

注意：$如果对于\forall a,都有a\mathbb{H}=\mathbb{H}a,则\mathbb{G}未必是阿贝尔群$

性质2：阿贝尔群的子群都是正规子群
性质3：阿贝尔群的任意子群都可以构造商群
性质4：阿贝尔群的子群构造的商群也是阿贝尔群

拉格朗日定理

定理：$\mathbb{G}是有限群，\mathbb{H}是\mathbb{G}的任意子群，\\则|\mathbb{H}|\mid|\mathbb{G}|$

$\begin{aligned}&\text{证明:设}\mathbb{H}\text{构造的陪集为}[a_1]_\mathbb{H},…,[a_n]_\mathbb{H}\text{,它们是}\mathbb{G}\text{的}\\&\text{划分。所以,}|\mathbb{G}|=\sum_{i=1}^n|[a_i]_\mathbb{H}|=\sum_{i=1}^n|\mathbb{H}|=n|\mathbb{H}|\end{aligned}$

商群

定义：$群(\mathbb{G}/\mathbb{N},*):群\mathbb{G}在模\mathbb{N}下的商群$

$集合\mathbb{G}/\mathbb{N}=\{[a]_\mathbb{N}|a\in \mathbb{G}\}$

$\mathbb{N}为正规子群，正规子群是啥？往上翻😾$

$二元运算[a]_\mathbb{N}*[b]_\mathbb{N}=[a*b]_\mathbb{N}$

正规子群是其中的平凡陪集，商群重点关注其中的非平凡陪集，元素不属于正规子群

整数群$\mathbb{Z}=\{0,\pm1,\pm2,…\}$

子群$n\mathbb{Z}=\{0,\pm n,\pm2n,…\}$

商群$\mathbb{Z}/ n\mathbb{Z}:$

$[ 0] _{n\mathbb{Z}}= \{ 0, \pm n, \pm 2n, . . . \}=[0]$
$[1]_{n\mathbb{Z}}=\{1,1\pm n,1\pm2n,…\}=[1]$
$[2]_{n\mathbb{Z}}=\{2,2\pm n,2\pm2n,…\}=[2]$
$\dots$
$[n-1]_{n\mathbb{Z}}=\{n-1,(n-1)\pm n,…\}=[n-1]$
$[n]_{n\mathbb{Z}}=\{n,n\pm n,n\pm2n…\}=[0]$
$[n+1]_{n\mathbb{Z}}=\{n+1,(n+1)\pm n,…\}=[1]$

$\dots$

$\mathbb{Z}/ n\mathbb{Z}=\{[0],[1],\dots \,[n-1]\}=\mathbb{Z_n}$

在整数群里，陪集和剩余类本质上是同一个东西，都是在等价关系上形成的等价类

商群的阶

$[\mathbb{G}:\mathbb{N}]商群\mathbb{G}/\mathbb{N}的阶$

定理1：$\mathbb{G}是有限群，\mathbb{N}是\mathbb{G}的正规子群，[\mathbb{G}:\mathbb{N}]=\frac{\mathbb{G}}{\mathbb{N}}$

定理2：$\mathbb{G}是有限群，\mathbb{N}是\mathbb{G}的正规子群，\mathbb{K}是\mathbb{N}的正规子群，[\mathbb{G}:\mathbb{K}]=[\mathbb{G}:\mathbb{N}][\mathbb{N}:\mathbb{K}]$

群同态(group homomorphism,名字可爱捏😸)

定义：设群$(\mathbb{G},*)$和群$(\mathbb{G}^\prime,\otimes)$,如果函数 $f:\mathbb{G}\to \mathbb{G}^\prime$ 对于

$\forall\boldsymbol{a},b\in \mathbb{G}$ ,都有

$f(a*b)=f(a)\otimes f(b),$

$f$为$(\mathbb{G},*)$到$(\mathbb{G}^\prime,\otimes)$的群同态。

性质

1.$f(e)=e^{\prime}\ (e和e^{\prime}分别是群G和G^{\prime}的单位元)$

2.$f(a^{-1})=f(a)^{-1},\quad\forall a\in G$

3.$H是G的子群\Longrightarrow f(H)是G^{\prime}的子群$
扩展：$H=G,\Rightarrow f(G)=Imf$

4.$H^{\prime}是G^{\prime}的子群\Rightarrow f^{-1}(H^{\prime})是G的子群$
扩展：$H^{\prime}={e^{\prime}}$

5.$f(a^m)=f(a)^m,\quad\forall a\in G,\forall m\in \mathbb{Z}$

同态像(homomorphic image)

$f:\mathbb{G}\to \mathbb{G}^\prime$

同态像$ Imf:=f(G):=\{f(a)|a\in G\},(同态像Imf是G^{\prime}的子群)$

同态核

同态核$Kerf:=\{a\in G|f(a)=e^{\prime}\},(同态核Kerf是G的子群)$

$(e^{\prime}$表示$G^\prime$的单位元)

定理：$f{:}G\to G^{\prime}\text{ 是群同态,则Ker }f\text{是正规子群}$

群同态的复合

定理：$f$是$(G,*)$到$(G^\prime,\otimes)$的群同态，$f^\prime$是$(G^\prime,\otimes)$到$(G^{\prime\prime}$,田)的群同态，则$f$和$f^\prime$的复合

$f^{\prime}\circ f{:}G\to G^{\prime\prime}也是群同态$

判断单一同态

定理1：

$f: G\to G^{\prime}是群同态,\forall a,b\in G,有\\f(a)=f(b)\Leftrightarrow a\equiv b\pmod {Ker f}$

定理2：

$f: G\to G^{\prime}是群同态,有\\f是单射 \Longleftrightarrow Kerf=\{e\}$

判断满同态

$f\text{是满同态}\Leftrightarrow Imf=G^{\prime}$

嵌入映射(inclusion map)

$H \to G$

$a\to f(a)=a$

子群元素直接映射到自身

子群到群的嵌入映射是个群同态
原像和像之间是一对一的，单射

单一同态：$f$是单射

自然映射(natural map)

$G \to G/N,(N是G的正规子群)$

$a\to f(a)=[a]_N$

自然映射的同态核就是正规子群N

满同态：$f$是满射

m次方映射(m-power map)

$G是阿贝尔群$

$G \to G$

$a\to f(a)=a^m$

$Imf=G^m$

$Kerf=G\{m\}$

雅可比映射(Jacobi map)

$\mathbb{Z}_n^* \to \{\pm 1\}$

$a\to J_n(a)=(\frac an)$

群同构(group isomorphism)

双射(单射&满射)
群同态

$G$与$G^\prime$同构，记为$G\cong G^\prime$
$G$与$G$之间的同构：自同构(group automorphism)

第一同构定理(first isomorphism theorem)

又称：基本同态定理 (FHT, fundamental homomorphism theorem)

定理：设群 $(G,*)$ 和群$( G^\prime , \otimes )$, $f{: }G\to G^\prime$ 是群同态($同
态核是Kerf，同态像是Imf$),则

$G/Kerf\cong Imf$ $\rho:[a]_{Kerf}\quad f(a)$

循环群(cyclic group)

孩子们，去往上回忆一下构造子群·方法3

定义：设$G$是群，$g\in G$,如果

$G=<g>,$

则称$G$是循环群，$g$是循环群$G$的生成元(generator)(可以有不止一个个生成元)。

有限循环群：群元素个数是无限的，同构于$\mathbb{Z}$

任意无限循环群都只有2个生成元
无限循环群：群元素个数是有限的,同构于$\mathbb{Z}_n$

定理：任意循环群都是阿贝尔群

定理：循环群的子群是循环群

定理：设$G$是循环群(生成元g)，$H$是其子群，则商群$G/H$是循环群(生成元$[g]_H$)

循环群的同构

1. $\begin{aligned}\text{对于无限循环群}G\text{的任意子群}H\text{,都存在唯一的非}\text{负整数}m\text{,使得}H=G^m。\end{aligned}$

2. $对于n阶有限循环群G的任意子群H,都存在n的唯一正因子m,使得H=G^m$

元素的阶(order)

定义：设$G$是群，$a\in G$,如果$n$是满足$a^n=e$的最小正整数，则称$n$是元素$a$的阶。

PS:存在无限阶的元素

性质$1:G$是群，元素$a$的阶是$n$ (a$^n=e)$,则$\forall m\in Z$,有$n|m\Leftrightarrow a^m=e_0$

性质$2:$有限循环群的阶是$n$,则生成元$g$的阶也是$n$,且群里元素 $g,g^2,g^3,…,g^n(=g^0=e)$各不相同。

性质$3:$正整数$d\mid n$, $n$阶有限循环群恰有唯一的$d$阶子群$$

性质$4: $n$阶有限循环群$ $,$ \forall k\in Z $,有$ g^k $的阶是$ \frac n{gcd(n,k)}$$

性质$5:$$n$阶有限循环群有$\phi(n)$ 个生成元。

性质$6:$$G$是有限群，元素$a$的阶是$|G|$的因子。

性质$7:$素数阶的群必然是有限循环群

性质$8: $$\begin{aligned}G\text{是}n\text{阶有限循环群,}d\text{是}n\text{的正因子,}G\text{里的}d\text{阶}\text{元素一共有}\phi(d)\text{个。}\end{aligned}$

原根(primitive root)

不妨先去复习一下卷一(数论)中的乘法阶概念

$g一般表示生成元$

定义：$g\in\mathbb{Z},gcd(g,n)=1$,如果$ord_n(g)=\phi(n)$,称$g$是模$n$下的原根。

$g$是模$n$下的原根，则$g^{ord_n(g)}\equiv g^{\phi(n)}\equiv1\left({\mathrm{mod~}}n\right)$。

原根的阶是$\phi(n)$, $Z_n^*$ 的阶也是$\phi(n)\Longrightarrow$原根是 $Z_n^*$ 的生成元 $\Longrightarrow\mathbb{Z}_n^*$ 是循环群

$Z_n^*$$里，“元素的阶”就是元素的“乘法阶” 模$n$下存在原根的话，$$Z_n^*$$是循环群，“生成元”就是“原根” $$(n=1,2,4,p^e,2p^e)$

$\forall k\in\mathbb{Z}\text{,}g^k\text{的乘法阶是 }\frac{\phi(n)}{gcd(\phi(n),k)}$

$Z_p^*\text{里,}\forall k\in Z\text{,}g^k\text{的乘法阶是}\frac{p-1}{gcd(p-1,k)}$

模n下原根一共$\phi(\phi(n))$个

$\mathbb{Z}_p^*\text{的生成元一共}\phi(p-1)\text{个}$

原根存在的条件

设$p$是奇素数，$e$是正整数
$n=1,2,4,p^e,2p^e$ 时，模$n$下存在原根

$Z_p^*\text{里,}\forall k\in Z\text{,}g^k\text{是原根}\Leftrightarrow gcd(p-1,k)$

寻找原根(生成元)的算法

$\begin{aligned}&\forall a\in\mathbf{Z}_n^*\Longrightarrow ard_n(a)|\phi(n)\\&a\text{是原根}\Longrightarrow ord_n(a)=\phi(n)\\&\text{设 }\phi(n)=p_1^{e_1}...p_r^{e_r}\\&a\text{不是原根}\Longrightarrow\exists d|\phi(n),d<\phi(n),a^d=1 \pmod n\\&\Longrightarrow\exists p_j,d|\frac{\phi(n)}{p_j} \Longrightarrow\exists q,dq=\frac{\phi(n)}{p_j}\\&a^d\equiv1 \pmod n\Longrightarrow a^{\frac{\phi(n)}{p_j}}\equiv a^{dq}\equiv(a^d)^q\equiv1 \pmod n\end{aligned}$

算法1：

step1.$因子分解\phi(n),求出其各个素因子 p_1,…,p_r$

step2.任选$a\in\mathbb{Z}_n^*$

step3.$if\ a^\frac{\phi(n)}{p_i} \not\equiv1(mod\: n),i=1,…,r$

output a

else goto step2.

算法2: $\text{如何找}Z_p^*\text{的原根(生成元)}\\\text{设 }p\text{ 是奇素数,}\phi(p)=p-1=p_1^{t_1}...p_r^{t_r}$

for $i=1$ to $r$

{

do{

任选$a\in Z_p^*$

} while $(a^{\frac{p-1}{p_i}}\equiv1$ (mod $p))$

$c_i\equiv a^{p_i{\frac{p-1}{t_i}}}\pmod p$

}

output $\prod_{i=1}^rc_i\pmod p$

定理1：设$G$是群，$c\in G$,对于某个素数$p$和整数$t\geq1$,如果
$c^{p^t}=e$ 但 $c^{p^{t-1}}\neq e$,则$c$的阶是$p^t$。

定理2：设$G$是群，$c_1,c_2\in G$,$c_1,c_2$的阶分别为$m_1,m_2$,且$gcd(\boldsymbol{m}_1,\boldsymbol{m}_2)=1$,则 $c_1*c_2$ 的阶是$m_1m_2$。

离散对数(discrete logarithm)

$n=1,2,4,p^e,2p^e$时，存在原根 (设为$g),Z_n^*$是循环群

定义：$gcd(a,n)=1$,必存在唯一整数$x(0\leq x<\phi(n))$
有 $a\equiv g^{x}\pmod n$,则称$x$是以$g$为底的$a$模$n$的指标
(index)或离散对数(discrete logarithm)。

简记为：$x=log_g(a)$

$1\equiv g^0(modn)\Longrightarrow log_g(1)=0\\g\equiv g^1(modn)\Longrightarrow log_g(g)=1$

定理：$a\equiv g^r\pmod n\Leftrightarrow log_g(a)\equiv r\pmod{\phi(n)}$

$\begin{aligned} \text{设 }x=log_g(a), &\text{则 }a\equiv g^x(\mathrm{mod~}n) \\ a\equiv g^r (mod n) &\Leftrightarrow g^x\equiv g^r\mathrm{~}(mod\mathrm{~}n) \\ &\Leftrightarrow x\equiv r\pmod{\phi(n)} \\ &\Leftrightarrow log_g(a)\equiv r\pmod{\phi(n)} \end{aligned}$

性质1:$log_g(ab)\equiv log_g(a)+log_g(b)\pmod {\phi(n)}$

性质2:$log_g(a^m)\equiv m\times log_g(a)\pmod {\phi(n)}$

性质3:$log_h(a)\equiv log_h(g)\times log_g(a)\pmod {\phi(n)}$

离散对数问题(DLP,discrete logarithm problem)

定义：设$G$是循环群，$g\in G$是生成元，对于$y\in G$和正
整数$x$,有 $y=g^x$,则离散对数问题定义为：
给定$y$和$g$,求$x (=log_g(y))$。

目前无高效算法

RSA的模数

RSA的所有计算都是在$\mathbb{Z}_n^*$上进行的

$n=pq$

$\phi(n)=\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$

$\forall a\in \mathbb{Z}_n^*,ord_n(a)\mid (p-1)(q-1)$

$设\lambda(n)=lcm(p-1,q-1)<(p-1)(q-1)$

$\mathbb{Z}_n^*没有原根（生成元），不是循环群$

定理： $\mathbb{Z}_n^*中任意元素的阶都是\lambda(n)的因子$

$\mathbb{Z}_n^*$$中没有原根(生成元)，不是循环群 $$Z_p^*$$和$$Z_q^*$$都是循环群 (因为$p$和$q$是素数，满足五种情况之一) $$\mathbb{Z}_p^*$$里元素最大阶为$p-1$ $$Z_q^*$$里元素最大阶为$q-1$ $$\mathbb{Z}_n^*$$里元素最大阶为$\lambda(n)$ **结论**：$$Z_n^*$$的阶是$\phi(n)$,元素最大阶为$\lambda(n)$ $$\forall a\in Z_n^*$$,由$ord_p(a)$和$ord_\mathfrak{q}(a)$如下计算$ord_n(a):$ $$ord_n(a)=lcm(ord_p(a),ord_q(a))$