Miller-Rabin PrimalityテストFIPS 186-3実装

Question

FIPS 186-3 C.3.1の説明に従ってMiller-Rabin素数性テストを実装しようとしています。私が何をしても、私はそれを働かせることはできません。指示はかなり具体的で、私は何も見逃しているとは思っていませんが、まだまだ非プライム値のために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 

Answer 1

実装とWik​​ipediaの間の唯一の違いは、第2戻し複合文を忘れてしまったということです。ループの最後にはリターン0が必要です。

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

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なので、常に素数が返されます。先頭に余分なチェックを追加する必要があります。あなたはcontinue;ときz == Wの代わりにbreak;なければならない内側のループで

Answer 2

、

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

。 continueによって、そのループの次の反復で、1つがある場合、zは1になり、候補は誤って複合語と誤って宣言されます。ここで、それは100より小さい素数の間で17,41,73,89および97の間に起こります。