FHE学习笔记 #1 部分抽象代数名词
本文最后更新于：2022年11月16日 下午
群 Group
对于非空集合 \(G\)，\(\circ\) 是它的一个代数运算，如果满足以下条件：
结合律成立，即对 \(G\) 中任意元素 \(a, b, c\) 都有
\[ (a \circ b) \circ c=a \circ(b \circ c) \]
\(G\) 中有元素 \(e\)，叫做 \(G\) 的左单位元，它对 \(G\) 中每个元素 \(a\) 都有
\[ e \circ a=a \]
对 \(G\) 中每个元素 \(a\)，在 \(G\) 中都有元素 \(a^{-1}\)，叫做 \(a\) 的左逆元 (Inverse)，使
\[ a^{-1} \circ a=e \]
则称 \(G\) 对代数运算 \(\circ\) 作成一个群。
群是一个满足封闭性、满足结合律、有单位元、有逆元的二元运算的代数结构。
单位元，也叫幺元，英文 Identity Element。
半群 Semi-group
设 \(S\) 是一个非空集合，如果它有一个代数运算满足结合律，则称 \(S\) 是一个半群。
子群
设 \(H\) 是群 \(G\) 的一个非空子集，如果 \(H\) 对于 \(G\) 的运算也构成群，则称 \(H\) 为 \(G\) 的子群，记作 \(H<G\)
设 \(m \in \mathbb{N}\)，则 \(m \mathbb{Z}=\{m n \mid n \in \mathbb{Z}\}\) 是 \(\mathbb{Z}\) 的子群
\(\mathbb{Z}\) 的任何子群都形如 \(m \mathbb{Z}, m \in \mathbb{N}\)
设 \(G\) 为群，\(a \in G\)，记 \(a^0=e\)
对 \(k \in \mathbb{N}\)，令 \(a^k=a \cdot a^{k-1},a^{-k}=\left(a^{-1}\right)^k\)
对 加法群 \(G\)，\(a^n\) 通常记为 \(n a\)
\(\langle a\rangle=\left\{a^n \mid n \in \mathbb{Z}\right\}\) 是 \(G\) 的子群，称为 \(a\) 生成的子群，子群的阶也称为 \(a\) 的阶
更一般地，设 \(S\) 是群 \(G\) 中一个非空子集，令 \(S^{-1}=\left\{a^{-1} \mid a \in S\right\}\)，记
\[ \langle S\rangle=\{x_1, \ldots ,x_m \mid m \in \mathbb{N}, x_1, \ldots, x_m \in S \cup S^{-1}\} \]
\(\langle S\rangle\) 是 \(G\) 的一个子群，称为 \(S\) 生成的子群。
陪集 Coset
设 \(H\) 是群 \(G\) 的一个子群，\(a \in G\)。则称群 \(G\) 的子集
\[ a H=\{a x \mid x \in H\} \]
为群 \(G\) 关于子群 \(H\) 的一个左陪集。而称
\[ H a=\{x a \mid x \in H\} \]
为群 \(G\) 关于子群 \(H\) 的一个右陪集。
以上叙述中都把群 \(G\) 中的运算记作乘法，并且省去了运算符。
如果群 \(G\) 中的运算记作加法，则以 \(a\) 为代表的左陪集应该记作
\[ a+H=\{a+h|h\in H\} \]
同余类 Congruence Class（或剩余类 Residue Class）
模 \(m\) 同余是一个等价关系，由此确定了整数上的一个分类
对于 \(\forall a\in [0,m-1]\)，集合 \(a+m\mathbb{Z}\) 中的所有数模 \(m\) 同余，这个集合叫做 \(a\) 的等价类，也叫同余类，记作 \([a]\;\text{or}\;\overline{a}_m\)
满足：
\[ \mathbb{Z}=(0+m \mathbb{Z}) \cup(1+m \mathbb{Z}) \cup \cdots \cup((m-1)+m \mathbb{Z})=\{\overline0+\overline1+\cdots+\overline {m-1} \} \]
最小剩余系（Residue Systems）
每个等价类通常用他们的最小非负元素来表示，这些最小代表的集合就是模 \(m\)所得的余数域，也叫最小的剩余系 \(\mathbb{Z}_m=\{0,1,\cdots,m-1\}\)
商集 Equivalence Set
商集是集合的一个划分，设 \(\sim\) 为集合 \(S\) 的一个等价关系，则 \(S/\sim\) 称为商集，是等价类构成的集合。
正规子群 Normal Subgroup 和商群 Quotient Group
设 \(H\) 是群 \(G\) 的一个子群，如果 \(\forall a\in G,~aH=Ha\)，则称 \(H\) 为 \(G\) 上的正规子群，记作 \(H\lhd G\)
设 \(H\) 是群 \(G\) 的一个正规子群，定义 \(G/H=\{aH|a\in G\}\)，对于陪集乘法
\[ (aH)(bH)=a(Hb)H=(ab)HH=abH \]
构成一个陪集为元素的群，叫做商群
由于 \(\{\mathbb{Z} ;+\}\) 是交换群，故其任一子群 \(m \mathbb{Z}\) 是 \(\mathbb{Z}\) 的正规子群，所以有商群：
$$
\[\begin{aligned} &\mathbb{Z} / m \mathbb{Z}= \begin{cases}\mathbb{Z}, & m=0 \\ \{\overline{0}, \overline{1}, \ldots, \overline{m-1}\}, & m \neq 0\end{cases}\\ &m\mathbb{Z}=\overline 0\\ &\overline a=a+m\mathbb{Z}=a\circ m\mathbb{Z} \end{aligned}\]$$
注意商群元素之间的运算为模 \(m\) 加法，这个群通常简记为 \(\mathbb{Z}_m\)（但是这个记号容易弄混），称为模 \(m\) 的剩余类加群。
当商群元素间的运算为模 \(m\) 乘法，这个商群记为 \((\mathbb{Z} / m \mathbb{Z})^\times\)，不同于加群，这个群的大小为欧拉函数 \(\varphi(m)\)（英文：Euler's totient Function），即集合 \(\{1,\cdots,m-1\}\) 中与 \(m\) 互质的数的个数，则
$$
\[\begin{aligned} &(\mathbb{Z} / m \mathbb{Z})^\times= \{\overline p|~\overline p\in(\mathbb{Z} / m \mathbb{Z})^+,\gcd(p,m)=1\}, m \neq 0\\ &\overline 1 \text{~is~the~identity}\\ &\overline a\times \overline b=\overline{a\times b} \end{aligned}\]$$
Multiplicative group of integers modulo n - Wikipedia
http://www.math.columbia.edu/~rf/numbertheory2.pdf
其中单位元为 \(\overline 1\) ，一个元素 \(\overline a\) 的最小非负代表数 \(a\) 的逆元 \(a^{-1}\) 要满足同余方程 \(aa^{-1} \equiv 1(\mathrm{mod}~m)\)，即方程 \(ax + my= 1\) 要有整数解 \(x,y\)。
根据裴蜀（贝祖）定理的推论，\(𝑎,𝑏\) 互质的充要条件是存在整数 \(𝑥,𝑦\) 使 \(𝑎𝑥+𝑏𝑦=1\)，所以 \(\mathbb{Z}_m^\times\) 中的最小非负代表数都是和 \(m\) 互质的数，否则没有逆元。
环 Ring
设非空集合 \(R\) 有两个代数运算，一个叫做加法（一般用 \(+\) 表示），另一个叫做乘法。如果：
\(R\) 对加法作成一个交换群
\(R\) 对乘法满足结合律（即半群）
乘法对加法满足左右分配律：
\[ \forall a,b,c\in R,\quad a(b+c)=a b+a c, \quad(b+c) a=b a+c a \]
则称 \(R\) 对这两个代数运算作成一个环。
若对乘法满足交换律，则称为可换环 Commutative Ring
若乘法有单位元，则称为幺环
后面的概念比较抽象，会在后面大量涉及，会经常更新，还是建议用 wolai 观看
https://shaih.github.io/columbia6261/lecture13-NTRU.pdf
理想 Ideal
设 \(R\) 为环，\(I\) 为 \(R\) 的子环，如果 \(I\) 满足条件「\(a \in I, x \in R \Rightarrow x a \in I\)」，则称 \(I\) 为 \(R\) 的左理想
如果 \(I\) 满足条件「\(a \in I, y \in R \Rightarrow a y \in I\)」，则称 \(I\) 为 \(R\) 的右理想
若一个子环既是左理想，又是右理想，则称为双边理想 Two-sided Ideal
主理想 Principal Ideal
主理想是环 \(R\) 的一个由单个元素 \(a\) 生成的理想 \(I\)，分为左/右/双边主理想
左主理想严谨表示为（右类似）：
\[ I=Ra=\{ra|r\in R\} \]
双边主理想严谨表示为（没太看懂，国内博客好像不太一致）：
\[ I=R a R=\left\{r_{1} a s_{1}+\cdots+r_{n} a s_{n}| r_{1}, s_{1}, \ldots, r_{n}, s_{n} \in R\right\} \]
对于可换环，以上三种主理想是一样的，可以记由 \(a\) 生成的环为 \(I=\langle a\rangle\; \text{or} \;I=(a)\)
\(\mathbb{Z}\) 的主理想就是 \(\langle m \rangle = m\mathbb{Z}\)
商环 Quotient Ring（或剩余类环 Residue Class Ring）
设 \(R\) 是一个环，\(I\) 是 \(R\) 的理想。考虑加法群 \(\{R ;+\}\) 对于子群 \(I\) 的商群 \(R / I\)，将 \(a \in R\) 所在的等价类记为 \(a+I\)。在 \(R / I\) 上定义乘法如下:
\[ (a+I)(b+I)=a b+I . \]
则集合 \(R / I\) 对于商群的加法以及上述乘法运算构成一个环，称为 \(R\) 对于理想 \(I\) 的商环。
\(\mathbb{Z}/m\mathbb{Z}\) 就是一个商环，当 \(m>0\) 时，称 \(\mathbb{Z}/m\mathbb{Z}\) 为 \(\mathbb{Z}\) 模 \(m\) 的剩余类环。