密码学数学基础(二)

这次，我们接着来聊密码学有关的数学知识，这一篇就不会有上一篇那么啰嗦了，有那么长的开场白了，先来回顾下，我们上一篇文章学了整除的相关知识和性质，这次我们跟着上一篇文章，接着来学习。

这里，首先说一下，因为考虑到在密码学当中，我们基本上不会用到负数，所以呢，在后续的文章的讨论当中，如果不做特殊说明，我们都在自然数上面来考虑相关的问题。

前景回顾

上文，我们提到了小朋友分桃子的例子，我们来看几种特殊的情况，第一种是只有一个小朋友，那么无论是有多少个桃子(桃子数量大于0)，这样对于桃子来说，总是够分的。第二种是桃子数量和小朋友数量总是一样多的，也就是小朋友数量和桃子数量均为n，这样也总是够分的，也就是每个小朋友都能分到一个桃子。第三种，就是桃子数量为0，那么就是所有的小朋友就都没有桃子了，这么看这也是够分的，那么我们考虑假设我们现在有5个桃子，那么除了上面所说的这三种情况，还有其他的分桃子的方案吗？

这里手动给加个分割线，读者可以先自行思考一下~~~

好了，这里答案是没有的，这也就引出了我们今天所讲的主角 「素数」。在我之前也写过素数相关的文章[^1]，这里，我们来详细讨论一下素数的相关知识，有兴趣的读者也可以去看下我之前写的那篇素数的文章。

素数

**定义1 **设整数. 如果出了显然的因数和之外，n没有其他的因数(约数，因子)，那么我们称n为素数(质数，不可约数)，否则，我们称之为n为合数。

回忆下，刚才我们在前景回顾当中讲到的小朋友分桃子的例子，如果说桃子个数是n，假设是有桃子的，也就是桃子个数要大于0，那么除了只有一个小朋友或者每个小朋友只有一个桃子的分配方案，不存在其他的分配方案了，那么我们说这个桃子个数就是素数。

来看几个例子吧，对于4，6， 10， 15， 21这些就都是合数，而对于2，3，5，7等这些就都是素数了。

「案例1」 找到100以内所有素数

相信，初学过编程语言，或者大学读过计算机相关专业的，应该是都见过这道题的，那么我们当时的代码是怎么写的呢，我们第一版的代码大概率是长这样的，这里为了符合一下大多数读者的入门语言，大学应该都是用的c，那么这里我也用c来写一下吧。

#include <stdio.h>

int if_prime(int num) {
    int i = 0;
    for (i = 2; i < num; i++) {
        if (num % i == 0)
            return 0;
    }
    return 1;
}

int main() {
    for (int i = 2; i <= 100; i++) {
        if (if_prime(i)) {
            printf("%2d is prime num. n", i);
        }
    }
    return 0;
}

相信，这段代码应该初学过c的都可以写得出来，整个思路也非常简单，就是从1到100来判断这个数字是不是素数。

接下来，我们重点来看一下这个判别素数的算法，我们有没有必要把因子给穷举到n呢，相信学过这块的读者应该也想起来了，这里我们只需要穷举到就可以了，至于原因呢，我们来看一下下面的这个定理。

「定理1」 设n是一个正合数，p是n的一个大于1的最小正因数，则p一定是素数，并且有 .

这个定理说明了，假设我们需要判定的n是一个合数，我们一定能在(包括这个值)之前来找到他的最小的因子. 好了，又到了喜闻乐见的证明环节了，对这一块不感兴趣的读者可以直接略过了.

❝

「证明」 我们使用反证法，假设p不是素数，那么存在整数q, 1 < q < p是的 .我们有，通过我们上节课所讲的性质1，我们可以得到 . 在这里我们找到了一个比p要小的因子，这与我们之前的条件p是最小的素因子矛盾，因此我们可以证明p是素数. 因为n是合数，并且p是n的一个因子，也就是 ,根据上一篇文章的有关整除的性质，我们可以得到 . 因此我们可以得到 也就得到了.

❞

好了，我们有了上面的定理，我们来看一个新的方法来找到100以内所有素数这一道题。

Eratoshenes筛法

从上面，我们来看，对于一个合数n，他的最小的素因子一定小于等于n开平方，那么会有如下的一个结论

❝

「定理2」 n是一个正整数，如果对于所有素数都有 那么n一定是一个素数.

❞

这个定理的证明也比较好做，根据定理1，我们知道最小的因子就在之内，然后这些又都不是n的因子，那么n就没有因子了，这也就是说n是一个素数.

通过上面的定理2我们有了一个新的寻找素数的确定算法，这个称之为「Eratoshenes筛法」，这里我就不给这个算法的中文翻译了，本身就是个音译，如果搜一下，翻译的会五花八门，保留下原汁原味，还是用英文吧.

算法描述

• 「算法输入」: 给定任意正整数N（N > 1）

• 「算法输出」: 不超过N的所有的素数

首先列出来N个整数，从中删除不大于的所有素数的倍数.

余下的整数，就是不超过N的所有的素数.

好了，那我们用上面所提供的算法，来回过头来看一下最开始的案例1. 这里，我们稍微变化一下，因为这样我们需要先找到10以内所有是素数，所以呢，我们先来找一下10以内所有素数，这里同样的可以使用「Eratoshenes筛法」来做，但是吧，10以内我们直接来手算一下就可以了，非要用，也不是不行，就是多麻烦一层，我们需要找到以内所有的素数，写到这里了，那就找一下吧，这个就很好找了，因为只有2和3，这个就不用筛法了直接出结果了，然后我们列出来2-10之间所有的数字，下面直接来看一张图吧，我这里懒得每次都截一张图来演示了~~~~

好了，这里我们使用「Eratoshenes筛法」来找到了10以内的所有素数，也就是2, 3, 5, 7,接下来，我们来回到我们的案例1，来找一下100以内所有的素数，同样的，我们来看图.

好了，这么我们就通过「Eratoshenes筛法」来得到了之前样例1的答案，这里我就不把所有的素数给列出来了，读者们看下图就好了。

好了，讲完了如何找到N以内所有的素数那么，回到一个之前讨论过的问题，素数的个数.

素数的个数

在我之前的那篇文章[^1]里面，这里是给证明过的素数有无穷多个，这里就不在重复证明了，有兴趣的读者可以自行翻一下我之前写的文章.

总结

本文主要重新带着读者聊了一下有关素数的知识，有关于素数更加深入的知识，超出我的能力范围了，有兴趣的读者可以去看看公钥密码学的数学基础[^2]一书，以及其中提到的相关文献.

最后呢，还是再来文艺一把，用一句诗词结束本文把。

❝

路漫漫其修远兮，吾将上下而求索 — 屈原

❞

学习道路漫长而久远，愿做知识海洋当中的一叶扁舟，随海浪而行，实际上，我又编不出来了，溜了溜了，下次再见~~~~

参考资料

• 信息安全数学基础-第二版 陈恭亮

[^1]: https://mp.weixin.qq.com/s/glYl6UyeMWL6fPmlRCmZUQ^[1]

[^2]: 公钥密码学的数学基础_王小云_王明强_孟宪萌^[2]

Reference