百科知识网

密码学：数论基础

发布时间：2025-10-08 | 来源：互联网转载和整理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

设是的子群那么定义右陪集（rightcoset）为:。同理,定义左陪集（leftcoset）为：。

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

如果是的子群，则整除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一个主环的例子是：

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

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

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

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

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

类似子群子环。