基本概念
集合
具有共同属性的事物的总体。
集合上的二元运算
设$S$为集合，映射
称为集合$S$上的二元运算。
群
群的定义
设三元组$(G,\cdot,1)$中G为集合，$\cdot$为集合$G$上的二元运算，$1$为$G$中一个元。
若$(G,\cdot,1)$满足：
- $G1$（乘法结合律）：$a\cdot(b\cdot c)=(a\cdot b)\cdot c,\quad a,b,c\in G$；
- $G2$（单位元）：$1 \cdot a=a \cdot 1 = a, \quad a\in G$；
- $G3$（逆元）：对$a \in G$，有$a’ \in G$使得$a \cdot a’=a’ \cdot a=1$。
则称$(G,\cdot,1)$为群，简称群$G$，$1$称为群$G$的单位元，$a’$称为$a$的逆元。
交换群
若$(G,\cdot,1)$还满足$G4$（交换律）：$a \cdot b = b \cdot a, \quad a,b \in G$，则称$G$为交换群。
有单位元的半群
若$(G,\cdot,1)$仅满足$G1,G2$，则称$G$为有单位元的半群。
有单位元的交换半群
若$(G,\cdot,1)$满足$G1,G2,G4$，则称$G$为有单位元的交换半群。
实例
在希尔密码（Hill Cipher）中加密变换为
这里密钥$M \in GL_m(Z_{26}), \ x_i,y_i \in Z_{26}, \ Z_{26}=\{0,1, \cdots, 25\}$，
$x_i$为明文，$y_i$为密文。（$GL_m(Z_{26})$表示在集合$Z_{26}$上定义的$m$阶可逆方阵构成的群，式子右边的行向量$(x_1,x_2, \cdots ,x_m)$与矩阵$M$乘是先进行通常的实数行向量与实数矩阵乘，再对所得行向量的每一分量模26）
几个常用群
- $Z$：整数集。关于数的加法构成交换群$(Z,+,0)$；
- $Q^\ast,R^\ast,C^\ast$：分别为零以外的所有有理数、实数、复数的集合。关于数的乘法构成交换群$(Q^\ast, \cdot, 1)$；
- $M_n(R)$：$R$上的全体$n$阶方阵。关于矩阵的加法构成群。
- $GL_n(R)$：（一般线性群）$R$上的全体$n$阶可逆方阵组成的集合。关于矩阵的乘法构成群；
- $SL_n(R)$：（特殊线性群）所有行列式等于$1$的$n$阶实数矩阵组成的集合。关于矩阵的乘法构成群；
- $O_n(R)$：（$n$阶正交群）$R$上的全体$n$阶正交矩阵组成的集合。关于矩阵的乘法构成群；
- $\{1,-1,i,-i\}$关于数的乘法构成交换群；
子群
子群的定义
设$(G, \cdot, 1)$为群，$A$为$G$的子集合。若$1 \in A$且$(A, \cdot, 1)$构成群，则称$A$为$G$的子群，并记为$A \leq G$。
实例
$nZ=\{0,\pm n, \pm 2n, \cdots\}$为整数群$(Z,+,0)$的子群。
循环群
循环群的定义
若群$G$的每一个元都能表示成一个元素$a$的幂次，则$G$称为由$a$生成的循环群，记作$G=\lt a \gt$，$a$称为循环群$G$的生成元。
阶的定义
有一个元素$g \in G$，如果存在一个$n \in Z^+$，使得$g^n=1$（$1$为循环群$G$的单位元），则称$n$为$g$的阶数（$g$是$n$阶元素）。
循环群的类型
循环群$G=\lt a \gt$共有两种类型：
- 当生成元$a$是无限阶元素，即找不到一个有限的$n$，使得$a^n=1$时，则$G$称为无限阶循环群。
- 如果$a$的阶为$n$，即$a^n=1$，那么这时$G=\lt a \gt=\lt 1,a,a^2,\cdots ,a^{n-1}\gt$，则$G$称为由$a$所生成的$n$阶循环群，注意此时$1,a,a^2,\cdots ,a^{n-1}$两两不同。
置换与对称群
置换的定义
$S=\{1,2,\cdots ,n\}$，映射$\sigma :S \rightarrow S$是可逆的，则称$\sigma$为$S$上的置换。
对称群的定义
全体$S$上的置换所成的集合记为$S_n$，命$1$表示恒等置换，在$S_n$中以$\sigma(i)$表示$i$在置换$\sigma$下的像，定义$S_n$中两元素$\sigma$与$\eta$的乘积为
则$(S_n,\cdot,1)$成群，群$S_n$称为$n$次对称群。
实例
在置换密码（Permutation Cipher）中加密变换为
这里$x_i,y_i \in S=\{1,2,\cdots,m\}$，$x_i$为明文，$y_i$为密文，$\sigma \in S_m$，$S_m$为$\{1,2,\cdots,m\}$上$m$次对称群。加密时按上述表达式每次$m$个字符的将明文串变为密文串。
群上的离散对数
概念
- 不同代数系统中都有各自的对数（离散对数）问题，有的可以找到快速算法，有的则尚未找到快速算法。
- 尚未找到快速算法的离散对数问题，可以看作一个数学上的“难题”，能够用来构造密码学算法或协议。
实例
- $(Z_n^\ast ,\bigotimes_n,1)$
设$\bigotimes_n$为模$n$乘，三元组$(Z_n,\bigotimes_n,1)$满足$G1$、$G2$和$G4$，为有单位元的交换半群，但其一半不为群，因为当$n$为合数时，$Z_n$中某些元不存在逆元。当$n$为素数时，对$a\in Z^\ast_n=\{1,2,\cdots,n-1\}$有$a’\in Z^\ast_n$使得$a\bigotimes_n a’=1$，即$Z^\ast_n$中每个元都有逆元，故$(Z_n^\ast,\bigotimes_n,1)$为群。
- $(Z_n^\ast,\bigotimes_n,1)$上的离散对数
设$n$为素数，在$(Z_n^\ast,\bigotimes_n,1)$中可定义
$a^m=a\bigotimes_n a\bigotimes_n \cdots \bigotimes_na$（$m$个$a$，$m$为整数）
对已知的$a,b\in Z_n^\ast$，求整数$x$，使得$a^x=b$的问题称为$Z_n^\ast$上的离散对数问题。该问题迄今无快速算法，被应用于Diffie-Hellman密钥交换协议中。
- 群上的离散对数
对$a,b\in G$（$G$为交换群），求整数$x$使得$b=a^x$。
群上离散对数问题中$G$为交换群，$G$的运算写成$+$，则群上的离散对数问题表示为：求整数$x$使得$b=xa$。
此种形式的离散对数问题应用于椭圆曲线密码体制（ECC）中。