素性测试

素性测试是一种用于确定给定数字是否为素数的测试，而不是实际将数字分解为其组成素因子（这被称为素因数分解）。

素性测试分为两种类型：确定性测试和概率性测试。确定性测试绝对确定地判断一个数字是否为素数。确定性测试的例子包括卢卡斯-莱默测试和椭圆曲线素性证明。概率性测试可能（尽管概率非常小）错误地将合数识别为素数（但反之则不然）。然而，它们通常远快于确定性测试。因此，通过了概率性素数测试的数字被恰当地称为可能素数，直到它们的素性可以被确定性地证明。

一个通过了概率性测试但实际上是合数的数字被称为伪素数。有许多特定类型的伪素数，最常见的是费马伪素数，它们是尽管是合数但仍满足费马小定理的数。

拉宾-米勒强伪素数测试是一种特别有效的测试。Wolfram 语言实现了基于基数 2 和 3 的多重拉宾-米勒测试，并结合卢卡斯伪素数测试作为函数使用的素性测试PrimeQ[n]。与许多此类算法一样，它是一种使用伪素数的概率性测试。为了保证素性，必须使用速度慢得多的确定性算法。然而，实际上没有已知数字通过了高级概率性测试（如拉宾-米勒测试）但实际上是合数。

任意数字的确定性素性测试的最新技术是椭圆曲线素性证明。截至 2009 年 2 月，程序认证的最大数字PRIMO（7993 位十进制数字）在 2-GHz 处理器上花费了八个月。

与素因数分解不同，长期以来人们认为素性测试是一个P 问题 (Wagon 1991)。然而，直到 Agrawal等人 (2002) 意外地发现了一种多项式时间素性测试算法，其渐近复杂度为 (Bernstein 2002, Clark 2002, Indian Institute of Technology 2002, Pomerance 2002ab, Robinson 2002)。他们的算法后来被称为AKS 素性测试。