抽象代数把对象和运算抽离出来,只关心它们满足什么规则。密码学里常见的有限域、椭圆曲线群和多项式环,都可以从这套语言开始理解。
群(Group)
群的概念
一个非空集合配上一种二元运算,如果满足封闭性、结合律、单位元和逆元,就可以称为一个群。记作
(G, *)。
快速判断
先确认运算结果仍在集合内,再看括号位置是否不影响结果,最后找单位元和每个元素的逆元。
- 整数集合在加法下构成群,单位元是 0。
- 模 n 的剩余类在加法下构成群。
- 非零有理数在乘法下构成群,单位元是 1。
更多更多的群
如果运算还满足交换律,就得到阿贝尔群;如果只保留部分条件,则会退化成半群、幺半群等结构。
环(Ring)
环的概念
环可以理解为同一个集合上同时存在加法和乘法。加法通常要求形成阿贝尔群,乘法要求结合,并且乘法要对加法满足分配律。
(a + b) * c = a * c + b * c
a * (b + c) = a * b + a * c
重点强调:零因子(zero divisor)
如果两个非零元素相乘得到 0,它们就是零因子。零因子的存在会让“消去律”失效,所以在代数推导里需要格外留意。
域(Field)
域是在环的基础上继续加限制:非零元素在乘法下也要有逆元。直观地说,域允许我们像处理有理数那样做加、减、乘、除。
有限域 GF(p) 和 GF(2^8) 在密码学中非常常见,AES 的字节运算就是一个典型例子。
小结
群强调一个运算的可逆结构,环把加法和乘法放在一起,域则让非零元素也能做除法。把这三层关系理清,后面看有限域和 ECC 会轻松很多。