密码学：数论基础

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

对于 ，如果 整除 ，则称“ 同余于 模 ”，记做

我们定义算术模 为 ：表示具有两个运算符 （加法）和 （乘法）的集合 。 中的加法和乘法与实数加法和乘法完全一样，只是结果要进行模 约化。

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

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

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

有限群 的阶定义为 ，表示为 。

对群中的元素，即 ， 的阶定义为满足如下式的最小的正整数 。其中 为 的单位元

对于群 ，如果操作符 还满足交换律，对 ，有 ，则称 为阿⻉尔群，⼜称为 交换群 。

对于群 ，如果 是有限集合，则称 是有限群。

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

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

假设 是一个有限群。如果 也是一个有限群，且 ，则称 是 的一个子群。

显然，为使 为有限群，并非任意的 就可以的，从 中选取元素时需重点考虑令 满足封闭性： 。

设 是 的子群，那么 ，定义 右陪集 （right coset） 为: 。

同理, 定义 左陪集 （left coset） 为： 。

对于整数 ， 表示小于 且与 互质的所有正整数的数量。 被称为欧拉函数。

如果 是 的子群，则 整除

一个从 到 的同构是一个双射（bijection） 满足 ， 。

如果 是从 到 的同构，那么 和 的阶相同，并且

一个从 到 的同态是一个映射（mapping） 满足 ， 。

一个从 到 的同态是同构当且仅当 是双射的时候。

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

给定两个不完全为0的整数 ， ，必存在整数 ， 使得 ， 是 ， 的最⼤公约数。

给定两个不全为0整数a和b，扩展欧几里得算法计算整数 使得 ，本文略。

假设 和 是群，则其直积 所得的群定义为 , 其中：对于任意的 ，满足 。

环是 非空集合 和基于 定义的两个⼆元操作符组成的，满足如下性质三元组 ，记作 。

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

如果环 中 是有限集合，则称为有限环。

如果环 中的乘法 满足交换律，则称为交换环。

计算两个多项式 , 的最大公约数

假设 和 是环。则其直积 所得的环定义为 , 其中：对于任意的 ，满足 ，且

一个从 到 的同构是一个双射（bijection） 满足 ， ，且 。

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

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

对于交换环 ，如果 的每个理想 都是主理想，那么称 是主环。

一个主环的例子是：

一个带单位元的交换环 ，如果使得每个非零元素都具有乘法逆元，即 是阿贝尔群，则称其为域，记作 。

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

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

举例而言， ， ， 是域， 是环。

根据定理，当且仅当 时阶为 的有限域 才存在，其中 为素数， 且 。 称为 的特征

类似子群，子环。