vb.net - 有人可以用简单的术语解释这个 Miller-Rabin Primality 测试伪代码吗？

Question

这里是...

Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
Write n − 1 as (2^s)·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← a^d mod n
   if x = 1 or x = n − 1 then do next WitnessLoop
   repeat s − 1 times:
      x ← x^2 mod n
      if x = 1 then return composite
      if x = n − 1 then do next WitnessLoop
   return composite
return probably prime

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

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

Function Miller_Rabin(ByVal n As Integer) As Boolean
    If n <= 3 Then : Return True
    ElseIf n Mod 2 = 0 Then : Return False
    Else
        Dim k, s, a, d, x As Integer
        k = 3
        d = n - 1

        While d Mod 2 = 0
            d = d / 2
            s += 1
        End While

        For c = 1 To k
            a = Random(2, n - 1)
            x = a ^ d Mod n
            If x = 1 Or x = n - 1 Then GoTo skip
            For r = 1 To s - 1
                x = x ^ 2 Mod n
                If x = 1 Then
                    Return False
                    Exit Function
                Else
                    If x = n - 1 Then
                        GoTo skip
                    Else
                        Return False
                        Exit Function
                    End If
                End If
            Next
skip:   Next
        Return True
    End If
End Function

Function Random(ByVal x As Integer, ByVal n As Integer) As Integer
    Dim a As Integer = Now.Millisecond * Now.Second
skip:
    a = (a ^ 2 + 1) Mod (n + 1)
    If a < x Then
        GoTo skip
    Else
        Return a
    End If
End Function

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 次机会。大多数人使用的 k 值介于 10 和 25 之间。powerMod 函数通过平方执行求幂，并在您的语言不提供它的情况下提供你。

如果你想了解更多关于这个测试背后的数学知识，我虚心推荐这个essay在我的博客上，其中还包括五种语言的实现，尽管它们都不是 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

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