Miller Rabbin
コードについての説明(個人的メモ)
ミラーラビン法は素数判定を高速に行うモンテカルロアルゴリズムである. つまり間違える可能性はあるが高い可能性で正解を返すアルゴリズムである.
$2^{32}$ および $2^{64}$以下などの数については経験的に $3$ 個および $7$ 個のある要素について調べれば十分であることが分かっているためそういう意味では決定的アルゴリズムと考えてもよい.
素数ならばフェルマーの小定理を満たすという必要条件をチェックしていくフェルマーテストでは素数でないのに必ず素数と判定してしまうようなもの(カーマイケル数)が存在するなどの問題があったためこちらの方がより正確な素数判定アルゴリズムと言えるかもしれない.
実装上の注意として long long 型の数($2^{32}$ 以上の数) について素数判定を行う場合は __int128 型の剰余算を途中で行う必要があるが, これがびっくりするくらい遅い(たぶん long long 型の剰余算の $10$ 倍近く遅い).
ただ計算量的には 1 つの数の判定に $\O (|numset| \ast \log (VAL))$ ($VAL$ は判定する数) time とかなのでたくさんの数の素数判定を行わないなら特に気にする必要のない注意である.
numset の値については こちらのサイト が参考になる.
(関数)
check$(n)$ : $n$ が素数であるかどうか(true / false)を返す
時間計算量: $\O (|numset| \ast \log (VAL))$ ($VAL$ は判定する数)
コード
const unsigned int numset[] = {2,7,61}; // < 4,759,123,141 ≒ 4×10^9 までは決定的
// const unsigned long long numset[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022ULL}; // 少なくとも 2^64 までは決定的
// int 型の素数判定の場合
unsigned int mod_pow(unsigned int x, unsigned int k, unsigned int mod){
unsigned int res = 1;
while(k){
if(k & 1) res = (unsigned long long)res * x % mod;
x = (unsigned long long)x * x % mod;
k >>= 1;
}
return res;
}
bool check(unsigned int n){
if(n < 2 || ((n % 6 != 1) && (n % 6 != 5))) return (n == 2) || (n == 3);
unsigned int d = n - 1, s = 0;
while(d % 2 == 0){
d /= 2;
s++;
}
for(unsigned int a : numset){
if(a == n) return true;
unsigned int res = mod_pow(a, d, n);
if(res == 1) continue;
bool ok = true;
for(unsigned int r = 0; r < s; r++){
if(res == n-1){
ok = false;
break;
}
res = (unsigned long long)res * res % n;
}
if(ok) return false;
}
return true;
}
// long long型の素数判定の場合
// unsigned long long mod_mul(unsigned long long a, unsigned long long b, unsigned long long mod) {
// long long ret = a * b - mod * (unsigned long long)((long double)(a) * (long double)(b) / (long double)(mod));
// return ret + mod * (ret < 0) - mod * (ret >= (ll)mod);
// }
// unsigned long long mod_pow(unsigned long long x, unsigned long long k, unsigned long long mod){
// unsigned long long res = 1;
// while(k){
// if(k & 1) res = mod_mul(res, x, mod);
// x = mod_mul(x, x, mod);
// k >>= 1;
// }
// return res;
// }
// bool check(unsigned long long n){
// if(n < 2 || ((n % 6 != 1) && (n % 6 != 5))) return (n == 2) || (n == 3);
// unsigned long long d = n - 1, s = 0;
// while(d % 2 == 0){
// d /= 2;
// s++;
// }
// for(unsigned long long a : numset){
// if(a % n == 0) return true;
// unsigned long long res = mod_pow(a, d, n);
// if(res == 1) continue;
// bool ok = true;
// for(unsigned int r = 0; r < s; r++){
// if(res == n-1){
// ok = false;
// break;
// }
// res = mod_mul(res, res, n);
// }
// if(ok) return false;
// }
// return true;
// }
verify 用の問題
yukicoder : ミラー・ラビン素数判定法のテスト 提出コード