密码学数学基础(九)

好久没有写这个系列的文章了，这次咱们来聊聊素性检验的知识吧，友情提示，这节文章需要一点点数论的知识，这里就不给先补一下了，用的的知识其实在之前的文章当中也都提到过。

Fermat素性检验

我们先来回顾下Fermat小定理的内容，如果n是一个素数，则对任意的整数b, ，有

由此可知，如果有一个整数b，使得

则n是一个合数。

现在，我们给出一个通过上面的方案来判定一个数字n是否为素数的方法。

Fermat素性检验算法

• 1）随机选择一个整数，，计算

• 2）如果则n不是素数

• 3）如果计算检查上面的同余式是否成立

• 如果不成立，则n不是素数

• 如果成立，则n是合数的可能性小于，或者说n是素数的可能性大于

• 4）重复上述步骤t次

• 如果说t次都被判定为素数，则我们说n是合数的可能性小于

Carmicheal数

当然，Fermat素性检验在一定条件下是可能存在无效的，我们称这类数为Carmicheal数。

❝

「定义1」 合数n，如果对于所有的正整数b, 都有成立，我们称合数n为「Carmicheal」数。

❞

目前已知的最小的Carmicheal数为561。

好了，这里我们不用代码写了，相信大多数读者可能也不会去写，还是来推广下我的工具箱吧。

如果读者发现某个数字可以通过素性检验，测试次数需要不小于100，并且确定是合数（需要给出一个因子），并且这个数字不是已知的Carmicheal数的话，大概率是我这算法写错了，或者说您的运气实在是太好了，在这个概率下的事件被您给踩中了，建议可以考虑买个彩票玩玩，当然，发现我算法错误，也欢迎联系我 ~~。

Lehmann素性检验

设n是奇素数，我们有同余式

对于任意的整数b成立，因此如果存在整数b，，使得

则n是一个合数，下面给出另一个素数判定的方法，「Lehmann」算法

算法过程

• 需要检测的数字n（）

• 安全参数t（）

• 1）随机选取整数b,

• 2）计算

• 3）如果以及，则r是合数

• 4）如果或者，则r有的概率为素数

• 5）重复上述操作t次，则n为素数的概率为

同样的，这里还是用我的工具箱来演示一下

然后，我们再来看一个相似的素性检验算法，「Solovay-Stassen」素性检验。

Solovay-Stassen素性检验

给定正奇数和安全参数t，按照如下的方式进行计算。

• 1）随机选取整数b,

• 2）计算

• 3）如果以及，则r是合数

• 4）计算Jacobi符号

• 5）如果则n是合数

• 6）重复上面的操作t次

Miller-Rabin素性检验

设n为奇素数，并且有则有如下的因数分解式:

因此，如果有同余式

则以下的同余式至少有一个成立。

因此，如果说我们可以找到一个整数b使得

那么n是合数。

算法

这里我们同样的要求了，虽然的时候算法也是对的，但是明显，我们没必要判断3是否为素数。

• 需要检测的数字n（）

• 安全参数t（）

• 1）计算s, k使得

• 2）随机选取整数b，

• 3）计算

• 4）判断

• a）如果或者通过校验，n可能为素数，返回2）

• b）否则，有或者,计算

• c）如果则通过校验，n可能为素数，返回1）

• d）否则，重新计算，回到c）

• e）如果重复s轮依然没有结果，则返回n是合数

• 5）重复上述2）~4）操作t次，则n为素数的概率为

工具箱链接

链接: https://pan.baidu.com/s/1W4iVPY9zDu5nRYGmZUBudA 提取码: 1387

参考资料

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

• https://en.wikipedia.org/wiki/Primality_test^[1]

• https://en.wikipedia.org/wiki/Solovay–Strassen_primality_test^[2]

• https://stackoverflow.com/questions/8357687/lehmann-test-for-prime-numbers^[3]

• https://math.stackexchange.com/questions/2275905/what-is-the-difference-between-the-lehmann-algorithm-and-lucas-primality-test^[4]

Reference