Miller-Rabin-Primalitätstest FIPS 186-3-Implementierung

Question

Ich versuche, den Miller-Rabin-Primzahltest gemäß der Beschreibung in FIPS 186-3 C.3.1 zu implementieren. Egal, was ich tue, ich kann es nicht zur Arbeit bringen. Die Anweisungen sind ziemlich spezifisch, und ich glaube nicht, dass ich etwas verpasst habe, und trotzdem bekomme ich true für nicht-prime Werte.

Was habe ich falsch gemacht?

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 
} 

dies:

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; 

ist mir geben:

0 
1 
1 
1 
0 
1 

Answer 1

Der einzige Unterschied zwischen der Implementierung und Wikipedias ist, dass Sie die zweite Rück Composite-Anweisung vergessen. Sie sollten am Ende der Schleife eine 0 zurückgeben.

Edit: Wie von Daniel erwähnt, gibt es einen zweiten Unterschied. Der Continue setzt die innere Schleife fort und nicht die äußere Schleife, wie es sein sollte.

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 

Auch wenn der Eingang selbst ist, wird es immer wieder zurückkehren wahrscheinlich prime da eine 0 ist Sie sollten dafür eine zusätzliche Kontrolle beim Start hinzuzufügen.

Answer 2

In der inneren Schleife,

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

sollten Sie break; statt continue; wenn z == W. Nach continue wird in der nächsten Iteration dieser Schleife, wenn es eine gibt, z wird 1 und der Kandidat wird möglicherweise fälschlicherweise als Composite deklariert. Hier passiert das für 17, 41, 73, 89 und 97 unter den Primzahlen weniger als 100.