密码学数学基础之环论基础

群是非常简单的代数结构，因为它只有一种运算。大量的数学对象和现实应用都会遇到不止一种运算的情况。
环是一种比群更复杂的、包含两个运算的代数结构，有着更为广阔的应用

环的定义

定义1：设非空集合R上有两个代数运算，分别称为加法“+”和乘法“∙”。如果这两个运算满足以下三组条件，则称R为环。
（1） $(R, +)$ 是一个交换群，其中加法零元用0来表示，元素 $a$ 的负元用 $-a$ 表示。
（2） $(R, \cdot)$ 满足封闭性和结合律，即对于R中的任意三个元素a,b,c， $a\cdot b$ 还在R中，且 $(a\cdot b)\cdot c=a\cdot(b\cdot c)$ 。

（3）乘法对于加法有左分配律和右分配律，也就是说对于R中的任意三个元素a, b, c, 有： $a \cdot(b + c)=a \cdot b + a \cdot c$ ， $(b+c)\cdot a =b \cdot a + c \cdot a$ 。

环一般记作 $(R, +, \cdot)$ ，其中两个元素相乘 $a\cdot b$ 也可以简写为 $ab$ 。

定义2 如果环R的乘法可换，即对于R中的任意元素a和b，一定有ab=ba，则称R为可换环（或者交换环），否则称为不可换环（或者非交换环）
显然如果已知R是交换环，则其左分配律和右分配律是一致的，证明时只需要证明其中一个即可。
定义3 如果环 $R$ 的元素个数有限，则称 $R$ 为有限环，否则称为无限环，环的元素个数称为环的阶，记作 $|R|$ 。
例1 常见的几个数集Z, Q, R, C对于数的加法和乘法都构成了环。
例2 实数集R上全体多项式组成的集合 $R[x]$ 对于多项式的加法和乘法构成一个环。
例3 实数集R上的全体n阶方阵组成的集合记作 $M_{n}(R)$ ，它对于矩阵的加法和乘法构成一个非交换环。
定义4 如果环R中存在乘法单位元，即存在特殊的元素1，对于R中的任意元素a，满足 $1a=a1$ ，称1为单位元，有时候称作幺元。
含单位元的环也称为含幺环。

定义5 设R是含幺环，如果对于元素a，存在元素b，使得ab=ba=1，则称b为a的逆元，记作a逆，此时称a为可逆元。
注意环中关于可逆性和逆元的定义特指乘法中的可逆性和逆元。

环的零因子

定义6 若环R中存在非零元a和b，满足条件ab=0，则称a为左零因子，b为右零因子。
环中的可逆元一定不是零因子。因为如果a为环R的可逆元，且ab=0，则等式两边同时左乘a在环R中的逆元a逆，就可以得到b=0，所以a一定不是零因子。
等价描述：零因子也一定不是可逆元。

例4 两个典型的无零因子环：整数环 $Z$ ；多项式环 $R[x]$ 。

三类特殊的环

定义7 无零因子的含幺交换环称为整环。整数环 $Z$ 和多项式环 $R[x]$ 都是整环。

定义8 设R为一个环且R的元素个数大于1，如果R中有单位元1并且任一非零元均有逆元，则称R为除环。可交换的除环称为域。

有理数集Q，实数集R和复数集C都是域，一般将其称为数域。
整数集Z存在不可逆元，所以不是除环，也不是域。
除环和域都没有零因子。这是因为除环和域中的任意非零元都可逆，而所有可逆元都不是零因子。

三类特殊环之间的关系：

如果一个环是域，那它一定既是整环又是除环；
如果一个环既是整环也是除环，那它一定是域。

如果F是一个域，则可以在F上定义减法： $a-b=a+(-b)$ ，也可定义除法： $\frac{a}{b}=ab^{-1}$ 。

要求b不为0。
因此在域中可以进行“加、减、乘、除（其中除元素不为0）”的四则混合运算，这种运算规则非常类似于数域Q、R、C中的相应运算。

剩余类环

定义9 在整数模n剩余类 $Z_{n}$ 上定义加法和乘法运算：
$\bar{i}\oplus \bar{j}=\bar{(i+j)modn}$

$\bar{i}\circ \bar{j}=\bar{ijmodn}$

可以验证 $Z_{n}$ 在这样的加法和乘法下构成了一个环，称为整数模n剩余类环。
定理1 对于整数模n剩余类环 $Z_{n}$ 中的非零元，当m与n互素的时候， $\bar{m}$ 可逆，如果m与n不互素，则 $\bar{m}$ 为零因子。

证明如果整数m与n互素，即 $(m, n)=1$ ，此时存在整数s,t使得 $sm+tn=1$ ，两边同时模n，可以得到 $sm\equiv 1(modn)$ 。
所以在 $Z_{n}$ 中 $\bar{s}\circ\bar{m}=\bar{1}$ ，也就是说 $\bar{m}^{-1}=\bar{s}$ 。
如果整数m与n不互素，则 $(m,n)=d>1$ ，我们不妨设 $m=m_{1}d,n=n_{1}d$ 。
此时 $\bar{m} \circ \bar{n_{1}}=\bar{mn_{1}modn}=\bar{m_{1}dn_{1}modn}=\bar{m_{1}nmodn}=\bar{0}$
因此 $\bar{m}$ 是零因子。

定理2 若p是一个素数，则剩余类环 $Z_{p}$ 是域，若n是合数，则剩余类环 $Z_{n}$ 有零因子，不是域。
证明若p是素数，则 $Z_{p}=\{\bar{0},\bar{1},...,\bar{p-1}\}$ ，因为p与1,2,...,p-1均互素，根据定理1， $Z_{p}$ 中所有p-1个非零元均可逆，因此 $Z_{p}$ 是域。