Crypto基础数学知识

代数系统和近世代数

概念

一个集合中，如果有一种或多种代数运算 (Algebraic Operation)，则称该集合为代数系统 (Algebraic System)，也称作代数结构 (Algebraic Structure)

代数学作为一个不断进步与

完善的数学分支，其研究范围也从古典的整数、有理数、实数与复数等常见数集扩展到了矢量、矩阵和线性算子等对象，这类课题就共同组成了如今的近世代数 (Modern Algebra)

上文提到的代数运算，是定义在集合中的元素之间的法则，亦与集合是否能作成代数系统有着密切关联，它们扩展自常见的加减乘除这样的运算。经过定义合适的代数运算，集合可以作成群、环、域、格等代数系统

前置知识

• $∅$：空集
• $∀$：所有（每一个），强调普遍性
• $∃$：存在（至少一个）
• $∈$：属于
• $e$：群的单位元（群中那个与任何元素运算后都“保持该元素不变”的独一无二的元素）
• $∘$：二元代数运算
• $ψ$：连接两个群（G 和 H）的那个特定映射（函数），在本文中无深意无需纠结

群

给定一个集合 $G≠∅$ 以及其上的二元代数运算$「 ∘ 」$，如若它们满足如下性质：

1. 封闭性（Closure）：∀v,u∈G,v∘u∈G;
2. 结合律（Associativity）： ∀v,u,w∈G,(v∘u)∘w=v∘(u∘w);
3. 单位元（Identity）： ∃e∈G,∀v∈G,e∘v=v;
4. 逆元（Inverse，亦称反元）： ∀v∈G,∃v−1∈G,v−1∘v=e;

则称集合 G 对该代数运算作成一个群（Group），记作 (G,∘).

例：

整数加法群 (Z,+) ，不难验证其不仅对加法封闭，满足结合律，且存在整数0作为单位元，并对于每个整数m皆有其相反数−m作为其逆元

整数乘法群 (Q+,×) ，其中单位元为1，对于每个元素a其逆元为1/a ，举一个更简单扽例子：定义在集合 {−1,1} 上的乘法群 ({−1,1},×)，这亦不难验证其作成一个群。

实数域 $R$ 上的全体 $m$ 阶可逆矩阵对于矩阵乘法作成群（单位元为 m 阶单位矩阵 $E_m$，对于每个元素 $A$ 其逆元为它的逆矩阵 $A^−1$），这在近世代数中被称为 $m$ 阶一般线性群 $GL_m(R)$.

在近世代数中，研究群的分支被称为群论（Group Theory）

半群和幺半群

在近世代数中，有些代数系统具有环的部分性质，虽不在我们的主要讨论范围内，但它们也具有广泛的应用场景与不可忽视的研究价值：

对于其上二元代数运算封闭的非空集合，

• 如若仅满足结合律，那么可以称该集合对该代数运算作成半群（Semigroup）
• 如若集合对于代数运算除封闭外，满足结合律，且具有单位元，则可以称其对该运算作成幺半群（Monoid）

由此，我们可以认为：

• 幺半群是含有单位元的半群
• 群是每个元素皆有逆元的幺半群

举例来说，正整数对于整数加法作成半群，而非负整数对于整数加法作成幺半群，由于零可以视为整数加法的单位元

交换群

给定一个群 (G,∘)，如若其满足交换律（Commutativity） i.e. $∀v,u∈G, v \circ u = u \circ v$ ，则称这个群是一个交换群或 Abel（阿贝尔）群（Abelian Group）

得出：上文提到的举例中，整数加法群 $(Z,+)$ 是交换群，但 $m$ 阶一般线性群 $GL_m(R)$ 不是交换群

环和域

给定一个集合 $R≠∅$ 以及其上的两个二元代数运算「 + 」和「 ∘ 」，如若它们满足如下性质：

1. $(R,+)$ 作成交换群；
2. R 对运算「 ∘ 」满足结合律： $∀v,u,w∈R$, 皆有 $(v∘w)∘u=v∘(w∘u)$;
3. 分配律（Distributivity）： $∀v,u,w∈R$, 皆有 $w∘(v+u)=w∘v+w∘u$ 与 $(v+u)∘w=v∘w+u∘w$ 成立；

则称集合 $R$ 对此二代数运算作成一个环（Ring），记作 $(R,+,∘)$，并常分别称运算「+」和「∘」为加法和乘法。

• 如若环 $R$ 上的乘法存在单位元 i.e. $∃e∈G,∀v∈G$, 皆有 $e∘v=v$, 则称环 $R$ 为幺环（Ring with identity）；
• 如若环 $R$ 上的乘法满足交换律，则称其为交换环（Commutative Ring）；
• 如若环 $R$ 中对除加法单位元外任意元素 $a≠0$ 皆存在乘法逆元 $a−1$，则称 $R$ 为除环（Division Ring）；
• 如若环 $R$ 既是交换环又是除环，那么环 $R$ 是一个域（Field）。

阶

指数：定义群中元素的指数，对于 $v∈G,m$ 为正整数，

• $v^0=e$;
• $v^m=v∘v∘⋯∘v$, 其中共有 $m$ 个 $v$ 参与代数运算；
• $v^−m=(v^−1)^m$;

元素的阶：对于任意给定的元素 $v∈G$, 如若正整数 $m$ 满足 $v^m=e, 则称元素 $v$ 的阶数为 $m$. 如若这样的正整数不存在，则称该元素的阶为无限。

举例而言，在群 ({1,−1,+j,−j},×) 中，各元素的阶如下：

元素	阶
1	1
-1	2
+j	4
−j	4

同态

代数系统间的同态（Homomorphism）指在不同代数系统间能够保持代数运算的映射。

具体来讲，对于群 $(G,∘)$ 和 $(H,∗)$ 而言，如若一个映射 $ψ:G→H$ 满足 $∀v,u∈G$,

$ψ(v∘u)=ψ(v)∗ψ(u)$,

那么映射 $ψ$ 便可以称为从 $G$ 到 $H$ 的一个群同态。

References

• 杨子胥，《近世代数》（第四版），高等教育出版社
• 群论简介 - OI-Wiki
• 基础数学知识 - CTF-Wiki