《我的第一本算法书》阅读笔记 7-2 素性测试

r囧r小猫 2022-11-16 13:38 208阅读 0赞

素性测试是判断一个自然数是否为素数的测试。素数（prime number）就是只能被 1 和其自 身整除，且大于 1 的自然数。素数从小到大有 2、3、5、7、11、13……目前在加密技术中被广 泛应用的 RSA 算法就会用到大素数，因此“素性测试”在该算法中起到了重要的作用。

--------------------

![20210407111212614.png][]

我们来试着判断3599是否为素数吧。简单的方法便是将3599按顺序除以比2大的数字，看是否能被 整除。“整除”就是指 mod 运算的结果为 0。由于 3599 的平方根为 59.99…，所以只需要除以从 2 到 59 的数字。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

根据 mod 运算的结果可知，3599 能被 59 整除。也就是说，3599 并不是素数。但假如需要判断的数非 常大，这种方法就十分耗费时间。这种时候就可以用“费马测试”来解决这个问题。

![20210407111302572.png][]

费马测试被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。在讲解费马测试之前， 我们先来学习基础知识——素数的性质。首先来看一看素数5有什么样的性质。

![20210407111350492.png][]

对于比 5 小的数，分别计算它们的 5 次方，结果 如上图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

接下来，再对结果分别进行 mod 运算，求得它 们除以5后的余数，结果如上图所示。

![20210407111455288.png][]

观察原本的数和余数，发现两者一致

![2021040711150910.png][]

由此，可以推导出关于素数5，以上公式成立。

![20210407111811422.png][]

实际上不只是 5，对于任意素数p，上面的公式 都是成立的。这就是“费马小定理”。根据是否 满足费马小定理来判断一个数是否为素数的方 法就是“费马测试”。

![20210407111821622.png][]

那么，我们就用费马测试来判断一下113是否 为素数吧。

![20210407111831581.png][]

随机选择3个比113小的数作为n，计算这些数的113次方，再用113去除得到的结果，求出余数。3 个数最后得到的余数都和原本的数相同，因此可以判断113是素数。

--------------------

确认 n 和余数一致的次数越多，需要判断的数确实为素数的可能性就越大。但是， 如果每一个小于 p 的数都要去计算，就会非常耗费时间。实际上，如果确认了几组 n 和 余数之后就能判断该数是素数的可能性非常高，那么大致就可以判定该数是素数了。

比如在 RSA 算法中，用于素性测试的是根据费马测试改进而来的“米勒 - 拉宾 （Miller-Rabin）素性测试”。用这个方法重复进行测试后，当数不是素数的概率小于 0.580 时，就可以大致判断该数为素数

如果 p 是素数，那么所有比 p 小的数 n 都满足 np mod p ＝ n 这个条件。但反过来， 即使所有 n 都满足条件，p 也有可能不是素数。因为在极低概率下会出现所有 n 都满足 条件的合数（非素数的自然数）。

比如数字 561 可以表示为 3×11×17，所以 561 是合数，不是素数。然而比 561 小 的所有数字都满足上述条件。

这样的合数就叫作“卡迈克尔数”（Carmichael numbers），也叫“绝对伪素数”。下 图按从小到大的顺序列举了一些卡迈克尔数，可以看出这种数字非常少

![20210407111917278.png][]

在过去很长一段时间内，人们都无法确定是否可以应用一个算法在输入规模的多项式时 间内进行（非概率意义，而是决定性的）素性测试。然而在2002年，印度的三位数学家 证明了它的可行性。他们提出的就是“AKS算法”，该名称也是以他们名字的首字母来命 名的。不过，虽说是“在多项式时间内”，但该算法的计算次数仍然较多，所以费马测试 这样的高速算法更为实用，应用范围也更加广泛。

--------------------

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[20210407111212614.png]: /images/20221022/08b2d95a1ec144eca134199cde9a6af8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/d2bbe9a39eea4c15b1f8038ec862d08c.png
[20210407111302572.png]: /images/20221022/6c19e1af88e04aa89244225b778ef8ec.png
[20210407111350492.png]: /images/20221022/5f5435d80b7a44888e190785870a3c0d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/e9d2f385d0e948a89a381e7a05ab7c99.png
[20210407111455288.png]: /images/20221022/7980295d71304be4926ca9e8024eac3d.png
[2021040711150910.png]: /images/20221022/c0299186f5c34b958a6b460ffb5c9b25.png
[20210407111811422.png]: /images/20221022/ddaddf05503643068a1bed683d76fc9f.png
[20210407111821622.png]: /images/20221022/e62882ddaa67490e87476637b4d66f28.png
[20210407111831581.png]: /images/20221022/302b3f06542743d9a7f2121bfd86a063.png
[20210407111917278.png]: /images/20221022/918778f530864610b9a70ef13b32b06a.png