密码学数学基础(五)

❝

欧几里得算法是所有算法的鼻祖，因为它是现存最古老的非凡算法。高德纳

❞

这是系列文章的第五篇了，前面四篇，我们回顾了小学一二年级所学过的认识整数以及简单的四则运算，本篇文章呢，就需要读者们需要有稍微高一点点的数学基础了，我们来回顾回顾我们小学五年级学过的因数和倍数的相关知识[^1]。

前情提要

上篇文章我们讲述了b进制整数的表示，由于我们在日常生活当中已经熟悉了10进制，因此后续文章，如果不做特殊说明，所有数字表示均为10进制表示，在正式开始本篇文章之前，我们先来回顾一下，我们小学二年级学过的除法的知识，这里先不考虑带余除法。想一想，我们是不是使用小朋友分桃子的例子，比如12个桃子，如果分给4个小朋友，那么每个小朋友将会分到三个桃子，然后呢，如果说是分配给6个小朋友，那么每个小朋友将会分的两个桃子，这里，我们引入了因数的概念，对于12来说，他的因数除了1和其本身，也就是还剩2、3、4、6了，然后呢，对于单个整数的因数是一个方面，我们如果要考虑多个整数，这里就需要思考一下这几个整数的公因数了，本篇文章就主要来聊一聊有关公因数的相关知识。

发展历史

有关于求解最大公约数的算法，我们先来回顾一下它的计算方法的一个简易的历史背景，我可不是为了来多水点字数(此地无银三百两，溜了溜了 ~~)

在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。[^2]

最大公约数

❝

「定义1」 设是n个整数，这里显然要求n>1，若整数d是他们中每一个的因数，则d就叫做. 然后我们可以用我们第一篇文章所学过的整除的知识来表达一下上面这段文字描述

❞

如果整数不全为0，那么整数所有公因数当中最大的那一个公因数叫做最大公约数，记作.

❝

这里我用最大公约数这个中文来表示这个含义，也可以称之为最大公因数，因为最开始我学的名字叫最大公约数，所以说这里维持下我当时的叫法，如果有不同的意见，那就忍忍吧~~

❞

特别的，如果我们称互素。然后，同样的，我们来用数学语言来描述一下最大公约数的概念，

• 这也就表示了，d是一个公因数

• 如果 ，那么 这个保证了d是最大的一个

最大公约数的计算

❝

「案例1」 计算两个数a和b的最大公约数

❞

相信，这个案例学过编程的各位读者大概率都会遇到过，基本上会作为一个编程的小栗子，那么最开始我们是如何计算的呢。

int gcd(int a, int b) {
    if (a < b) {
        int tmp = b;
        b = a;
        a = tmp;
    }
    for (int i = b; i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            return i;
        }
    }
    return -1;
}

我们大概率第一次会写出来这样的代码，这个方法也很好理解，我们来穷举a和b当中所有的因子，然后呢再从其中的公因子当中找到最大的那个。

当然，利用最大公约数的定义，我们是可以得到答案的，但是呢这种方法对于小的两个整数还算是可行的，但是对于密码学当中，我们所使用的整数大多都是1024比特(以rsa为例)，在这种情况下，如果我们想要枚举所有的因子，这个是在有效的计算时间内绝对不可接受的，如果读者不相信，可以试一下。

那么，如何在有效时间内计算出来最大公约数呢，我们在前文的发展历史篇已经介绍过这种方法，也就是「辗转相除法」了，这个曾经在有限域的那篇文章[^3]当中简单的提了一下，这次呢，我们来仔细聊聊，这个算法的核心思想实际上就是带余除法，那么我们来看一下

广义欧几里得除法

设a和b是两个正整数，记，我们反复使用欧几里得除法，有

$$begin{aligned} r_{-2} & = q_{0} cdot r_{-1}+r_{0}, quad 0<r_{0}<r_{-1},\ r_{-1}="" &="q_{1}" cdot="" r_{0}+r_{1},="" quad="" 0<r_{1}<r_{0},\="" r_{0}="" r_{1}+r_{2},="" 0<r_{2}<r_{1}="" text="" {,="" }\="" vdots="" \="" r_{n-3}="" r_{n-2}+r_{n-1},="" 0<r_{n-1}<r_{n-2},\="" r_{n-2}="" r_{n-1}+r_{n},="" 0<r_{n}<r_{n-1},\="" r_{n-1}="" r_{n}+r_{n+1},="" r_{n+1}="0" .="" end{aligned}="" $$=""

$$0=r_{n+1}<r_{n}<r_{n-1}<cdots<r_{1}<r_{0}<r_{-1}=b $$="".

我们来回顾下有限域那篇文章[^3]的内容，

这里只贴出一个流程图了，有关剩余内容，自行回顾下之前的那篇文章吧，然后有关于这个算法的复杂度的估计，可以参考信息安全数学基础[^4]一书的相关章节，这里就不展开了。

贝祖(Bezout)等式

❝

**定理 1 **设a,b是两个正整数，则存在整数s,t使得

❞

这两个数比较容易找到，我们一起来看一下，从上一节的广义欧几里得除法的表达式我们可以发现

然后，我们依次消掉就可以得到对应的整数s和t了。有关于Bezout等式的详细证明，可以参考信息安全数学基础[^4]一书的相关章节，这里也不展开来讲了。

小结

按照惯例，来一个小结，本文呢，主要是和各位读者聊了一下有关求解最大公约数的算法，欧几里得算法，本篇文章所用到的算法用途其实还是蛮广泛的，比如有限域的计算，rsa算法等就用到了这一部分的知识，好了，最后的最后，还是一如既往的文艺一把。

❝

去留无意，闲看庭前花开花落；宠辱不惊，漫随天外云卷云舒 —小窗幽记·集景篇

❞

走在奋斗的路上，不要过分在意一些荣辱，保持一颗平常心便好，咱们下次再见~~

参考资料

[^1]: 苏教版小学五年级数学下册^[1]

[^2]: https://zh.wikipedia.org/zh-hans/輾轉相除法^[2]

[^3]: https://mp.weixin.qq.com/s/r_QOcDFqXW3biIpS0rjAJg^[3]

[^4]: 信息安全数学基础_第二版_陈恭亮^[4]

Reference