Próbuję wprowadzić test prymatu Miller-Rabin zgodnie z opisem podanym w FIPS 186-3 C.3.1. Bez względu na to, co robię, nie mogę go uruchomić. Instrukcje są dość szczegółowe i nie sądzę, żebym przeoczył cokolwiek, a mimo to otrzymuję true
dla wartości innych niż prime.Próba pierwowzoru Millera-Rabin'a Wdrożenie FIPS 186-3
Co zrobiłem źle?
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
}
to:
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;
daje mi:
0
1
1
1
0
1
W jaki sposób wdraża się "POW()? – sarnold
Czy możemy zobaczyć 'POW'? Widzę błąd, który może zadeklarować niektóre liczby pierwsze jako złożone, ale nic nie wyskakuje na odwrót. Za jakie wartości osiągasz złe wyniki? –
Gdzie jest twoja definicja POW? – Antimony