updated: 2023-04-25

信息安全数学基础笔记

整除
素数
- 素数无穷
- 素数的算术基本定理
最大公因数
欧几里得除法
最小公倍数
群（group）

整除

定义：

性质：

传递性：
线性组合中整除保持：

素数

定义： 对于整数，若，则称为素数，否则为合数

定理：

若为正合数，为的一个非最小因子，则为素数且

证明：使用反证法，若p为合数，则，又有，则由整除传递性得到，因此不是的最小非因子，与题设相矛盾。

又由n为合数，则，由于p为最小非1因子，故，此时有，显然

素数无穷

证明：基本思想是先假设素数有无限多个，然后证明可能在一个素数在这有限多个素数构成的集合之外。

假设素数有有限多个，则可以将其枚举为，假设有那么必定有。

假设为素数，那么说明前提不正确，素数有无限多个。假如为合数。那么必定存在为的非最小子。因此存在使。若，则

因此有

此时

因此不是整数，这与为的一个因子相盾，因此（更准确的来说，此时的所素因子都要比中最大的元素还要大），因此素数有无多个。

上述证明过程利用了一类特殊的数——素数阶乘素数

扩展：证明形如的素数有无限多个

从上面对素数无限的证明，我们可以看到证明集合无限的核心思想是先去一个有限集合，然后证明总存在一个有限集合外的元素。这一过程需要通过构造来实现。

证明：假设有有限多个，那么这些素数可枚举为。考虑，易知

若为素数，则与开头假设相矛盾，可得形式的素数有无限多个。

若为合数，假设m的所有素因子为则

首先证明引理。由于Q中元素皆为素数，故中的一个元素要么满足的形式，要么满足的形式，假设所有满足的形式，易得也一定满足形式，这与定义相矛盾。引理得证。

有上述引理可知存在的素因子具有的形式，若，则与开头假设相矛盾，可得形式的素数有无限多个。

若，假设，则存在使有：

即

故不是整数，这与假设相矛盾，故。与开头的假设相矛盾，证毕。（有问题，参见这里）

素数的算术基本定理

素数的算术基本定理：任何一个大于1的整数都可以写成素数的乘积，且该乘积唯一。

证明：

假设该整数为，利用数学归纳法证明：

当为素数时，有为素数使，定理成立

当为合数时，将分解为，其中为的非1最小因子，有前面素数定理1我们可以得知为素数。此时将作同样的分解，最终我们可以得到，因此定理前半部分得证，后半部分可利用反证法证明，此处省略。

性质：

将整数分解式写作

则对于，当且仅当

时，为的一个因子

最大公因数

定义： 几个整数的最大公因数记为。若，则称它们互质。

性质：

证明：假设，则

由于是b与c的最大公因数，得到，同理可得，因此
假设，且，那么

证明：

假设，，那么，因此。

假设，，则，由于，易知，。由式联立得，即，因此为的公因数，因此

综上所述，

证毕（p.s. 也可以用广义欧几里得除法证）

由上述定理我们可以得到：

一个特殊情况是为素数时，必成立，此时
假设且

则。

此性质描述了最大公因数在可逆变换（剪切，旋转）下的不变性。

欧几里得除法

算法实现

注意到在上述定理中，我们可以得到一种逐步逼近a与b的最大公因数的方法——将计算的问题转换成计算的问题，从而保证每次迭代中c总会减小，最终减小到0，算法停机，代码实现如下：

pub fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        return a;
    }
    gcd(b, a % b)
}

或者

1	`let rec gcd a b = if b == 0 then a else gcd b (a mod b);;`

贝祖等式

假设整数的最大公约数为，则等式

有整数解当且仅当为的倍数，且只要等式有解，它必然有无穷多解。

证明：

设，假设有，其中为中的最小正元素，以及，假设

其中为非负整数，，则有

故，又因为，注意是中的最小正整数，因此，因此，因此，特别的，，因此为a与b的公约数，又因为对于a，b的任意一个公约数，假设，得到，即，因此为与的最大公约数。

扩展欧几里得算法

有了贝祖等式后，我们可以得到，所谓扩展欧几里得算法即是求上述等式中，值的方法。

假设现在我们要求的最大公约数，假设有：

由于便是我们要求的最大公约数，我们只需要求出中的即可。假设，我们首先可以导出:

因此有

可以看到，我们可以通过逐级上推最终确定的值，这一过程可以通过递归来完成：

#[derive(Debug)]
pub struct ExtGCD {
    pub p: i64,
    pub q: i64,
    pub m: i64
}

pub fn ext_gcd(a: i64, b: i64) -> ExtGCD {
    if b == 0 {
        return ExtGCD {
            p: 1,
            q: 0,
            m: a
        }
    }
    
    let next = ext_gcd(b, a % b);

    ExtGCD {
        p: next.q,
        q: next.p - a / b * next.q,
        m: next.m
    }
}

最小公倍数

几个整数的最小公倍数记为

性质：

假设为的最小公倍数，则
证明：使用归纳法证明：

当时，显然成立。

假设对结论成立，则有

对于，假设，由于且，可得，，进而

同时又易知为的公倍数，因此。

综上所述，，证毕。
证明：省略，利用数学归纳法以及上面的性质2即可证明。

群（group）

定义：

群由一个集合和定义在该集合上的运算组成

使用表示该集合，使用表示该运算。那么当代数结构满足下面的四条群公理时，该结构可以被称为群：

封闭性：
结合律：
单位元存在性：，可以将单位元（identity element）记为
逆元存在性：，其中为单位元，此时称为的逆元，记为

将二元运算称为该群上的乘法，那么由此可以导出该群上的除法：

假设有，现定义群上的除法。要证明除法的存在性即证明的存在性。

那么根据群的逆元存在性可知一定存在的逆元使。因此由单位元的性质以及结合律有

因此。

群同态（Homomorphism）

定义：

假设与为两个群，有映射，假如

那么称为群到群的一个同态。

若为单射，则该同态为单同态，若为满射，那么该同态是满同态。当为一一对应（双射），那么该同态称为同构，记为。

当两个群同构时，这两个群拥有完全相同的群结构，本质上可以认为是同一个群。

一个群到其自身的同态/同构称为自同态/自同构。

性质：

若是到的一个同态，且这两个群的单位元分别为与，那么

证明：// TODO

子群（subgroup）

定义：

对于群，若为的一个非空子集且同时与的二元运算构成一个群，那么称为的一个子群，群被称为该子群的母群，记为。

性质：

对于每个群，一元群以及自身都是它的子群，这两个子群被称为平凡子群。
证明：只需证是一个群即可。
1. 单位元：假设为的单位元，那么令，则，因此的单位元为
2. 逆元：令，则，因此中的每个元素都有逆元。
3. 封闭性：即证。令（逆元存在性），则
综上所述，是一个群。

举例：

对于整数加法群以及，为的一个子群，并且与同构。

证明：要证明与同构，只需证明存在到的一个双射满足，显然函数满足条件，因此与同构。

阿贝尔群（Abelian group）

定义：

对于群中的两个元素，不一定有，当一个群满足时，该群被称为可交换的，也被称为阿贝尔群或者加法群、交换群（commutative group）。

当称一个阿贝尔群为加法群时，可以将加法单位元记为，群上的二元运算记为。同时可以定义群上的减法

半群（semigroup）

定义：

使用表示该集合，使用表示集合上的运算。那么当代数结构满足

结合律，即
封闭性，即

时，该代数结构被称为半群。

当半群上存在单位元，即时，该半群被称为幺半群（monoid），该单位元被称为幺元。

性质：

若为幺半群，记为中的可逆元素全体，那么是群。

证明：
1. 结合律与单位元：由于是幺半群，易知满足结合律，且单位元即为幺元
2. 封闭性：现证，即证存在逆元。有，由结合律：，因此存在逆元。故在上封闭。
3. 逆元存在性：根据的定义，这是显然的。
综上所述，定理得证。

陪集（coset）

定义：

假设为一个群，为其子群，为中的元素，那么

为在中的左陪集
为在中的右陪集

对于加法群，可以用或者来表示左/右陪集

注意我们可以从陪集的定义中导出一个关系：考虑在中的左陪集，一个元素在中当且仅当，即，这时我们定义群上的关系。

接下来我们证明该关系是一个等价关系：

自反性：由子群的定义（单位元和母群相同）可知
对称性：若有，由于为群，有

注意乘法的顺序反过来是因为默认乘法不可交换，因此。
传递性：若，则由群的封闭性，有

综上所述，关系是一个等价关系，即

我们可以看到，该等价关系导出的等价类即为，假设是对上述等价关系的完全代表元系，根据等价类的性质，我们可以导出在该等价关系下的划分：

该分割被称为对子群的左陪集分解，其中左陪集的个数为，记为，这个值被称为子群对的指数。

拉格朗日定理

对于有限群，由于可以被分割为，其中每个等价类的元素个数相同。显然，即群的阶为子群的阶的倍数。

循环群

对于群，若存在使得，那么称为一个循环群，其中为该循环群的生成元。

循环群的阶

有限群中所有元素的个数称为群的阶，记为。

当是阶为的循环群时，有

对于中的元素，构成一个循环群，该群为的子群。其阶也被称为在中的阶，记为。当时，称为的生成元。

假设，为了求的阶，我们需要得到最小的，使得。由于，我们只需求出最小的使。不难得到

即的阶为。

推论

对于阶为的有限循环群，其生成元的个数为。

证明：要使某一元素为群的生成元，只需，即互质，显然，这样的的个数即为欧拉函数。（同时可以证明时，幂乘不会得到自身）
阶为质数的群都是循环群。

证明：// TODO

环（ring）

定义：

假设有一个集合以及定义在该集合上的二元运算以及，三元组形成一个代数结构，当且仅当该代数结构满足下面条件时，其被称为一个环：

形成一个交换群
形成一个半群
乘法运算（）关于加法（）满足分配律，即

性质：

环的性质可以由其定义导出

交换群的单位元被称为0元素，有。同时有

证明：

由分配律：

因此：

注意上面的是加法群的逆运算，由乘法半群的封闭性以及加法群逆运算的定义知，因此

同理可证.（注意这个不是半群的单位元）
证明：

由分配律：

同理有，原式得证。

幺环（unital ring）

定义：

当半群存在单位元（为幺半群）时，该环被称为幺环。此时幺半群的幺元也是该幺环的幺元。

环的理想（ideal）

定义：

若一个环的一个子集上的加法运算形成一个群，同时所有与子环中的元素进行的乘法运算的结构均在该子环中，那么称该子环称为原环的理想。环的理想呈现出一种闭包（对加法封闭）和吸收（对乘法吸收）的性质，因此可以利用环的理想来构造商环，从而实现对原环进行某种聚类。

严格定义如下：

假设有环，，那么当

构成的子群
时，被称为的一个左理想。时，被称为的一个右理想。当既是的左理想，也是右理想时，称其为的一个双边理想，简称理想。

举例：整数环只有形式的理想

商环 (quotient ring)

定义：

假设是一个环，是它的一个（双边）理想，定义如下等价关系（满足自反，传递，对称性）：

使用来表示由这个等价关系导出的等价类的集合，其中的元素记为。注意这个元素是一个集合，准确的来讲，。

对于集合

//TODO

剩余（residual）类与剩余系

同余（congruence）

定义：

注：也可以写作

性质：

同余具有自反性，对称性以及传递性。
证明：易知，由于，由最大公因数的性质2可知，因此成立。
证明：利用上面提到的最小公倍数的第三条性质，这是显然的。
证明：易知，利用最大公因数的性质1即可证明。

Definition: A group view

定义一个等价关系

那么我们可以在整数集上可以由该等价关系导出一个分割。这个分割由个等价类组成，将包含的一个等价类记为。使用表示上述个等价类组成的集合，在上定义加法

现证明该集合是一个阿贝尔群。

由同余的性质，该加法显然成立并且满足交换律，结合律以及封闭性。
单位元：易知我们总是有，且有，因此为单位元。
逆元：根据同余的性质，有，因此对于每个，总有使。

综上所述，是一个阿贝尔群。这个群被称为整数模n加法群。

该群中的等价类称为模剩余类，这个中所有等价类的代表元组成的集合被称为一个模完全剩余系。

Definition: A ring view

在上面提出的整数模加法群上假如定义一个乘法。我们下面证明整数群在这一二元关系下形成一个幺半群：

封闭性：由于任何一个整数必然属于某一个等价类，因此这是显然的
结合律：根据乘法的定义，这同样是显然的
单位元：由于，可知为单位元。

综上所述，对此乘法形成一个含幺交换半群。

根据环的定义可知构成一个幺环。

整数模n乘法群

接下来我们研究含幺交换乘法半群，通过上面提到的含幺半群的性质，我们可以知道从这个半群中可以提取出一个所有元素均可逆的子集，这个子集在乘法运算上构成群。

首先我们来研究该半群中的哪些元素可逆：

对于该条件的形式描述为

即，即。

下面我们简化问题：若，求应当满足的关系。

由上面提到的关于最小公因数的定理我们可以知道

此时取即可使。

因此我们推测

但注意这这里我们仅仅证明了充分性，下面我们来证明其必要性，即证明

显然当时有，进而，显然。故必要性得证。

综上所述，半群中元素可逆的充要条件是。

故从该半群可以导出一个交换群，我们将这个群称为整数模n乘法群。

可以看到，整数模n乘法群中等价类的代表元均与互质，因此这个群中元素（等价类）的个数即所有小于且与互质的整数的个数，记为，这个函数被称为欧拉函数。群的阶为.

中元素的阶

对于交换群，对于群中的某一个元素，根据群的封闭性，可以证明必然存在使得，那么使等式成立的最小称为的阶，在这种情况下，令，则群是交换群的循环子群，其阶为的阶。

要判断一个数是否是的阶，若。我们只需判断是否存在一个数使得。假设这样的数存在，那么显然，则一定整除某个的素因子，假设，取，则。因此我们只需验证的每一个质因数，使得如果均成立，那么便是的阶。

欧拉定理

根据拉格朗日定理，群中某一个元素的阶（其生成的循环群的阶）一定被的阶整除，由于，我们可以得到即对于任意，。

原根

原根的判定

不难看出，当的阶等于群的阶时，是一个循环群。此时称是模的一个原根，即是的一个生成元。即要验证某个数是否是模的原根，只需验证并且对于的每一个素因子都有即可。

原根的存在性

存在原根当且仅当，其中为奇素数。

若是的一个原根，那么和中必然有一个是的原根，和中的奇数必然是的原根。

根据之前的论述，循环群的生成元的个数为阶的欧拉函数，因此整数模乘法群的生成元个数为。换言之，即模的原根个数为。

若是的一个原根，我们可以通过循环群的性质求出其他的原根：对所有小于的质数，求即可。

离散对数（指数）

由于原根可以通过指数运算得到群中所有的元素，我们可以使用该指数作为群中元素的一个表征，例如模11乘法群中2是一个原根，由于，我们称9模11对于2的原根为6。

离散对数（记为）和通常的对数相比有很多类似的性质。

费马小定理

对于质数，群的阶。根据原根的存在性，存在原根，因此群是一个循环群。根据群的拉格朗日定理，该群中任何元素生成的子群的阶要么是1，要么是，由于单位元的存在，该群中任何非单位元元素的阶为，根据阶的定义，有。

整理上面的推导，我们得到下面的结论：对于任意素数，任意整数，有注：费马小定理也可以看作欧拉定理的一种特殊情况。

≡∧