信息安全中的素性测试是什么？

素性测试是一种确定输入数字是否为素数的算法。一些素性测试是确定性的。它们总是能够正确地判断一个数字是素数还是合数。

已知最快的确定性素性测试算法发明于2004年。三位计算机科学家，Agrawal、Kayal和Saxena发明了AKS素性测试，其运行时间为O˜ (log(n)6 )，其中O˜ (f(n))表示为O(f(n).log(f(n))k)，k为某个整数[1]。虽然这是一个重大突破，但与信息安全的要求相比，这个速度相当慢。

素数的优势在于它们被用于密码学。其中一种标准密码系统——RSA算法需要素数作为密钥，通常超过1024位以提供更高的安全性。

处理如此大的数字时，这种方法肯定不好用。处理如此大的数字并不容易，尤其是在素性测试期间执行/和%运算时。

因此，目前产生的最佳素性测试算法只能判断提供的数字是“可能的素数”还是合数。

素性测试主要有以下几种类型：

  • **确定性算法** - 确定性素性测试算法接受一个整数并始终输出素数或合数。该算法总是给出正确的答案。

  • **可分性算法** - 最简单的素性测试如下：

    给定输入数字n，检查从2到n-1的任何整数是否能整除n。如果n能被任何m整除，则n是合数；否则，n是素数。但是，不必测试所有m直到n-1，只需要测试到√n即可。如果n是合数，则它可以分解为两个值，其中至少一个应该小于或等于√n。

  • **概率算法** - 概率算法提供的答案大多数情况下是正确的，但并非所有情况下都是正确的。这些测试确定n是否满足所有素数都应满足的一个或多个条件。概率算法返回素数或合数取决于以下规则：

    • 如果待测试整数实际上是素数，则算法肯定返回素数。

    • 如果待测试整数实际上是合数，则它以1 − ε的概率返回合数，但它也可能以ε的概率返回素数。如果可以运行该算法'm'次，则错误概率可以降低到Σm。

**费马素性测试** - 费马素性测试源于费马小定理，该定理指出，如果n是素数，则an−1 ≡ 1 (mod n)。给定输入n和a < n，可以检查an−1 ≡ 1 (mod n)是否成立。如果不成立，则n是合数；如果成立，则n可能是素数。不幸的是，费马素性测试的错误率很高，许多合数都被认为可能是素数。

更新于：2022年3月16日

6K+ 浏览量

启动您的职业生涯

通过完成课程获得认证

开始学习
广告