整理一下密码学常用的抽代知识。分成两个部分:基本框架、重要内容。
我在B站上录制了一个课程(建议1.5倍速),2小时即可快速回顾抽代知识:密码学的数学基础:课程简介
基本框架和语言
几个重要术语:代数结构、子结构、同态、商结构
在线性代数中对应:线性空间、子空间、线性映射、商空间
代数结构 | 子结构 | 同态 | 商结构 |
---|---|---|---|
群 | 子群 | 群同态 | 正规子群->商群 |
环 | 子环 | 环同态 | 理想->商环 |
域 | 子域 | /(同上) | /(同上) |
线性空间 | 子空间 | 线性映射 | 商空间 |
直积(直和)、生成子集对应线性代数中的直和、基。
其他重要内容
群、环
- 拉格朗日定理——费马小定理、欧拉定理
- 同构第一定理——$\mathbb{Z}_{N} \cong \mathbb{Z}/N\mathbb{Z}$(模运算)、中国剩余定理
- 循环群——离散对数问题
- 多项式环——NTRU、多变量公钥
- 一些概念:整环、除环、域、主理想、素理想、极大理想…
域
素域、域的特征
由整环构造域:分式域、$R/M$ ( $PID$ 中 $R/(p)$ )
域的分类:按元素个数分为有限域、无限域,可用特征区分
域的扩张:代数扩张与有限扩张、超越扩张与无限扩张
多项式的分裂域,例如 $\mathbb{R}$ 上 $x^2+1$ 的分裂域,$x^n - 1$ 的分裂域。
有限域的结构:子域格、$\mathbb{F}_q$ 作为向量空间,$\mathbb{F}_q$ 作为分裂域、本原元
一般有限域的结论(与$\mathbb{F}_p$类似):费马小定理、欧拉定理、Wilson定理…
有限域上的运算、元素的表示
本原多项式——LFSR相关理论、周期计算等