Cryptography/群环域

群/环/域论是许多密码学算法的基石. 我整理了下资料, 将它们的定义摘录如下. 在数论中, 群, 环和域都是代数结构的概念, 用于描述集合和运算之间的关系.

群

数学里面的群(G, group)是由集合和二元运算(用符号 + 表示)构成的, 符合以下四个群公理的数学结构. 群公理的四个性质如下:

加法封闭性: 对于群中的任意两个元素进行运算后, 结果仍然属于该群.
加法结合律: 群中的运算满足结合律, 即对于群中的任意三个元素进行运算, 先计算前两个元素的运算结果, 然后再与第三个元素进行运算, 结果应该与先计算后两个元素的运算结果再与第三个元素进行运算的结果相同.
加法单位元: 群中存在一个特殊的元素, 称为单位元, 对于群中的任意元素 a, 运算 a 与单位元的结果等于元素 a 本身, 即 a + e = e + a = a, 其中 e 表示单位元素.
加法逆元素: 群中的每个元素都有一个逆元素, 对于群中的任意元素 a, 存在一个元素 b, 使得 a + b = b + a = e, 其中 e 表示单位元.

如果我们添加第五条要求:

加法交换律: a + b = b + a.

那么这个群就是阿贝尔群或交换群.

例: 整数集 Z 是一个阿贝尔群. 自然数集 N 不是一个群, 因为它不满足第四条群公理.

一个有限群 G 的元素个数称为群的阶(order). 一个群元素 P 的阶为最小的整数 k 使得 kP = O(k 个 P 进行群运算, O 为单位元)称为 P 的阶. P 的阶一定整除群的阶. 如果一个元素 P 的阶等于群的阶, 则 P 是 G 的一个生成元, 且 G = {P, 2P, ...} 是一个循环群(cyclic group).

环

环(Z, ring)在群的基础上多定义了一个群运算 ×(乘法).

乘法封闭性: 对于环中的任意两个元素进行乘法运算后, 结果仍然属于该环.
乘法结合律: 环中的乘法运算满足结合律, 即对于环中的任意三个元素进行乘法运算, 先计算前两个元素的乘法结果, 然后再与第三个元素进行乘法运算, 结果应该与先计算后两个元素的乘法结果再与第三个元素进行乘法运算的结果相同.
乘法分配律: 环中的乘法运算对于加法运算满足左分配律和右分配律, 即对于环中的任意三个元素 a, b, c, 有 a * (b + c) = a * b + a * c 和 (b + c) * a = b * a + c * a.

域

域(F, Field)是一种代数结构, 由一个集合和两个二元运算(加法和乘法)组成. 域满足环的所有条件, 并且具有以下额外性质:

乘法单位元: 域中存在一个特殊的元素, 称为乘法单位元素, 对于域中的任意元素 a, 乘法 a 与乘法单位元素的结果等于元素 a 本身, 即 a * 1 = 1 * a = a, 其中 1 表示乘法单位元素.
乘法逆元素: 域中的每个非零元素都有一个乘法逆元素, 对于域中的任意非零元素 a, 存在一个元素 b, 使得 a * b = b * a = 1, 其中 1 表示乘法单位元素.

例: 整数集 Z 构成一个环但不构成域. 有理数集, 实数集和复数集均构成域.