Я написал тест простоты Миллера-Рабина на основе следующего псевдокода:
Input: n > 2, an odd integer to be tested for primality;
k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
pick a randomly in the range [2, n − 1]
x ← ad mod n
if x = 1 or x = n − 1 then do next LOOP
for r = 1 .. s − 1
x ← x2 mod n
if x = 1 then return composite
if x = n − 1 then do next LOOP
return composite
return probably prime
Код, который я редко получаю после 31 (если я помещаю его вцикл для проверки чисел от 2 до 100).Должно быть что-то не так, но я не вижу, что это такое.
bool isProbablePrime(ulong n, int k) {
if (n < 2 || n % 2 == 0)
return n == 2;
ulong d = n - 1;
ulong s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
assert(2 ^^ s * d == n - 1);
outer:
foreach (_; 0 .. k) {
ulong a = uniform(2, n);
ulong x = (a ^^ d) % n;
if (x == 1 || x == n - 1)
continue;
foreach (__; 1 .. s) {
x = (x ^^ 2) % n;
if (x == 1) return false;
if (x == n - 1) continue outer;
}
return false;
}
return true;
}
Я также попробовал вариант
...
foreach (__; 1 .. s) {
x = (x ^^ 2) % n;
if (x == 1) return false;
if (x == n - 1) continue outer;
}
if ( x != n - 1) return false; // this is different
...
У меня другая версия теста, которая работаетправильно, но он использует modpow.Я хотел бы иметь версию, которая будет ближе к псевдокоду, который является частью описания задачи rossetta.org .
Редактировать : Re: проблема переполнения.Я подозревал что-то подобное.Я все еще озадачен, почему в версии Ruby такой проблемы нет.Это вероятно обрабатывает это по-другому под капотом.Если я использую BigInt, код работает, но становится намного медленнее, чем когда я использую modpow.Так что я думаю, что я не могу уйти от этого.Жаль, что на Фобосе нет встроенной модпо, или я, должно быть, упустил это из виду.
ulong x = ((BigInt(a) ^^ d) % BigInt(n)).toLong();