Crypto基础数学知识
代数系统和近世代数
概念
一个集合中，如果有一种或多种代数运算 (Algebraic Operation)，则称该集合为代数系统 (Algebraic System)，也称作代数结构 (Algebraic Structure)
代数学作为一个不断进步与完善的数学分支，其研究范围也从古典的整数、有理数、实数与复数等常见数集扩展到了矢量、矩阵和线性算子等对象，这类课题就共同组成了如今的近世代数 (Modern Algebra)
上文提到的代数运算，是定义在集合中的元素之间的法则，亦与集合是否能作成代数系统有着密切关联，它们扩展自常见的加减乘除这样的运算。经过定义合适的代数运算，集合可以作成群、环、域、格等代数系统
前置知识
- $∅$：空集
- $∀$：所有（每一个），强调普遍性
- $∃$：存在（至少一个）
- $∈$：属于
- $e$：群的单位元（群中那个与任何元素运算后都“保持该元素不变”的独一无二的元素）
- $∘$：二元代数运算
- $ψ$：连接两个群（G 和 H）的那个特定映射（函数），在本文中无深意无需纠结
群
给定一个集合 $G≠∅$ 以及其上的二元代数运算$「 ∘ 」$，如若它们满足如下性质：
- 封闭性（Closure）：∀v,u∈G,v∘u∈G;
- 结合律（Associativity）： ∀v,u,w∈G,(v∘u)∘w=v∘(u∘w);
- 单位元（Identity）： ∃e∈G,∀v∈G,e∘v=v;
- 逆元（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≠∅$ 以及其上的两个二元代数运算「 + 」和「 ∘ 」，如若它们满足如下性质：
- $(R,+)$ 作成交换群；
- R 对运算「 ∘ 」满足结合律： $∀v,u,w∈R$, 皆有 $(v∘w)∘u=v∘(w∘u)$;
- 分配律（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