Проблемы с тестом Миллера-Рабина

Я пытаюсь отладить свою реализацию стандартного (то есть вероятностного) теста Миллера-Рабина. Это код прямо сейчас, с элементарным выполнением теста в main метод:

#include <iostream>
#include <random>

typedef unsigned long long int ulli;
std::random_device rd;
std::mt19937_64 mt(rd());

ulli upow(ulli x, ulli y) {
if (y == 0)
return 1;
else if (y == 1)
return x;
else if (y % 2 == 0)
return upow(x*x, y/2);
else
return x * upow(x*x, (y-1)/2);
}

bool miller_rabin(ulli n, ulli d) {
std::uniform_int_distribution<ulli> dist(2, n-2);

ulli a = dist(mt);
ulli x = upow(a, d) % n;
if (x == 1 || x == n - 1)
return true;

while (d != n - 1) {
x = x*x % n;
d *= 2;
if (x == 1)
return false;
if (x == n - 1)
return true;
}

return false;
}

bool is_prime(ulli n, ulli k) {
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0)
return false;

ulli d = n - 1;
while (d % 2 == 0)
d /= 2;

for (int i = 0; i < k; ++i) {
if (!miller_rabin(n, d))
return false;
}

return true;
}int main() {
ulli tests = 30;

std::cout << "is_prime(2): " << is_prime(2, tests) << std::endl;
std::cout << "is_prime(10): " << is_prime(10, tests) << std::endl;
std::cout << "is_prime(97): " << is_prime(97, tests) << std::endl;
std::cout << "is_prime(256): " << is_prime(256, tests) << std::endl;
std::cout << "is_prime(179424691): " << is_prime(179424691, tests) << std::endl;
std::cout << "is_prime(32416187563): " << is_prime(32416187563, tests) << std::endl;
}

Проблема, с которой я сейчас сталкиваюсь, заключается в следующем: последние два теста возвращают false, что (потому что они являются оба простых) должно быть невозможно. Даже с таким большим количеством тестов, как я прохожу, is_prime все еще выводит false.

На данный момент, я действительно потерян, что не так. Есть идеи?

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]