6

FIPS 186-3 C.3.1の説明に従って、Miller-Rabin primality テストを実装しようとしています。私が何をしても、私はそれを機能させることができません。指示はかなり具体的で、何も見逃していないと思いますがtrue、非素数の値を取得しています。

私は何を間違えましたか？

template <typename R, typename S, typename T>
T POW(R base, S exponent, const T mod){
    T result = 1;
    while (exponent){
        if (exponent & 1)
            result = (result * base) % mod;
        exponent >>= 1;
        base = (base * base) % mod;
    }
    return result;
}



// used uint64_t to prevent overflow, but only testing with small numbers for now
bool MillerRabin_FIPS186(uint64_t w, unsigned int iterations = 50){
    srand(time(0));
    unsigned int a = 0;
    uint64_t W = w - 1; // dont want to keep calculating w - 1
    uint64_t m = W;
    while (!(m & 1)){
        m >>= 1;
        a++;
    }

    // skipped getting wlen
    // when i had this function using my custom arbitrary precision integer class,
    // and could get len(w), getting it and using it in an actual RBG 
    // made no difference 

    for(unsigned int i = 0; i < iterations; i++){
        uint64_t b = (rand() % (W - 3)) + 2; // 2 <= b <= w - 2
        uint64_t z = POW(b, m, w);
        if ((z == 1) || (z == W))
            continue;
        else
            for(unsigned int j = 1; j < a; j++){
                z = POW(z, 2, w);
                if (z == W)
                    continue;
                if (z == 1)
                    return 0;// Composite
            }
    }
    return 1;// Probably Prime
}

これ：

std::cout << MillerRabin_FIPS186(33) << std::endl;
std::cout << MillerRabin_FIPS186(35) << std::endl;
std::cout << MillerRabin_FIPS186(37) << std::endl;
std::cout << MillerRabin_FIPS186(39) << std::endl;
std::cout << MillerRabin_FIPS186(45) << std::endl;
std::cout << MillerRabin_FIPS186(49) << std::endl;

私に与えている：

0
1
1
1
0
1
4

2 に答える 2

5

あなたの実装とウィキペディアの実装の唯一の違いは、2 番目の return 複合ステートメントを忘れていることです。ループの最後に return 0 が必要です。

編集：ダニエルが指摘したように、2番目の違いがあります。continue は、想定されているように外側のループではなく、内側のループを継続しています。

for(unsigned int i = 0; i < iterations; i++){
    uint64_t b = (rand() % (W - 3)) + 2; // 2 <= b <= w - 2
    uint64_t z = POW(b, m, w);
    if ((z == 1) || (z == W))
        continue;
    else{
        int continueOuter = 0;
        for(unsigned int j = 1; j < a; j++){
            z = POW(z, 2, w);
            if (z == W)
                continueOuter = 1;
                break;
            if (z == 1)
                return 0;// Composite
        }
        if (continueOuter) {continue;}
    }
    return 0; //This is the line you're missing.
}
return 1;// Probably Prime

また、入力が偶数の場合、a が 0 であるため、常におそらく素数が返されます。最初に追加のチェックを追加する必要があります。

于 2012-06-28T01:10:55.140 に答える
4

内側のループでは、

        for(unsigned int j = 1; j < a; j++){
            z = POW(z, 2, w);
            if (z == W)
                continue;
            if (z == 1)
                return 0;// Composite
        }

whenbreak;の代わりにすべきです。ingにより、そのループの次の繰り返しで、もしあれば1 になり、候補は誤って複合として宣言される可能性があります。ここでは、100 未満の素数のうち、17、41、73、89、および 97 について発生します。continue;z == Wcontinuez

于 2012-06-28T01:31:02.917 に答える