原来早有耳闻的「米勒-拉宾检验」,可以认为是费马小定理的优化版,被广泛用于计算机判断某数是否为质数。…(虽然路径并不相同。AKS更像是对费马素性检验思路上的优化)
人类对质数的检验方法的升级,大概经历4个阶段,跨越两千年。
费马素性检验是一种用于判断一个数是否为素数的方法。它基于费马小定理,该定理指出:如果 ( p ) 是一个素数,而 ( a ) 是小于 ( p ) 的任意正整数,则 (
) 除以 ( 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)
}
}
在上面这个实现中:
isPrime
函数执行费马检验。它重复执行指定次数的检验迭代,每次都随机选择一个 ( a ) 并检查是否满足 ( )。
math/big
包来处理可能的大数运算,因为当数字很大时,常规的整数类型可能无法存储这些值。main
函数中,测试了数字 10021 是否为素数。需要注意,由于费马检验是概率性的,它可能会产生假阳性,即错误地判断一个合数为素数。在实际应用中,通常将费马检验与其他素性检验方法结合使用,以获得更准确的结果。
这个数论公式
其含义是:
对于素数p,如果a不是p的倍数,那么a的(p-1)次幂对p取模的值等于1。
详细解释:
表示a的(p-1)次幂,即a乘自己(p-1)次。
表示对p取模。取模运算意味着把计算结果除以p,取余数。
表示把a的(p-1)次幂除以p后的余数。
举个例子:
对于素数7,如果2不是7的倍数,那么:
这里
除以7余1,满足这个公式。
所以这个公式指的是,对于素数p,任何不被p整除的数字a,其(p-1)次幂在模p下都等价于1。它在密码学和数论中很重要。
卡迈克尔数(Carmichael numbers)是一类特殊的合数,它们在数论中具有重要的地位。这些数被命名为卡迈克尔数是为了纪念美国数学家罗伯特·卡迈克尔(Robert Carmichael)[1],他在1910年首次描述了这类数。卡迈克尔数的定义与费马小定理密切相关。
卡迈克尔数是满足以下条件的合数 ( n ): 对于任何与 ( n ) 互质的整数 ( a ),都有 (
)。 这意味着,虽然卡迈克尔数不是素数,却能通过费马小定理的素性检验。
卡迈克尔数揭示了数论中一些深刻的现象,并对加密学中素数的检测方法产生了深远的影响。
米勒-拉宾检验
是一种用于确定一个给定的正整数是否为素数的概率性算法。与费马素性检验
相比,米勒-拉宾检验
更加可靠,因为它对于所谓的“伪素数”(即那些能通过费马检验但实际上是合数的数)的鉴别能力更强。
) 的形式,其中 ( d ) 是奇数。这可以通过不断除以2来实现。
))。
)**。如果 ( x ) 等于1或( n-1 ),则 ( n ) 可能是素数。
))共 ( s-1 ) 次。在此过程中,如果 ( x ) 变为1,则 ( n ) 是合数。如果 ( x ) 变为( n-1 ),则 ( n ) 可能是素数。
下面是一个用 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
表示为
的形式,然后对于随机选择的 a
,计算
。接下来重复平方 x
并检查其值,以确定 n
是否可能是素数。重复这个过程若干次可以提高测试的准确性。
尽管米勒-拉宾检验是一个概率性测试,但其在实际应用中非常有效且准确度较高。
AKS素性检验算法(Agrawal-Kayal-Saxena primality test)是一个在2002年由印度计算机科学家Manindra Agrawal[2]和他的学生Neeraj Kayal[3]与Nitin Saxena[4]提出的算法。
这个算法的重要性在于它是第一个被证明对所有数有效的确定性多项式时间素性检验算法。也就是说,对于任何给定的整数,AKS算法都能在多项式时间内准确地判断它是素数还是合数。
)((
))的形式。如果是,( n ) 是合数。
)**,这里 ( o_r(n) ) 是最小的正整数 ( k ) 使得 (
)。这一步骤是算法中最具挑战性的部分。
),检查 (
)**。如果存在 ( a ) 使得 (
) 和 (
),则 ( n ) 是合数。
),则 ( n ) 是素数。
) 对于所有 (
)**。如果所有这些都成立,那么 ( n ) 是素数,否则是合数。
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 n
func 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算法更多地被视为理论上的突破,而在实际应用中则较少使用。