【密码学】密码学数学基础：剩余系

        不得不啃的密码学数学基础之剩余系是个啥？数学里面有好多的定义都有前置的数学概念，要想弄懂剩余系还得先说说“同余”。

一、同余

        那么“同余”有是个什么呢？在谈论“同余”之前，我们先圈定个讨论的范围。接下来讨论的都是整数集合。好了！可以正式开始介绍了。

（1）等价关系与同余

        当我们讨论整数集合上的等价关系时，“同余”是一个核心概念，而由同余关系定义的“同余类”或“剩余类”则是研究整数除法性质和模运算的基本单元。

        首先，我们需要了解什么是等价关系。在数学中，如果集合 𝐴 上的关系 ∼ 满足以下三个性质，则称 ∼ 是 𝐴 上的等价关系：

1. 自反性：对于所有 𝑎∈𝐴，有 𝑎∼𝑎
2. 对称性：对于所有 𝑎,𝑏∈𝐴，若 𝑎∼𝑏 则 𝑏∼𝑎
3. 传递性：对于所有 𝑎,𝑏,𝑐∈𝐴，若 𝑎∼𝑏 且 𝑏∼𝑐，则 𝑎∼𝑐

        同余关系就是整数集 𝑍 上的一种等价关系。两个整数 𝑎 和 𝑏 被称为模 𝑛 同余，如果它们被 𝑛 除后的余数相同，记作 𝑎≡𝑏 (mod 𝑛)。换句话说就是，𝑎 和 𝑏 同余模 𝑛 当且仅当 𝑛 整除 𝑎−𝑏。

（2）同余类又叫剩余类

        既然同余关系是一种等价关系，那么它自然会将整数集 𝑍 划分成不同的等价类，这些等价类就是我们所说的同余类或剩余类。给定一个正整数 𝑛，对于 𝑍 中的任意整数 𝑎，我们可以构造模 𝑛 下的同余类，记作 [𝑎]𝑛 或者简单地写作 [𝑎]，其中包含所有与 𝑎 同余模 𝑛 的整数。

形式上，同余类 [𝑎] 定义为：

[𝑎]={𝑏∈𝑍∣𝑎≡𝑏 (mod 𝑛)}

        例如，考虑模 7 同余关系见下图

【我的理解】模7的剩余类[1]，意思就是有哪些数除7余1，将这些数组成一个集合，记为。所以“模7的同余类”其实可以理解为除7有共同余数的七堆数（余0余1一直到余6共七堆数）。

（3）剩余系

        在模 𝑛 同余意义下，所有可能的同余类构成了一个剩余系。更具体地说，模 𝑛 的完全剩余系是一组整数，每个整数代表了不同的同余类。最常见的是取模 𝑛 的完全剩余系为 {0,1,2,…,𝑛−1}。这个剩余系包含了所有可能的余数，即模 𝑛 同余类的代表元素。

还是拿上图，模7来举例：

        我们从七堆数里面，每堆抽出一个，合为一组。就叫做一组完全剩余系。若在每一堆数里面抽出一个数，不是随机抽，而是选出最小非负的，构成的剩余系被叫做最小非负完全剩余系。

二、完全剩余系

        上面我们见过了完全剩余系长什么样子，现在我们给完全剩余系一个严谨的数学定义：

        在整数模m的所有剩余类中各取一个代表元

        则称为模m的完全剩余系，其中完全剩余系被称为最小非负完全剩余系。

        用表示由m的最小非负完全剩余系集合，，在中的加法、减法、乘法都是模m意义下的运算。

三、简化剩余系

        在模m的一个剩余类当中，如果有一个数与m互素，则该剩余类中所有的数均与m互素，这是称该剩余类与m互素。

（1）欧拉函数的数学定义

        与m互素的剩余类的个数称为欧拉函数，记为。等于当中与m互素的数的个数，对于任意一个素数p，有

（2）简化剩余系的数学定义

        在与m互素的个模m的剩余类中各取一个代表元它们组合成的集合称为模m的一个简化剩余系。中与m互素的数构成模m的一个简化剩余系，称为最小非负简化剩余系。

        举例说明简化剩余系：

        设m=12，则 {0,1,2,3,4,5,6,7,8,9,10,11} 构成模12的完全剩余系，把其中与12互素选出来，即 {1,5,7,11} 构成模12的简化剩余系。

        再来一个例子加深理解，设m=6：

        模 6 的完整剩余系：可以是 {0,1,2,3,4,5} 或者 {−2,−1,0,1,2,3} 等。

        模 6 的简化剩余系：可以是 {1,5} 或者 {−1,5} 等，因为只有 1 和 5 与 6 互素。若指定最小非负简化剩余系，则为 {1,5}

        简化剩余系和欧拉函数是RSA算法（最广泛使用的公钥加密算法）中用于选择加解和解密指数的基础， RSA算法的公钥和私钥生成都依赖于简化剩余系的性质。