素数检验 --- 跨越 2000 年的人类智慧

概述

<br>

原来早有耳闻的「米勒-拉宾检验」，可以认为是费马小定理的优化版，被广泛用于计算机判断某数是否为质数。…（虽然路径并不相同。AKS 更像是对费马素性检验思路上的优化）

<br>

人类对质数的检验方法的升级，大概经历 4 个阶段，跨越两千年。

1. 埃拉托色尼：地理学之父，首位测量地球周长的人，和秦始皇差不多一个年代。他提出的（暴力尝试）方法，不仅可以判断某个数 n 是否为质数，还可以得到所有小于 n 的质数。但缺陷在于时间复杂度太高，对于大数如 2 的 256 次方，耗时比宇宙年龄还要长，对大数实际没法应用。

2. 费马素性检验：直接基于费马小定理，时间复杂度相比之下低得多，对一个大数 n，可以优化到（以 2 为底 n 的对数）的三次方。这是一个概率算法，即因为有费马证人数和骗子数的存在，得到的结果无法保证 100%准确。更大的缺陷在于有卡迈克尔数（如合数 561），按费马素性检验会得出这是个质数的错误结论。

3. 米勒-拉宾检验，无 卡迈克尔数，并且时间复杂度最优可以到（以 2 为底 n 的对数）的平方——这也是目前计算机应用最广的质数检验方法。

4. AKS 检验算法：方法 2，3 均为概率算法，无法确凿判断某数一定是质数。2002 年三个印度人搞出了 AKS 算法，是精确的而不是概率算法；另外是一般的，不依赖其他（猜想），如最早米勒-拉宾检验，依赖（还未被证明的）广义黎曼猜想。…但这个算法的毛病在于时间复杂度比较高，需要 （以 2 为底 n 的对数）的 12 次方，经过改进也还是要到（以 2 为底 n 的对数）的 6 次方。所以实际用的也不多。

<br>

实践

<br>

费马素性检验

<br>

费马素性检验是一种用于判断一个数是否为素数的方法。它基于费马小定理，该定理指出：如果 ( p ) 是一个素数，而 ( a ) 是小于 ( p ) 的任意正整数，则 ( $a^{p-1}$ ) 除以 ( p ) 的余数恒等于 1。换句话说，对于素数 ( p ) 和任意整数 ( a )，以下等式成立：

费马素性检验通过随机选择 ( a ) 并检查这个等式是否成立来判断一个数是否可能为素数。如果对于多个不同的 ( a ) 值，这个等式都成立，那么这个数很可能是素数。然而，需要注意的是，费马检验是一种概率性测试，它不能完全确定一个数是素数。

下面是用 Go 语言实现费马素性检验的代码，用于检验数字 10021 是否为素数：

package main
import (    "fmt"    "math/big"    "math/rand"    "time")
// 费马素性检验func isPrime(n int, iterations int) bool {    if n < 2 {        return false    }
    for i := 0; i < iterations; i++ {        a := rand.Intn(n-2) + 2        if big.NewInt(0).Exp(big.NewInt(int64(a)), big.NewInt(int64(n-1)), big.NewInt(int64(n))).Cmp(big.NewInt(1)) != 0 {            return false        }    }    return true}
func main() {    num := 10021    iterations := 5 // 这个值越高，结果越准确，但计算量也越大
    rand.Seed(time.Now().Unix()) // 初始化随机数生成器
    if isPrime(num, iterations) {        fmt.Printf("%d is probably a prime number.\n", num)    } else {        fmt.Printf("%d is not a prime number.\n", num)    }}

在上面这个实现中：

1. isPrime 函数执行费马检验。它重复执行指定次数的检验迭代，每次都随机选择一个 ( a ) 并检查是否满足 ( a^{n-1} \equiv 1 \mod n )。

2. 在此使用 Go 的 math/big 包来处理可能的大数运算，因为当数字很大时，常规的整数类型可能无法存储这些值。

3. main 函数中，测试了数字 10021 是否为素数。

需要注意，由于费马检验是概率性的，它可能会产生假阳性，即错误地判断一个合数为素数。在实际应用中，通常将费马检验与其他素性检验方法结合使用，以获得更准确的结果。

<br>

关于 $a^{p-1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}p$ 这个数论公式

<br>

其含义是:

对于素数 p,如果 a 不是 p 的倍数,那么 a 的(p-1)次幂对 p 取模的值等于 1。

详细解释:

• $a^{p-1}$ 表示 a 的(p-1)次幂,即 a 乘自己(p-1)次。

• $\mathrm{m}\mathrm{o}\mathrm{d}p$ 表示对 p 取模。取模运算意味着把计算结果除以 p,取余数。

• 所以 $a^{p-1}\mathrm{m}\mathrm{o}\mathrm{d}p$ 表示把 a 的(p-1)次幂除以 p 后的余数。

• 根据费马小定理,如果 a 不是 p 的倍数,那么这个余数必定是 1。

举个例子:

对于素数 7,如果 2 不是 7 的倍数,那么:

这里 $2^6$ 除以 7 余 1,满足这个公式。

所以这个公式指的是,对于素数 p,任何不被 p 整除的数字 a,其(p-1)次幂在模 p 下都等价于 1。它在密码学和数论中很重要。

<br>

关于 卡迈克尔数

<br>

卡迈克尔数（Carmichael numbers）是一类特殊的合数，它们在数论中具有重要的地位。这些数被命名为卡迈克尔数是为了纪念美国数学家罗伯特·卡迈克尔（Robert Carmichael），他在 1910 年首次描述了这类数。卡迈克尔数的定义与费马小定理密切相关。

<br>

定义：

<br>

卡迈克尔数是满足以下条件的合数 ( n )：对于任何与 ( n ) 互质的整数 ( a )，都有 ( $a^{n-1}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}n$ )。这意味着，虽然卡迈克尔数不是素数，却能通过费马小定理的素性检验。

<br>

历史背景：

<br>

• 罗伯特·卡迈克尔的发现（1910 年）：卡迈克尔首次指出了这类特殊数的存在。他发现了第一个这样的数，561，它是最小的卡迈克尔数。

• 后续研究：在卡迈克尔的工作之后，数学家们发现了更多这样的数，并研究了它们的性质和分布。

<br>

作用：

<br>

• 在素数测试中的重要性：卡迈克尔数在密码学和数论中尤为重要，因为它们是费马素性测试的潜在“陷阱”。由于卡迈克尔数即使不是素数，也能通过基于费马小定理的素性测试，这使得仅仅依赖费马测试来判断素数可能会出错。

• 对密码学的影响：在公钥加密和数字签名算法的设计中，正确识别素数是至关重要的。卡迈克尔数的存在表明，需要更复杂的算法（如米勒-拉宾素性测试）来可靠地区分素数和合数。

• 数论研究：卡迈克尔数对于理解素数的性质和分布提供了重要视角。它们是研究数论中素数和合数特性的一个有趣案例。

卡迈克尔数揭示了数论中一些深刻的现象，并对加密学中素数的检测方法产生了深远的影响。

<br>

米勒-拉宾检验

<br>

米勒-拉宾检验是一种用于确定一个给定的正整数是否为素数的概率性算法。与费马素性检验相比，米勒-拉宾检验更加可靠，因为它对于所谓的“伪素数”（即那些能通过费马检验但实际上是合数的数）的鉴别能力更强。

<br>

基本原理：

<br>

1. 写出 ( n-1 ) 为 ( $2^s\cdot d$ ) 的形式，其中 ( d ) 是奇数。这可以通过不断除以 2 来实现。

2. 选择一个随机数 ( a )（( $2\le a<n-1$ )）。

3. 计算 ( $x=a^d\mathrm{m}\mathrm{o}\mathrm{d}n$ )。如果 ( x ) 等于 1 或( n-1 )，则 ( n ) 可能是素数。

4. 重复平方 ( x ) （即计算 ( $x=x^2\mathrm{m}\mathrm{o}\mathrm{d}n$ )）共 ( s-1 ) 次。在此过程中，如果 ( x ) 变为 1，则 ( n ) 是合数。如果 ( x ) 变为( n-1 )，则 ( n ) 可能是素数。

5. 重复以上步骤多次。每次通过检验，都会大大增加 ( n ) 是素数的概率。通常进行多次迭代以提高准确性。

<br>

用 Go 实现米勒-拉宾检验，并检验 21237 是否为素数

<br>

下面是一个用 Go 语言实现的米勒-拉宾素性检验的示例代码，用于检验数字 21237 是否为素数：

package main
import (    "fmt"    "math/big"    "math/rand"    "time")
// 使用米勒-拉宾算法检查n是否为素数func isPrime(n int64, iterations int) bool {    if n < 2 {        return false    }    if n != 2 && n%2 == 0 {        return false    }
    // 将 n-1 写成 2^s * d 的形式    s := 0    d := n - 1    for d%2 == 0 {        d /= 2        s++    }
    for i := 0; i < iterations; i++ {        a := rand.Int63n(n-2) + 2        x := big.NewInt(0).Exp(big.NewInt(a), big.NewInt(d), big.NewInt(n))
        if x.Cmp(big.NewInt(1)) == 0 || x.Cmp(big.NewInt(n-1)) == 0 {            continue        }
        for r := 0; r < s-1; r++ {            x.Exp(x, big.NewInt(2), big.NewInt(n))            if x.Cmp(big.NewInt(1)) == 0 {                return false            }            if x.Cmp(big.NewInt(n-1)) == 0 {                break            }        }
        if x.Cmp(big.NewInt(n-1)) != 0 {            return false        }    }    return true}
func main() {    num := int64(21237)    iterations := 5 // 这个值越高，结果越可靠，但计算量也越大
    rand.Seed(time.Now().Unix()) // 初始化随机数生成器
    if isPrime(num, iterations) {        fmt.Printf("%d is probably a prime number.\n", num)    } else {        fmt.Printf("%d is not a prime number.\n", num)    }}

在上面代码中，首先将 n-1 表示为 $2^s\ast d$ 的形式，然后对于随机选择的 a，计算 $a^{d}modn$。接下来重复平方 x 并检查其值，以确定 n 是否可能是素数。重复这个过程若干次可以提高测试的准确性。

尽管米勒-拉宾检验是一个概率性测试，但其在实际应用中非常有效且准确度较高。

<br>

AKS 素性检验算法

<br>

AKS 素性检验算法（Agrawal-Kayal-Saxena primality test）是一个在 2002 年由印度计算机科学家Manindra Agrawal和他的学生Neeraj Kayal与Nitin Saxena提出的算法。

这个算法的重要性在于它是第一个被证明对所有数有效的确定性多项式时间素性检验算法。也就是说，对于任何给定的整数，AKS 算法都能在多项式时间内准确地判断它是素数还是合数。

<br>

基本原理：

<br>

1. 检查是否存在幂：首先检查给定的数 ( n ) 是否为 ( $a^b$ )（( $a\in \mathbb{N},b>1$ )）的形式。如果是，( n ) 是合数。

2. 找到最小的 ( r ) 使得 ( $o_r(n)>({\log }_{2}n{)}^2$ )，这里 ( o_r(n) ) 是最小的正整数 ( k ) 使得 ( $n^k\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}r$ )。这一步骤是算法中最具挑战性的部分。

3. 对于所有 ( $1\le a\le \sqrt{\varphi (r)}{\log }_{2}n$ )，检查 ( $\gcd (a,n)=1$ )。如果存在 ( a ) 使得 ( $\gcd (a,n)\ne 1$) 和 ( $1<\gcd (a,n)<n$)，则 ( n ) 是合数。

4. 如果 ( $n\le r$ )，则 ( n ) 是素数。

5. 检查 ( $(X+a{)}^n\equiv X^n+a\mathrm{m}\mathrm{o}\mathrm{d}(X^r-1,n)$ ) 对于所有 ( $1\le a\le \sqrt{\varphi (r)}{\log }_{2}n$ )。如果所有这些都成立，那么 ( n ) 是素数，否则是合数。

<br>

Go 实现 AKS 检验

<br>

AKS 算法的完整实现相对复杂，涉及大量数论概念和高效率计算。在此提供一个精简版本的 Go 实现，用于检验数字 61357 是否为素数。这个实现可能不是最优的，主要用于演示目的：

package main
import (    "fmt"    "math"    "math/big")
// 计算最大公约数func gcd(a, b int64) int64 {    if b == 0 {        return a    }    return gcd(b, a%b)}
// 计算 a^b mod nfunc modPow(a, b, n int64) int64 {    result := int64(1)    a = a % n    for b > 0 {        if b%2 == 1 {            result = (result * a) % n        }        b = b >> 1        a = (a * a) % n    }    return result}
// AKS 素性检验func isPrime(n int64) bool {    // Step 1: 检查 n 是否为 a^b 的形式    for b := int64(2); b*b <= n; b++ {        a := int64(math.Pow(float64(n), 1/float64(b)))        if modPow(a, b, n) == n {            return false        }    }
    // 更多步骤需要实现，但它们在Go中较为复杂    // ...
    return true // 这里的返回值可能不准确，因为算法未完整实现}
func main() {    num := int64(61357)
    if isPrime(num) {        fmt.Printf("%d is probably a prime number.\n", num)    } else {        fmt.Printf("%d is not a prime number.\n", num)    }}

以上代码实现了 AKS 素性检验的第一步，但请注意，为了完整实现 AKS 算法，需要进一步实现更多步骤，这些步骤涉及复杂数论计算。因此，实际应用中一般使用其他更易于实现且效率较高的算法（如米勒-拉宾检验）进行素性检验。 AKS 算法更多地被视为理论上的突破，而在实际应用中则较少使用。

<br>

<br>

更多参考:

米勒拉宾素数检验--Google

米勒-拉宾素性检验