Miller-Rabin(ミラーロビン)素性試験 1151 ワード アルゴリズム思想 2より大きい素数nの場合、n-1をここで、sおよびdは正の整数であり、dは奇数である.すべての整数a(0 {2r*d}\equiv -1 \pmod{n} (for \ some \ r \ that \ 0\leq r \leq s-1)) 測定対象数nについて、見つかったaが上記の条件に合致しない場合、aは「witness for the compositeness of n」と呼ばれ、nは必ず合数である。そうでなければ、aを「strong liar」と呼び、nはaベースの「strong probable prime」である。 せいど すべての奇合数には「witness」の条件を満たすaが多いが,これまで確定されていないアルゴリズムがnに直接基づいてこのような数aを生成できるので,1~n−1の整数を複数回ランダムに抽出してテストすることができる.k回ランダムにaテストを選択すると,このアルゴリズムによって1つの合数が素数と判定される確率は4^(-k)であった。 実装 #include #include using namespace std; typedef long long ll; ll mod_pow(ll x, ll y, ll m) { ll base = x, res = 1; while (y) { if (y&1) (res*=base)%=m; (base*=base)%=m; y>>=1; } return res; } bool MillerRabin(ll n, int k) { if (n==2||n==3||n==5||n==7||n==11||n==13) return true; if (n==1||n%2==0||n%3==0||n%5==0||n%7==0||n%11==0||n%13==0) return false; ll d=n-1; int r=0; while (d%2==0) { d>>=1; ++r; } for (int i=0;i>n) { if (MillerRabin(n,5)) cout< ここでll mod_pow(ll x,ll y,ll m)はモードmの意味での高速べき乗演算を実現する. 拡張読書 詳細な精度、時間の複雑さの分析と証明は参照してください。https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) Unity面接概要-機能実装 テストLSTMのTutorial例