Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина позволяет эффективно определять, является ли данное число составным.
Алгоритм был разработан Гари Миллером в 1976 году и модифицирован Майклом Рабином в 1980 году.
Исходный код функции Миллера — Рабина на С++
Для быстрого возведения числа в степень по модулю используется функцияpow_on_mod. Её реализацию вы можете найти в интернете.
bool test_Miller_Rabin(long long m) {
if(m==2 || m==3)
return true;
if(m % 2 == 0 || m == 1){
return false;
}
long long s = 0;
long long t = m-1;
long long x=0;
long long r1 = 2;
long long r2 = m-2;
long long a;
long long r = (log(m) / log(2));
while(t!=0 && t % 2 == 0){
s++;
t/=2;
}
for(long long i = 0; i < r; i++) {
a
= r1 + rand()%(r2-r1);
x
= pow_on_mod(a,t,m);
if(x==1 || x==m-1) {
continue;
}
for(long long j = 0; j < s-1; j++) {
x
= pow_on_mod(x,2,m);
if(x == 1)
return false;
if(x == m - 1)
break;
}
if(x == m - 1)
continue;
return false;
}
return true;
}
