揭开密码的神秘面纱——同余运算 Part III

[遇见数学] 核心成员: 蘑菇长颈鹿

一枚数学系的大学生，喜欢数学文化的小视频，翻译中如有问题，请多指正~

密码学中的同余运算 III

欧几里得算法(Euclidean algorithm)，又称辗转相除法，是求最大公约数的算法。它最早出现在欧几里得的《几何原本》中，而在我国可以追溯至东汉出现的《九章算术》。欧几里得算法根据明确定义的规则来执行计算过程，是最常用的最古老算法之一。

欧几里得算法

我们先来回忆一个刚才我们提到的数论中的重要概念——最大公约数(Greatest Common Divisor ())，它是表示可以同时整除两个整数  和  的最大整数。
由于在确定逆的存在性时常常会用到  ,下面我们来探索一种算法来帮助我们快速的找到 。
欧几里得算法(The Euclidean Algorithm)就为我们提供了一种快速找到两个整数之间  的方法。具体方法如下：
  • 若  ，那么  ，同理，若  ，那么  。
  • 将  写成带余除法形式 。
  • 由于  ，利用欧几里得算法找到  即为所求。
  • 若  仍不容易得到，则循环第三步至得出所求。
下面我们通过一个简单的例子来进一步的理解欧几里得算法。
假设我们要寻找  与  之间的 。令  , 由于  , 且 ,而后我们有
因此， 。
也可以观看下面图像演示的过程：
两条线段长分别可表示  和 ，则其中每一小分段长代表最大公约数 。如动画所示，只要辗转地从大数中减去小数，直到其中一段的长度为 ，此时剩下的一条线段的长度就是  和  的最大公因数。
欧几里得算法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数的五倍。法国数学家加布里埃尔·拉梅于 1844 年证明了这点，同时这也标志着计算复杂性理论的开端。
通过上面的例子我们可以看出，欧几里得算法主要是应用了以下几个性质：
  • 及 。
  • 若 ,并且 ,那么  这里  为整数，  为  到  之间的整数。
其中，第一个性质告诉我们当其中一个数是  时怎样找  ，而第二个性质则告诉我们如何将数字大、计算困难的  ，转化为数字小，简单的  来计算。

同余运算小结

同余关系满足等价关系中所有的条件：
  • 自反性：
  • 对称性：若 ，那么
  • 传递性：若 ，且 ，那么
若  ,并且  （或 ，则：
  • 对于任意的  ,
  • 模的数乘运算：对于任意的  ,
  • 模的加法运算：
  • 模的减法运算：
  • 模的幂运算：对于任意的  ,
  • 模的多项式求值运算：对于任意整系数多项式  ,
除此之外对于模的运算我们还有，
  • 对于任意的  , 若 ，则 。
  • 对于任意的与  互质的数  ，若 ，则 。
对于模的逆运算我们有
  • 存在性：当且仅当  与  互质时，存在一个整数  ,使得 。此时我们称  为  模  的逆。
  • 若  并且  存在，则
  • 若  并且  与  互质，则线性同余的解为
  • 费马小定理：若  为质数，并且不整除 , 那么 。
  • 欧拉定理：若  与  互质，那么  ，其中  为欧拉函数。
    欧拉函数的值是所有小于或等于  的正整数中与  互质的数的个数。
  • 费马小定理的推论：若  为质数，那么 （）为模的逆的乘法。更一般的，通过欧拉定理我们知道，如果  和  互质，那么 。
  • 另一个推论：如果  （ 为欧拉函数），那么由  可知，  与  互质。
  • 威尔森定理： 为质数，当且仅当
  • 中国剩余定理：对于任意的 ， 以及与其互质的数  存在唯一的 ，使得  并且 。事实上，，其中  为  模  的逆， 为  模  的逆。
  • 拉格朗日定理：同余式  ，这里  为质数，并且  为整系数多项式，使得  最多有  个根。
  • 原根：如果对于所有与  互质的整数 , 存在一个整数  使得 ，此时称  为模  的原根。模  的原根存在当且仅当  等价于 , 这里  为奇质数， 为正整数。如果模  的原根存在，则有  个原根，这里  为欧拉函数。
  • 二次剩余：若存在整数  ,使得 ，则整数  称为二次剩余模  。欧拉准则称，如果  为奇质数，并且  不是  的整数倍，那么  为模  的二次剩余当且仅当
赞 (0)

相关推荐