3

私は現在Project Eulerに取り組んでおり、すべての質問を力ずくで解決しないと、より興味深い (そしてより良い学習体験になる) 可能性があると考えました。質問 3 では、数値の素因数を求められます。私の解決策は、(別の因数分解アルゴリズムを使用して) 数値を因数分解し、因数の素数性をテストすることです。Miller-Rabin Primality テスト用のこのコードを思いつきました (素数テストを徹底的に調査した後)。入力したすべての複合奇数に対して true を返します。誰かが理由を理解するのを手伝ってくれますか? アルゴリズムを正しくコーディングしたと思いました。

    public static boolean isPrime(long num)
{
if(num % 2 == 0)
    return false;
else
{
    double d;
    int r=0;
    while((num-1) % Math.pow(2,r+1) == 0)
        r++;
    d = (num-1) % Math.pow(2,r);
    int[] a = {2,3,5,7,11,13,17,23,31,62,73,1662803};
    boolean primality = true;
    for(int k = 0; k < a.length; k++)
    {
        if((Math.pow(a[k],d)-1) % num != 0)
        {
            for(int s = 0; s < r-1; s++)
            {
                if((Math.pow(a[k],Math.pow(2,s)*d)+1) % num != 0)
                    primality = false;

            }
        }
    }
    return primality;
}
4

1 に答える 1

4

が与えられnum > 3た場合、次のものが必要ですd, r s.t. pow(2,r) * d = num - 1, where d is odd。

num - 1の係数を削除するために、から末尾のゼロを効果的に数えてい2ます。pow(2,r)ただし、そのループの後、が の因数であることがわかりますnum - 1。したがって： 

d = (num-1) % Math.pow(2,r);

常に生成されます: d = 0. %ここで( mod ) を/( div )に置き換えるつもりだったのではないかと思います。それ以外の場合Math.pow(a[k],d)-1は常に yield(0)になり、内側のループは実行されません。

他の人が指摘したように、いくつかの単純なトレース ステートメントまたはアサーションでこれらのエラーが検出されます。整数オーバーフローなど、他の問題があると思います。a[]候補に対するテスト( a-SPRPテスト) のループは、私には完全に間違っているように見えます。

ウィキペディアからアルゴリズムを入手したことがあるかもしれませんが、The Handbook of Applied Cryptography : 4.2.3: Miller-Rabin test, Algorithm: 4.24のより詳細なリファレンスを参照してください。

于 2013-06-13T11:41:34.670 に答える