怎么做网站的seo,制作一个网页游戏需要多少钱,说明书得制作需要哪些材料,网站空间续费不得不啃的密码学数学基础之剩余系是个啥#xff1f;数学里面有好多的定义都有前置的数学概念#xff0c;要想弄懂剩余系还得先说说“同余”。
一、同余 那么“同余”有是个什么呢#xff1f;在谈论“同余”之前#xff0c;我们先圈定个讨论的范围。接下来讨论的都是整数集… 不得不啃的密码学数学基础之剩余系是个啥数学里面有好多的定义都有前置的数学概念要想弄懂剩余系还得先说说“同余”。
一、同余 那么“同余”有是个什么呢在谈论“同余”之前我们先圈定个讨论的范围。接下来讨论的都是整数集合。好了可以正式开始介绍了。
1等价关系与同余 当我们讨论整数集合上的等价关系时“同余”是一个核心概念而由同余关系定义的“同余类”或“剩余类”则是研究整数除法性质和模运算的基本单元。 首先我们需要了解什么是等价关系。在数学中如果集合 上的关系 ∼ 满足以下三个性质则称 ∼ 是 上的等价关系
自反性对于所有 ∈有 ∼对称性对于所有 ,∈若 ∼ 则 ∼传递性对于所有 ,,∈若 ∼ 且 ∼则 ∼ 同余关系就是整数集 上的一种等价关系。两个整数 和 被称为模 同余如果它们被 除后的余数相同记作 ≡ (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的一个简化剩余系称为最小非负简化剩余系。 举例说明简化剩余系 设m12则 {0,1,2,3,4,5,6,7,8,9,10,11} 构成模12的完全剩余系把其中与12互素选出来即 {1,5,7,11} 构成模12的简化剩余系。 再来一个例子加深理解设m6 模 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算法的公钥和私钥生成都依赖于简化剩余系的性质。
