密码学：数论基础

作者: PlyTools | 来源:发表于2020-02-04 04:12 被阅读0次

符号表

符号	说明	衍生示例
$\mathbb{Q}$	有理数，即 $\{\frac{a}{b} \mid a, b \in \mathbb{Z}, b \neq 0\}$	$\mathbb{Q}^+$ , $\mathbb{Q}^-$
$\mathbb{Z}$	整数集，即 $\{..., −3, −2, −1, 0, 1, 2, 3, ...\}$	$\mathbb{Z^*}$ ， $\mathbb{Z}^+$ 表示正整数集， $\mathbb{Z^-}$ 表示负整数集
$\mathbb{N}$	自然数集，即 $\{0, 1, 2, 3, ...\}$	$\mathbb{N^*}$ 也表示正整数集
$\mathbb{R}$	实数集，即 $\{x \mid x \in [-\infty, +\infty]\}$	$\mathbb{R}^+$ , $\mathbb{R}^-$
$a \equiv b (\bmod m)$	$a$ 同余于 $b$ 模 $m$
$ord(G)$	有限群 $G$ 的阶
$gcd(c, b)$	$a$ , $b$ 的最大公约数
$\phi(n)$	欧拉函数
$G$	群
$g$	生成元
$R$	环
$(c)$	由 $c$ 生成的主理想
$F$	域	$F_n$ 表示模n形成的有限域， $n$ 为素数

1 模运算（Modular Arithmetic）

1.1 模约化（Modular Reduction）

如果我们用 $a \bmod m$ 代替 $a$ ，称为此过程称为模约化，而 $a \bmod m$ 代表了 $a$ 除以 $m$ 的余数

1.2 同余式（Congruences）

对于 $\forall a, b \in \mathbb{Z}, m \in \mathbb{Z}^+$ ，如果 $m$ 整除 $b-a$ ，则称“ $a$ 同余于 $b$ 模 $m$ ”，记做 $a \equiv b (\bmod m)$

1.3 算数模（arithmetic modulo）

我们定义算术模 $m$ 为 $\mathbb{Z}_m$ ：表示具有两个运算符 $+$ （加法）和 $\cdot$ （乘法）的集合 $\{0, \dots, m − 1\}$ 。 $\mathbb{Z}_m$ 中的加法和乘法与实数加法和乘法完全一样，只是结果要进行模 $m$ 约化。

2 群（Groups）

2.1 代数结构

讲“群”，先讲讲“代数结构”。代数结构是指具有⼀个及以上运算的⾮空集合。

2.2 群（Group）

群是非空集合 $X$ 和基于 $X$ 定义的二元操作符 $\star$ 组成的，满足如下4种性质的对，表示为 $G=(X, \star)$ 。因此，群也是一种代数结构。

封闭性（closed）：如果 $a, b \in X$ ，则 $a\star b \in X$ 。
结合律（associative）：如果 $a, b, c \in X$ ，则 $(a\star b)\star c = a\star(b\star c)$ 。
单位元（identity）：集合中存在⼀个元素 $id$ ，保证 $a\star id = id\star a = a$ ，对所有 $a \in X$ 的都成⽴。
逆元（inverse）：对每个集合的元素 $a \in X$ ，存在对应的 $b \in G$ ，保证 $a\star b = b\star a = id$ 。

有两类特殊的群：阿贝尔群和循环群，下文介绍。

2.3 阶（Order）

有限群 $G =(X, \star)$ 的阶定义为 $|X|$ ，表示为 $ord(G)$ 。

对群中的元素，即 $\forall a \in X$ ， $a$ 的阶定义为满足如下式的最小的正整数 $m$ 。其中 $id$ 为 $G$ 的单位元

$\underbrace{a \star a \star \cdots \star a}_{m} = id$

2.4 阿贝尔群（Abelian Group）

对于群 $G=(X, \star)$ ，如果操作符 $\star$ 还满足交换律，对 $\forall a, b \in X$ ，有 $a\star b = b\star a$ ，则称 $G$ 为阿⻉尔群，⼜称为交换群。

2.5 有限群（Finite Group）

对于群 $G=(X, \star)$ ，如果 $X$ 是有限集合，则称 $G$ 是有限群。

2.6 循环群（Cyclic Group）

对于有限阿贝尔群 $(X, \star)$ ，如果存在一个元素 $g \in X$ 的阶数等于 $|X|$ ，则称该群为循环群，元素 $g$ 称为该群的生成元（Generator），通常记作 $g$ 。循环群中的所有元素都可以由生成元 $g$ 通过幂次运算得到，且生成元和群的阶 $|X|$ 一定是互质的。

循环群都是阿⻉尔群，但不是所有的阿⻉尔群都是循环群。

2.7 子群（Subgroup）

假设 $G=(X, \star)$ 是一个有限群。如果 $H =(Y, \star)$ 也是一个有限群，且 $Y \subseteq X$ ，则称 $H$ 是 $G$ 的一个子群。

显然，为使 $H$ 为有限群，并非任意的 $Y \subseteq X$ 就可以的，从 $X$ 中选取元素时需重点考虑令 $H$ 满足封闭性： $\forall h1, h2 \in H, h1\star h2 \in H$ 。

2.8 陪集（Coset）

设 $H = (Y, \star)$ 是 $G = (X, \star)$ 的子群，那么 $\forall a \in X$ ，定义右陪集（right coset） $Ya$ 为: $Ya = \{y \star a : y \in Y\}$ 。
同理, 定义左陪集（left coset） $aY$ 为： $aY = \{a \star y : y \in Y\}$ 。

2.9 欧拉函数（Euler Totient Function）

对于整数 $n≥2$ ， $\phi(n)$ 表示小于 $n$ 且与 $n$ 互质的所有正整数的数量。 $\phi(n)$ 被称为欧拉函数。

2.10 拉格朗日定理（Lagrange’s theorem）

如果 $H = (Y, \star)$ 是 $G = (X, \star)$ 的子群，则 $ord(H)$ 整除 $ord(G)$

2.11 同构（Isomorphism ）

一个从 $G = (X, \star)$ 到 $H = (Y, ∗)$ 的同构是一个双射（bijection） $\varphi : X → Y$ 满足 $\forall a, a' \in X$ ， $\varphi(a \star a') = \varphi(a) ∗ \varphi(a')$ 。

如果 $\varphi: X \rightarrow Y$ 是从 $G = (X, \star)$ 到 $H = (Y, ∗)$ 的同构，那么 $G$ 和 $H$ 的阶相同，并且 $\forall x \in X, ord(x) = ord(\varphi(x))$

2.12 同态（Homomorphism）

一个从 $G = (X, \star)$ 到 $H = (Y, ∗)$ 的同态是一个映射（mapping） $\varphi : X → Y$ 满足 $\forall a, a' \in X$ ， $\varphi(a \star a') = \varphi(a) ∗ \varphi(a')$ 。

一个从 $G$ 到 $H$ 的同态是同构当且仅当 $\varphi$ 是双射的时候。

2.13 欧几里得算法（Euclidean Algorithm）

用于计算两个正整数（例如a和b）的最大公约数。

2.14 扩展欧几里得定理（Extended Euclidean Algorithm）

扩展欧几里得定理

给定两个不完全为0的整数 $a$ ， $b$ ，必存在整数 $x$ ， $y$ 使得 $ax + by = \gcd(a,b)$ ， $\gcd(a,b)$ 是 $a$ ， $b$ 的最⼤公约数。

扩展欧几里得算法

给定两个不全为0整数a和b，扩展欧几里得算法计算整数 $x, y$ 使得 $ax + by = \gcd(a,b)$ ，本文略。

2.15 直积（Direct Product）

假设 $G = (X, \star)$ 和 $G'= (X', *)$ 是群，则其直积 $G × G'$ 所得的群定义为 $G × G'= (X × X', \star)$ , 其中：对于任意的 $a, b \in X, a', b' \in X'$ ，满足 $(a, a') \circ (b, b') = (a \star b, a' * b')$ 。

3 环（Rings）

3.1 环（Ring）

环是非空集合 $X$ 和基于 $X$ 定义的两个⼆元操作符组成的，满足如下性质三元组，记作 $R=(X, \cdot, +)$ 。

$(X, +)$ 是一个阿贝尔群，即满足封闭性，结合律，交换律，且有单位元和逆元。
乘法封闭性：如果 $a, b \in X$ ，则 $ab \in X$ 。
乘法结合律：如果 $a, b, c \in X$ ，则 $(ab)c = a(bc)$ 。
乘法分配律（distributive）：如果 $a, b, c \in S$ ，则

$a(b + c) = (ab) + (ac)$

$(b + c)a = (ba) + (ca)$

注意，环中的乘法不要求可交换、有单位元或逆元，可理解为只支持加减乘运算。

3.2 有限环（Finite Ring）

如果环 $R=(X, \cdot, +)$ 中 $X$ 是有限集合，则称为有限环。

3.3 交换环（Cyclic Ring）

如果环 $R=(X, \cdot, +)$ 中的乘法 $\cdot$ 满足交换律，则称为交换环。

3.4 欧几里得多项式算法

计算两个多项式 $a(x)$ , $b(x)$ 的最大公约数

3.5 直积（Direct Product）

假设 $R = (X, \cdot, +)$ 和 $R'= (X', \cdot, +)$ 是环。则其直积 $R × R'$ 所得的环定义为 $R × R'= (X × X', \cdot, +)$ , 其中：对于任意的 $a, b \in X, a', b' \in X'$ ，满足 $(a, a') \cdot (b, b') = (a \cdot b, a' \cdot b')$ ，且 $(a, a') + (b, b') = (a + b, a'+ b')$

3.6 同构（Isomorphism ）

一个从 $R = (X, \cdot, +)$ 到 $S = (Y, ∗)$ 的同构是一个双射（bijection） $\varphi : X → Y$ 满足 $\forall a, a' \in X$ ， $\varphi(a \cdot a') = \varphi(a) \cdot \varphi(a')$ ，且 $\varphi(a + a') = \varphi(a) + \varphi(a')$ 。

3.7 中国剩余定理（Chinese Remainder Theorem）

求解同时满足多个子同余式的 $x$ 的同余式。本文略去。

3.8 子环（Subring）

子环

环的⼀个⾮空⼦集，如果在加法和乘法上依然是个环，那么就称这个环是原来的环的⼦环。

对于有理数域 $\mathbb{Q}$ ，整数环就是它的⼀个⼦环。对于整数环，所有偶数依然在加法、乘法下构成⼀个环（因为任何两个偶数通过加、减、乘得到的还是偶数，对于加、减、乘是封闭的，所以依然是⼀个环），偶数环是整数环的⼀个⼦环。对于 $n$ 阶实数矩阵环，其所有的⾮对⻆线上的值全为0的 $n$ 阶矩阵在矩阵加法、矩阵乘法上也构成了原矩阵环的⼀个⼦环，对于 $a$ 、 $b$ 两个矩阵，如果⾮对⻆线上为0，那么⽆论加法、减法还是乘法，得到的结果⾮对⻆线上都为0。

3.9 理想（Ideal）

理想（Ideal）：

对于交换环 $R = (X, \cdot, +)$ 。满足下面要求的集合称为 $R$ 的理想：
1. $I \subseteq X$
2. $(I, +)$ 是阿贝尔群
3. $\forall a \in X, b \in I$ ，满足 $ab \in I$
平凡理想（Trival Ideal）

很明显，每个环⾄少有两个理想：⼀个理想是单个0元所组成的环，因为任何⼀个元与0元的乘都为0元；另⼀个是这个环本身。这两个理想，称为“平凡理想”（trival ideal）。
主理想（Principal Ideal）

对于交换环 $R = (X, \cdot, +)$ ，设 $c \in X$ ，以c生成的主理想，记作 $(c)$ ，定义为如下集合：

$(c) = {ac : a \in X}$
显然，主理想一定是一种理想。

3.10 商环（Quotient Ring）

分划

分划是指，⼀个⾮空⼦集的集合，并满⾜所有元素有且只能有⼀个所在的⾮空⼦集。⽐如 $\{1, 2, 3, 4\}$ 可以有如下的分划:

$\{\{1, 2\}, \{3, 4\}\}$

$\{\{1\}, \{2, 3, 4\}\}$

$\{\{1\}, \{2\}, \{3\}, \{4\}\}$
类

分划中的任意一个非空子集，称为类。
商环

设 $I$ 是 $R$ 的理想，如果 $Q$ 是 $R$ 的一个分划，且 $\forall x, y \in Q$ ，满足 $x-y \in I$ ，则 $Q$ 为 $R$ 关于理想 $I$ 的商环，记为 $R/I$ 。也就是说，商环 $Q$ 是以为 $I$ 为“界”的切割后的⼦环的集合。

举例来说， $\mathbb{Z}$ 是整数环， $(n)$ 是 $\mathbb{Z}$ 的理想，商环 $\mathbb{Z}/(n)$ 就是 $\mathbb{Z}_n$ 。

基于陪集的定义：对于交换环 $R = (X, \cdot, +)$ ， $I = (c)$ 是以 $c$ 生成的主理想，则其商环 $R/I$ 构造为： $R/I = (Y, \cdot, +)$ ，其中 $Y$ 由 $I$ 的（加法）陪集构成。

对于 $\forall a, b \in X$ ，两个陪集 $I + a$ 和 $I + b$ 的和定义为 $I + (a + b)$ ，乘积（product）定义为 $I + ab$