环和域

定义1： 环（Ring）

一个同时有两种运算：加法和乘法的集合，如果满足如下性质，就称为环R：

  1. R在加法+下是一个阿贝尔群，加法单位元记作0（称为零元）
  2. R在乘法 ⋅\cdot 下满足封闭律，结合律和单位元律，乘法单位元记作1
  3. ∀a,b∈R,a⋅b=b⋅a\forall a, b \in R, a \cdot b =b \cdot a
  4. ∀a,b,c∈R,a⋅(b+c)=a⋅b+a⋅c\forall a,b,c \in R, a \cdot (b+c) = a \cdot b +a \cdot c

如果乘法还满足交换律，则是一个交换环。

例1：

  1. 在通常的加法和乘法运算下， Z,Q,R和C均是环
  2. 对 n>0， 在模n加法和模n乘法运算下，ZnZ_n是一个环

定义2： 域（Field）

如果一个环中的非零元在乘法运算下构成群，则该环就称为域。

域中乘法群（即非零元）满足封闭律，这表明域FF不含零因子，即对任意的a,b∈F,ab=0a,b\in F,ab=0可推出a=0或b=0

例2：

  1. 在通常的加法和乘法运算下，QRC均是域。

定义3： 一个代数结构如果包含有限个元素，就说该代数结构是有限的，元素的个数称为这个结构的阶。

如果一个代数结构A的一个非空子集S在A的运算下自身成为一个代数结构，那么S就称为代数结构A的子结构。

有限域的结构

有限域在密码学和密码协议中有着广泛的应用。现在我们对有限域的结构进行一下完整的讨论。

含有素数个元素的有限域

最简单结构的有限域就是阶为素数的有限域，然而这样的域在密码学中的应用却最广泛。

素域：不含真子域的域称为素域

例如，Q为素域，由于Q为R的真子域，所以R不是素域，Q是一个无限域。

同态和同构：令A，B是两个代数结构，如果映射f:A→Bf:A\rightarrow B保持A的运算，即如果⋅\cdot是A的运算，∗*是B中的运算，那么$\forall x,y \in A, f(x\cdot y)=f(x)*f(y) $，则该映射就称为A到B的同台。如果f是A到B上的一一同台，那么f就称为一个同构，我们就说A和B是同构的。

如果f:A→Bf: A\rightarrow B 十一个同态，且e是A中的一个单位元（加法的或乘法的），那么f(e)∗f(e)=f(e⋅e)=f(e)f(e)*f(e)=f(e\cdot e)=f(e)

举例：同构的代数结构：

对于任意素数p，函数f(x)=gx(modp)f(x)=g^x(mod p)是加法群Zp−1Z_{p-1}和乘法群Zp∗Z_p^*之间的同构映射，因此这两个群是同构的。

域FpF_p，令p为一个素数，有限域ZpZ_p记为FpF_p

代数结构的特征：A是一个代数结构，对每一个a∈Aa\in A，满足 na=0na =0的最小正整数n称为A的特征，记为char(A)char(A)，如果正整数n不存在，就说AA的特征为0。每一个有限域的特征均为素数。