有人可以用简单的术语解释这个米勒-拉宾素性测试伪代码吗？

Question

这里是...

\n\n

Input: n > 3, an odd integer to be tested for primality;\nInput: k, a parameter that determines the accuracy of the test\nOutput: composite if n is composite, otherwise probably prime\nWrite n \xe2\x88\x92 1 as (2^s)\xc2\xb7d with d odd by factoring powers of 2 from n \xe2\x88\x92 1\nWitnessLoop: repeat k times:\n   pick a random integer a in the range [2, n \xe2\x88\x92 2]\n   x \xe2\x86\x90 a^d mod n\n   if x = 1 or x = n \xe2\x88\x92 1 then do next WitnessLoop\n   repeat s \xe2\x88\x92 1 times:\n      x \xe2\x86\x90 x^2 mod n\n      if x = 1 then return composite\n      if x = n \xe2\x88\x92 1 then do next WitnessLoop\n   return composite\nreturn probably prime\n

\n\n

我从维基百科关于米勒-拉宾素性测试的文章中得到了这个。但我一直无法理解它......我不想理解它背后的数学，而只想在程序中实现它。在我看来，这个算法有点令人困惑。更好、更简单的伪代码或在 vb.net 中实现它会很有帮助。

\n\n

编辑到目前为止编写的代码：

\n\n

Function Miller_Rabin(ByVal n As Integer) As Boolean\n    If n <= 3 Then : Return True\n    ElseIf n Mod 2 = 0 Then : Return False\n    Else\n        Dim k, s, a, d, x As Integer\n        k = 3\n        d = n - 1\n\n        While d Mod 2 = 0\n            d = d / 2\n            s += 1\n        End While\n\n        For c = 1 To k\n            a = Random(2, n - 1)\n            x = a ^ d Mod n\n            If x = 1 Or x = n - 1 Then GoTo skip\n            For r = 1 To s - 1\n                x = x ^ 2 Mod n\n                If x = 1 Then\n                    Return False\n                    Exit Function\n                Else\n                    If x = n - 1 Then\n                        GoTo skip\n                    Else\n                        Return False\n                        Exit Function\n                    End If\n                End If\n            Next\nskip:   Next\n        Return True\n    End If\nEnd Function\n\nFunction Random(ByVal x As Integer, ByVal n As Integer) As Integer\n    Dim a As Integer = Now.Millisecond * Now.Second\nskip:\n    a = (a ^ 2 + 1) Mod (n + 1)\n    If a < x Then\n        GoTo skip\n    Else\n        Return a\n    End If\nEnd Function\n

\n

Answer 1

根据要求，这是简单的伪代码：

function isStrongPseudoprime(n, a)
    d := n - 1; s := 0
    while d % 2 == 0
        d := d / 2
        s := s + 1
    t := powerMod(a, d, n)
    if t == 1 return ProbablyPrime
    while s > 0
        if t == n - 1
            return ProbablyPrime
        t := (t * t) % n
        s := s - 1
    return Composite

function isPrime(n)
    for i from 1 to k
        a := randInt(2, n-1)
        if isStrongPseudoprime(n, a) == Composite
            return Composite
    return ProbablyPrime

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := e // 2 # integer division
    return x

该isStrongPseudoprime函数测试a是否是n复合性的见证；请注意，如果isStrongPseudoprime返回的Composite数字肯定是合数，但相反的是ProbablyPrime因为有可能该数字仍然是合数。该isPrime功能测试k 个见证人；通过设置k的值，您可以将错误的可能性确定为 4^ k中的 1 次机会。大多数人使用10 到 25 之间的k值。该powerMod函数通过平方执行求幂，并且在您的语言不提供此功能的情况下提供。

如果您想了解更多有关此测试背后的数学知识，我在我的博客上谦虚地推荐这篇文章，其中还包括五种语言的实现，尽管它们都不是 VBA。

编辑：虽然他没有这么说，但原始发布者实际上想要做的是找到小于 200 万的素数之和，从而解决欧拉计划 10。从 2 到n循环数字是一种非常低效的方法对小于n 的素数求和；相反，推荐的方法是使用筛子。再次伪代码：

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

这里使用的算法是埃拉托斯特尼筛法，由希腊数学家在两千多年前发明。同样，我的博客文章中有解释和代码。