群环域

群/环/域论是许多密码学算法的基石. 我整理了下资料, 将它们的定义摘录如下.

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

  1. 封闭性: 如果 a 和 b 属于 G, 那么 a + b 也属于 G
  2. 结合律: (a + b) + c = a + (b + c)
  3. 单位元: a + 0 = 0 + a = a
  4. 逆元素: 对于任意元素 a 存在 b 使得 a + b = 0, b 称为 a 的逆元

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

  1. 交换律: 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)在群的基础上多定义了一个群运算 ×, 也满足封闭性和结合律, 且存在(乘法)单位元(不要求存在逆元素).

域(F, field)在环的基础上, 除了加法单位元之外所有元素存在(乘法)的逆元素.

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