#zkp #math

群：具有封闭加法运算的集合称为群

环：在群的基础上，添加一种乘法运算。但每个元素不一定有乘法逆元。

域：在环的基础上，要求每个元素都有乘法逆元。等于加法群和乘法群

常见的域： $Q$ 有理数； $Z$ 整数； $Z^+$ 正整数； $N$ 非负整数； $N^+$ 正整数； $R$ 实数

群的定义：只有一个运算的、简单的代数结构（代数结构是指具有一个以及以上运算的非空集合），由 一个集合 $\mathbb{G}$ 和一个二元操作构成，满足以下四个性质：

  1. 封闭性：如果 $a, b \in \mathbb{G}$，则 $a \cdot b \in \mathbb{G}$
  2. 结合律： $(a \cdot b) \cdot c = a \cdot (b \cdot c)$
  3. 单位元 $I$：存在一个元素使得 $a \cdot I = I \cdot a = a$
  4. 逆元：每个元素 $a$ 都有逆元 $a^{-1}$ 使得 $a \cdot a^{-1} = e$

阿贝尔群（Abelian Group）：又称交换群，额外满足一个性质：

  1. 交换律： $a \cdot b = b \cdot a$

循环群（Cyclic Group）：循环群都是阿贝尔群，还额外满足一个性质：

  1. 生成元：存在一个元素 $g$，能够通过 有限次的本身运算 表达出其它所有元素。一般用 $g^x$ 表达生成元 $g$ 经过 $x$ 次自身运算得到的结果。

群的举例：

  • $G = {0, 1}$, 除法运算 $\div$。不满足封闭性，比如 $1 \div 0 \notin G$，所以不是群。
  • $G = {0, 1, 2, 3, 4}$，加法再模5运算 $(x + y) \mod 5$。这是一个满足条件的加法群，单位元为 0，生成元 ${1, 2, 3, 4}$。
  • $G = {0, 1, 2, 3, 4, 5, 6}$，乘法再模7运算 $(x + y) \mod 7$。这是一个满足条件的乘法群，单位元为 0，生成元 ${3, 5}$。

常见的群：密码学中常见的群是素数群、椭圆曲线群，只是计算的速度不一样。要达到相同的安全性，所需要的私钥位宽不一样。

环的定义：由一个集合和两个二元操作构成，满足以下性质：

  1. 加法结合律： $(a + b) + c = a + (b + c)$
  2. 加法交换律： $a + b = b + a$
  3. 加法单位元： $a + I = I + a = a$
  4. 加法逆元： $a + (-a) = I$
  5. 乘法结合律： $(a * b) * c = a * (b * c)$
  6. 分配律： $a * (b + c) = (a * b) + (a * c)$

可以看出，环 在加法操作下是个 阿贝尔群。

域的定义：域，是一个集合，满足加法和乘法的结合律、交换律、分配律、单位元和逆元共五个性质。

伽罗瓦域：有限域

See Also