FHE之代数基础（一）群环域、多项式

非原创声明

本篇blog大部分为参考下文所作，其中进阶部分为个人总结。

基础

代数系统

代数是数学的其中一门分支，主要由初等代数和抽象代数组成，初等代数学主要研究方程组，而抽象代数则是研究代数系统上的运算和公理。代数系统主要有两部分组成：

• 成分：运算及其载体，即运算和运算的对象
• 公理：运算性质，即交换律、结合律等算律

举例而言，小学中学习的1+2=3，其中运算就是加法（这里用+表示），加法运算的对象是1、2，由于加法运算需要两个运算对象，因此加法也是一种二元运算。很明显，1+2=2+1，因此运算对象可以交换在运算中的位置，因此满足交换律，这就是加法运算的基本算律。

其中公理是很好理解的，但代数系统的成分容易理解但不好表达，下面从中抽象出一些共性，并用数学语言进行概况有：

• 运算对象：用集合表示运算对象和运算的结果，比如集合A、B、X、Y等
• 运算：用$+, -,\times, \cdot, \circ$等运算符号表示运算，它们不具有任何一种运算，仅仅是一种符号表示。

因此我们可以给出一些运算的定义：

• n元运算的数学定义：给定集合$A_1, A_2, ..., A_n$和集合$B$，那么映射$f:A_1\times A_2\times ...\times A_n\rightarrow B$即表示一个n元运算。

根据运算所需的运算对象的个数，运算称为0元运算、一元运算、二元运算等。

而讨论最多的就是下面的一种二元运算：

• 集合A上的运算：设A为集合，称二元运算$f:A\times A \rightarrow A$为集合A上的二元运算。进一步地，若A​中任何元素都可参与运算，且结果属于集合A，那么称运算$f$是封闭的

设$+, \times$是集合A上的二元运算，称为加法和乘法，那么有下面的运算规律和特异元素（指单位元和逆元）：

• 交换律：若$\forall a, b\in A$有$a+b=b+a$，则称有加法交换律，同理有乘法交换律
• 结合律：若$\forall a, b, c\in A$有$a+(b+c)=(a+b)+c$，则称有加法结合律，同理有乘法结合律
• 消去律：若$\forall a, b, c\in A$有$a+b=a+c\Rightarrow b=c$，则称有加法消去律，同理有乘法消去律
• 乘法对加法的分配律：若$\forall a, b, c\in A$有$a\times (b+c)=a\times b+a\times c$，则称乘法对加法具有分配律
• 单位元：单位元$e$满足$e\in A,\;\forall a\in A$有$a+e=e+a=a$，则称有加法单位元，同理有乘法单位元
• 逆元：对于$x\in A$，$\exists y \in A$使得$x+y=e$，则称有$x$有加法逆元$y$（$y$的加法逆元为$x$），同理有乘法逆元

值得注意的是，算律、单位元和逆元是针对运算来说的，如果代数结构中有多种运算，那么对于不同的运算可能就有不同的运算规律和单位元和逆元。

下面就基于上述概念介绍群环域等基本概念。

群、环、域基本概念

群

群（Groups）是一种具有一个二元运算的代数系统，通常记作$<G, \circ>$，简记为$G$，其满足以下条件：

• 封闭性：$\forall a, b \in G$，都有$a\circ b\in G$
• 结合律：$\forall a, b, c \in G$，都有$a\circ (b\circ c) = (a\circ b)\circ c$
• 单位元：$\exists e\in G$使得$a\in G$，有$a\circ e=e\circ a=a$，单位元也称幺元
• 逆元：$\forall a\in G$，$a$都存在一个逆元$a^{-1}$使得$a\circ a^{-1}=e$

由于有逆元，因此群也满足消去律。举个例子，整数集合上的加法运算构成的代数系统$<Z, +>$就是一个群，因为整数和整数相加也是整数，整数加法满足结合律，其单位元为0，任意元素的逆元是其相反数。

进一步地，在群的基础上，如果增加一些条件那么就可以形成具有更多良好性质的群。

• 半群：若$<G, \circ>$只满足封闭性和结合律，那么$<G, \circ>$是一个半群
• 含幺半群：若$<G, \circ>$只满足封闭性、结合律和单位元，那么$<G, \circ>$是一个含幺半群（也称幺半群）
• 有限群和无限群：若一个群的元素是有限的，则该群称为有限群，并且群的阶等于群中元素的个数，否则称该群为无限群。
• 交换群：若对于群中任意运算还满足交换律，那么该群称为交换群
• 循环群：记群中的幂运算$a^n=a\circ a\circ ...\circ a$（n个a相乘），且有$a^0=e, a^{-n}=(a^{-1})^n$，那么如果群G中的每个元素都是有一个固定元素$a\in G$的幂，那么称群G​是循环群

显然循环群是交换群，但循环群可能是有限群，也可能是无限群。

环

环（Rings）是一个具有两个二元运算（通常称为加法和乘法）的代数系统，常记作$<R, +, \times>$，简记为$R$，其满足以下条件：

• $<R, +>$是加法交换群，此时用$0$表示其加法单位元，$-a$表示环中元素$a$的加法逆元
• $<R, \times>$是半群
• 乘法对加法具有分配律：$\forall a, b, c\in R$有$a\times (b+c)=a\times b+a\times c$

由于加法一定有逆元，因此通过加法可以定义减法：$a-b=a+(-b)$，同时若不会引起歧义，那么环中的乘法$a\times b$也可记为$ab$。进一步地，如果环还满足其他性质，那么可以形成具有更多性质的环：

• 交换环：若环$R$中的乘法满足交换律，那么环$R$是一个交换环

• 整环：如果环$R$满足下面两个条件，那么环$R$称为整环：

  • 乘法单位元：环中的乘法有单位元，即$<R, \times>$是含幺半群，此时其单位元记作$1$

  • 无零因子：环中元素$a,b$称为零因子当且仅当$a,b\ne 0$但$ab=0$，因此环中无零因子则有$\forall a, b \in R$，若$ab=0$，那么必有$a=0$或者$b=0$（此处的$0$是加法的单位元）

域

域（Fields）也是一个具有两个二元运算（通常称为加法和乘法）的代数系统，常记作$<F, +, \times>$，简记为$F$，其满足以下条件：

• $<F, +>$是加法交换群，此时用$0$表示其加法单位元，$-a$表示环中元素$a$的加法逆元
• $<F^*, \times>$是乘法交换群，其中$F^*$包括$F$中的所有非零元素，$F^*=F-\{0\}$，此时用$1$表示乘法单位元，$a^{-1}$表示元素$a(a\ne0)$的乘法逆元
• 乘法对加法具有分配律：$\forall a, b, c\in R$有$a\times (b+c)=a\times b+a\times c$

有理数集、无理数集以及复数集是我们熟悉的代数系统，它们在普通的加法和乘法两种运算下都构成域。

小结

可以看到群是最基础的代数结构，而环是由加法交换群和乘法半群构成的，进一步地，域是由加法交换群和乘法交换群（除0以外）构成的。

读者可能会问，群、环和域有什么用？下面举一个简单的例子来说明。假如在研究下表所示的集合$S=\{a, b\}$上的代数结构，其加法和乘法的定义如下（用算术表表示）：

  如果在集合S上可不可以用减法，加法和乘法有没有交换律等是需要的回答的问题，那么此时如果发现$<S, +, \times>$是环，那么一切都迎刃而解了。

另外，由于不是所有常见的运算都可以有加、减、乘、除、乘方、开方等运算，那么在遇到一个新的结构时，如果赋予它们一些好的性质是很重要的，比如学习矩阵运算时，加法是需要自己定义的，乘法是自己定义的，由此会发现矩阵加法满足交换律，但是矩阵乘法不满足，实际上会发现n阶实数矩阵对于加法和乘法构成环，那么n阶实数矩阵上的运算就可以利用许多环的运算了。

由此得出一个结论：

• 群环域没有定义哪一种代数结构，而是定义了一类代数结构，数学工作者只需要研究这一类代数结构的共性。当某种特定的代数结构满足群、环、域的条件时，那么该代数结构自然而然地具备群、环、域的良好性质。

下图总结了群、环、域的基本性质，这里是按照群、环、域满足的条件来介绍的。

进阶

环的拓展概念

剩余类（同余类）环

设$Z_q=\{\overline{0},\overline{1},\cdots,\overline{q-1\}}$是整数模$q$的同余类集合。

• 加法：模q加法，$\overline{a}+\overline{b}=\overline{a+b}$
• 乘法：模q乘法，$\overline{a}\cdot\overline{b}=\overline{ab}$

显然，$(Z_q,+,\cdot)$是有单位元的交换环，称为整数模$q$的同余类（或剩余类）环

子环

若$S$为环$R$的一个非空子集，且$S$关于$R$的运算构成环，则称$S$为$R$的一个子环，$R$为$S$的一个扩环。

$S$为$R$的子环的充要条件为：

$\forall a,b \in S,a+b\in S ,ab\in S$

理想

设$I$为环$R$的非空子集，若$I$满足：

• $\forall r_1,r_2 \in I,r_1+r_2\in I$
• $\forall r\in I,s \in R, sr\in I, rs\in I$

则称$I$为$R$的一个理想(ideal)

商环

若$I$是环$R$的一个理想

记$\overline{a}=a+I=\{a+x|x\in I\},R/I=\{\overline{a}|a\in R\}$

则$(R/I,+,\cdot)$是一个环，称其为$R$关于$I$的商环，或$R$模$I$的同余类环

环同态

设$R$和$S$是两个环，若$\exists \varphi:R\to S:r\mapsto \varphi(r)$，满足：

• $\forall r_1,r_2 \in R, \varphi(r_1+r_2)=\varphi(r_1)+\varphi(r_2)$
• $\forall r_1,r_2 \in R, \varphi(r_1r_2)=\varphi(r_1)\varphi(r_2)$

则称$\varphi$是$R$到$S$的一个环同态(ring homomorphism)

环同构

若环同态中的$\varphi$是一个双射，则称$\varphi$是$R$到$S$的一个环同构(ring isomorphism)，并称两个环是同构的，记为$R\cong S$。

若$\varphi:R\rightarrow R$为同构映射，则称$\varphi$是一个$R$到$R$的自同构(automorphism)

高级

有限域

若 域中元素个数（称为域的阶） 有限，则称该域为有限域，否则称为无限域

有限域通常记作$GF(q^n)$，符号$G$是为了纪念群论的创立者Galois，符号F是域Fields，因此有限域称为Galois域。

构造

当$q$为素数时，同余类环$<Z_q, \oplus_q, \otimes_q>$，为一个有限域。

• 模q加法：通常用$\oplus_q$表示，$a\oplus_q b=(a+b)\mod q$

• 模q乘法：通常用$\otimes_q$表示，$a\otimes_q b=(a\times b)\mod q$

• $n=1$时的有限域$GF(q)$，由上面的讨论可以很容易构造该有限域

• $n>1$时的有限域$GF(q^n)$，其中$GF(2^n)$在密码学中有重要的应用

多项式环

环上的多项式环

记$a_0,a_1,\cdots,a_n\in R$，则称形如$f(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0=\sum_{i=0}^n{a_ix^i}$的表达式为$R$上多项式。环$R$上所有关于$x$的多项式构成的集合记为$R[x]$

• 加法：多项式加法
• 乘法：多项式乘法

此时$(R[x],+,\cdot)$称为环$R$上的多项式环。

域上的多项式环

当以上环$R$为一个域时，称$R[x]$为域上多项式环，记为$F[x]$。

我们一般只研究有限域上的多项式环。设有限域$GF(q)$，其上有集合$Z_q=\{0, 1, 2, ..., q-1\}$，定义在$Z_q$上的多项式有

$f(x)=a_{n-1}x^{n-1}+...+a_1x+a_0=\sum_{i=0}^n{a_ix^i}\qquad\forall i\in\{0, 1, 2, ..., n-1\},a_i\in Z_q$

设集合S是所有定义在$Z_q$上的多项式集合，即

$S=\{f(x)|f(x)=a_{n-1}x^{n-1}+...+a_1x+a_0=\sum_{i=0}^n{a_ix^i}\qquad\forall i\in\{0, 1, 2, ..., n-1\},a_i\in Z_q\}$

可知集合$S$中共有$q^n$个元素，其包含了所有次数小于$n$次的多项式。

特别地，我们还会研究有限域上的多项式商环：

在有限域$GF$上的多项式环$F(x)$中，对$\forall f(x)\in F[x]$，有$I=\{g(x)f(x)|g(x)\in F[x]\}$为$F[x]$的理想。

在有限域$GF$上的多项式环$F(x)$中，$f(x)=a_{n-1}x^{n-1}+...+a_1x+a_0=\sum_{i=0}^n{a_ix^i}\qquad\forall i\in\{0, 1, 2, ..., n-1\}\in F[x]$，$I=\{f(x)\}$，则$F[x]/I=F[x]/f(x)=\{\sum_{i=0}^n{b_ix^i}+I|b_0,b_1,\cdots,b_{n-1}\in F\}$

称为有限域上的多项式商环。

多项式的带余除法

对于域$F$中的$n$次多项式$f(x)$和$m$次多项式$g(x)$（$m\le n$），则用$g(x)$除$f(x)$会得到一个商式$q(x)$和一个余式$r(x)$，其满足

$$f(x)=q(x)g(x)+r(x) \\ \partial(f(x))=n, \partial(g(x))=m, \partial(q(x))=n-m，0\le \partial(r(x))\le m-1$$

其中$\partial(f(x))=n$表示$f(x)$的最高次数为$n$（即$f(x)$中$x$的最高次幂为n）。

通常将余式$r(x)$记作$r(x)=f(x)\mod g(x)$，若余式为0则称$g(x)$整除$f(x)$。

既约多项式

若域$F$中多项式$f(x)$不能表示域$F$上任两个多项式$g_1(x)$和$g_2(x)$的乘积（$g_1(x)$和$g_2(x)$在域F中，且次数都小于$f(x)$的次数），那么称多项式$f(x)$为既约多项式，也称不可约多项式、素多项式。

该概念类似整环中素数的概念。

多项式的模运算

针对域上的多项式商环而言。

• 运算中，系数运算以q为模数，即遵循有限域$Z_q$上的运算规则
• 若乘法运算的结果是次数大于n-1的多项式，那么须将其除以某个次数为$n$的既约多项式$m(x)$并取余式。对于多项式$f(x)$，这个余数表示为$r(x)=f(x)\ mod\ m(x)$

良好性质