近世代数作为理论数学的一个完整分支，其对群、环、域等的研究非常复杂，此处仅总结一些与密码学相关的概念和基础

群

首先定义代数运算

定义集合M上的一个法则 $\cdot$ ，若对于M上的每一组有序对$(a,b)$，$a,b\in M$，总存在唯一的$d\in M$使得$a\cdot b=d$成立，即满足封闭性，则法则 $\cdot$ 被称为M上的一个代数运算

设G是一个定义了代数运算 $\cdot$ 的非空集合，当满足如下条件时称G对代数运算 $\cdot$ 做成一个群

  • 结合律：若$a,b,c\in G$，则$a\cdot(b\cdot c)=(a\cdot b)\cdot c$
  • 存在左单位元：存在一个元素$e\in G$，使得对G中任意元素$a$，都有$e\cdot a=a$成立
  • 存在左逆元：对G中任意元素$a$，在G中都有元素$a^{-1}$，使得$a^{-1}\cdot a=e$

群有一些重要定理

  • 群G的左单位元也是右单位元，即有$e\cdot a=a\cdot e=a$，且单位元是唯一的
  • 群G中任意元素$a$的左逆元$a^{-1}$也是其右逆元，即有$a\cdot a^ {-1}=a^{-1}\cdot a=e$，且逆元是唯一的

若群G还满足交换律，即对G中任意元素a、b，都有$a\cdot b=b\cdot a$成立，则称为交换群或Abel群

环

设R是定义了两个代数运算+和×的非空集合，两个代数运算分别称为加法和乘法
当满足如下条件时称R对代数运算+和×做成一个环

  • 加群：R对加法做成交换群。此时用$0$表示其单位元，称为零元，$-a$表示$a$的逆元
  • 乘法满足结合律：若$a,b,c\in R$，则$a(bc)=(ab)c$
  • 结合律：若$a,b,c\in R$，则$a(b+c)=ab+ac$和$(a+b)c=ac+bc$均成立

若环R还满足乘法交换律，即对R中任意元素a、b，都有$ab=ba$成立，则称为交换环

此处再引入一个概念零因子

设R为环，$a\in R$且$a\neq 0$，若存在$b\in R$且$b\neq 0$使得$ab=0$，则称a为环R的左零因子，同理可定义右零因子

然后可以定义整环

阶大于1，有乘法单位元且无零因子的交换环称为整环

域

当满足如下条件时称环R做成一个域

  • $|R|>1$
  • R有乘法单位元，记为1，满足$a1=1a=a$
  • R的每个非零元都有逆元，即对任意$a\in R$且$a\neq 0$，都存在$a^{-1}$使得$aa^ {-1}=a^{-1} a=1$成立
  • R满足乘法交换律

根据上述定理可以推出域没有零因子，因此也可以将域定义为非零元都有乘法逆元的整环

有限域GF(p)

密码学中主要关注的是有限域，定理表明有限域的阶一定为$p^n$，其中$p$为素数，$n$为正整数

阶为$p^n$的域一般记为$GF(p^n)$，我们主要关注$GF(p)$和$GF(2^n)$

给定一个素数p，有限域$GF(p)$定义为$Z_p$，即${0,1,…,p-1}$，其运算为模 $p$ 的算术运算

$Z_p$中任意整数$a$有乘法逆元定义为使得$ab\equiv 1(\mod p)$成立的$b$
当且仅当$a$与$p$互素时$a$有乘法逆元，因此$Z_p$中除0元外均有乘法逆元，其余做成域的条件$Z_p$则显然满足

乘法逆元的求解可以用扩展欧几里得或费马小定理

特别的，$GF(2)$中加法等价于异或，乘法等价于逻辑与

多项式环

一个$n$次多项式的表达式形如$f(x)=\sum_{i=0}^na_ix^i$

设$f(x)=\sum{i=0}^na_ix^i,\ g(x)=\sum{m=0}^nb_ix^i,\ n\geq m$，定义多项式的加法与乘法运算如下

多项式的除法按如下定义：给定n次多项式$f(x)$和m次多项式$g(x)$，$n\geq m$，若用$g(x)$除$f(x)$，可得到商$q(x)$和余数$r(x)$，满足$f(x)=g(x)q(x)+r(x)$，其中$q(x)$次数为n-m，$r(x)$小于等于m-1

假如多项式的系数为域F的元素，则称之为域F上的多项式，这样的多项式集合是一个环，因为其除法不一定是整除，也即不一定有乘法逆元，这个环称为多项式环

域F上的多项式$f(x)$称为不可约的，当且仅当$f(x)$不能表示为两个多项式的乘积，也称为素多项式

有限域GF(2^n)

由于所有加密算法都涉及整数集上的算术运算，若某个算法使用了除法，就必须定义一个域
同时我们希望这个整数集中的数与二进制位数表达的信息一一对应，即对n位的二进制数，我们希望整数集的范围是$[0,2^n-1]$，从而不造成空间浪费
综上所述，我们的任务就是构造一个合适的有限域$GF(2^n)$

设集合S由域$Z_p$上次数小于等于$n-1$的多项式组成，当满足如下条件时S是一个有限域

  • 运算遵循普通多项式运算
  • 系数运算以p为模，即遵循有限域$Z_p$上的运算规则
  • 若多项式乘法运算结果次数大于$n-1$，必须对某个次数为$n$的素多项式取模

根据上述条件，我们可以定义$GF(2^n)$为域$Z_2$上次数小于等于$n-1$的多项式构成的有限域
这样，每个n​位二进制数就唯一地对应一个系数为0或1的n-1次多项式