密码学：数论基础

符号表

符号	说明	衍生示例
$\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$

3.11 主环（Principal Ring）

对于交换环 $R = (X, \cdot, +)$ ，如果 $R$ 的每个理想 $I$ 都是主理想，那么称 $R$ 是主环。

一个主环的例子是： $(\mathbb{Z}, \cdot, +)$

4 域（Fields）

4.1 域（Field）

一个带单位元的交换环 $R = (X, \cdot, +)$ ，如果使得每个非零元素都具有乘法逆元，即 $(R\backslash\{0\}, \cdot)$ 是阿贝尔群，则称其为域，记作 $F= (X, \cdot, +)$ 。

域是同时满⾜加法和乘法的结合律，交换律，分配律，单位元以及逆元五个性质的三元组 $(X, \cdot, +)$ ，能同时支持加减乘除（除0以外）。

上式意思是，域中的所有⾮零元素的集合是关于乘法的阿⻉尔群。

举例而言， $\mathbb{R}$ ， $\mathbb{Q}$ ， $\mathbb{C}$ 是域， $\mathbb{Z}$ 是环。

4.2 有限域（Finite Field）

有限域

有限域是集合中元素有限的域，⼜称为伽罗瓦域（Galois域）。它是伽罗瓦在18世纪30年代研究代数⽅程根式求解问题时提出的。

4.3 特征（Characteristics）

根据定理，当且仅当 $q=p^k$ 时阶为 $q$ 的有限域 $F_q$ 才存在，其中 $p$ 为素数， $k\geq 1$ 且 $k \in \mathbb{Z}$ 。 $p$ 称为 $F_q$ 的特征

4.4 子域（Subfield）

类似子群，子环。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,076评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,658评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,732评论 0赞 350
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,493评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,591评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,598评论 1赞 293
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,601评论 3赞 415
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,348评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,797评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,114评论 2赞 330
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,278评论 1赞 344
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,953评论 5赞 339
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,585评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,202评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,442评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,180评论 2赞 367
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,139评论 2赞 352