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

score 5 · Accepted Answer

要求に応じて、簡単な疑似コードを次に示します。

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の複合性を証明しているかどうかをテストします。ifisStrongPseudoprimeが返すComposite数値は間違いなく合成ですが、その逆はProbablyPrime、数値がまだ合成である可能性があるためです。関数はk証人をisPrimeテストします。kの値を設定することで、エラーの可能性を 4^ kで 1 回として判断できます。ほとんどの人は、10 から 25 の間のどこかでkの値を使用します。この関数は、2 乗による累乗を実行します。この関数は、使用している言語で提供されていない場合に提供されます。powerMod

このテストの背後にある数学について詳しく知りたい場合は、私のブログでこのエッセイをお勧めします。これには 5 つの言語での実装も含まれていますが、いずれも VBA ではありません。

編集: 彼はそうは言いませんでしたが、元の投稿者が実際にやりたいことは、200 万未満の素数の合計を見つけて Project Euler 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

ここで使用されているアルゴリズムは、ギリシャの数学者によって 2000 年以上前に発明されたエラトステネスのふるいです。繰り返しになりますが、説明とコードは私のブログのエッセイにあります。

score 4 · Accepted Answer

重要なアイデアと概念(ここでは p は素数を表します) :

フェルマーの小定理。( a^(p-1) = 1 ( mod p ))
p が素数で x^2 = 1 ( mod p ) の場合、 x = +1 または -1 ( mod p ) です。

これは次のように証明できます。

x^2 = 1 ( mod p )
x^2 - 1 = 0 ( mod p )
(x-1)(x+1) = 0 ( mod p )

p が (x-1) と (x+1) の両方を割り切れず、それらの積を割り切れる場合、それは素数にはなりません。これは矛盾です。したがって、p は (x-1) を割るか、(x+1) を割るので、x = +1 または -1 ( mod p ) になります。

p - 1 = 2^d * s で、s が奇数で d >= 0 であると仮定しましょう。 p が素数の場合、この場合のように as = 1 ( mod p ) のいずれかで、 as からの二乗を繰り返すと常に 1 になります。、したがって (a^(p-1))%p は 1 になります。または a^(s*(2^r)) = -1 ( mod p ) 0 <= r < d となるいくつかの r の場合、それから二乗を繰り返すと常に 1 が得られ、最後に a^(p-1) = 1 ( mod p )。これらのいずれも当てはまらない場合、 a^(p-1) は素数 a に対して 1 にはなりません (そうでなければ、事実 #2 と矛盾します)。

アルゴリズム :

素数性をテストする必要がある特定の数値を p とします。
まず、p-1 を (2^d)*s に書き換えます。(ここで、s は奇数で、d >= 0)。
ここで、範囲 [1,n-1] の a を選択し、as = 1 ( mod p ) または a^(s*(2^r)) = -1 ( mod p ) かどうかを確認します。
両方とも失敗した場合、p は間違いなく合成です。それ以外の場合、p はおそらく素数です。別の a を選択して、同じテストを繰り返すことができます。
一定回数の繰り返しの後に停止し、p が確実に合成であるか、おそらく素数であると主張できます。

小さなコード : Miller-Rabin primality テスト、反復はテストの精度を意味します

bool Miller(long long p,int iteration)
{
    if(p<2)
        return false;

    if(p!=2 && p%2==0){
                return false;

        long long s=p-1;
        while(s%2==0)
        {
                s/=2;
        }
        for(int i=0;i<iteration;i++)
        {
                long long a=rand()%(p-1)+1;
            long long temp=s;
                long long mod=modulo(a,temp,p);
                while(temp!=p-1 && mod!=1 && mod!=p-1)
            {
                    mod=mulmod(mod,mod,p);
                    temp *= 2;
                }
                if(mod!=p-1 && temp%2==0)
             {
                    return false;
                }
         }
         return true;
}

パフォーマンスに関するいくつかのポイント:

上記のテストで「a」として選択された場合、任意の合成数 p について、p 未満の数の少なくとも (3/4) が p が合成であることを証明することができます。つまり、1 回反復すると、合成数が素数として返される確率は (1/4) になります。k 回の反復では、テストが失敗する確率は (1/4)k または 4(-k) です。このテストは、フェルマーのテストに比べて比較的低速ですが、特定の合成数では破綻せず、18 ～ 20 回の反復はほとんどのアプリケーションに適しています。

PS: この関数は、a*b がオーバーフローする可能性があることを考慮して (a*b)%c を計算します。

   long long mulmod(long long a,long long b,long long c)
   {
       long long x = 0,y=a%c;
       while(b > 0)
       {
          if(b%2 == 1)
          {
              x = (x+y)%c;
          }
          y = (y*2)%c;
          b /= 2;
       }
       return x%c;
    }

vb.net - この Miller-Rabin Primality テストの疑似コードを簡単な言葉で説明できる人はいますか?

3 に答える 3

Related

Reference