【数論】Miller-Rabinアルゴリズム

一つの数が素数であるかどうかを判断する必要があるとき、最も考えやすいのはそのよく知っているO(√n)のアルゴリズムです.そのアルゴリズムはとても簡単で分かりやすいですが、よく考えてみると、nという数字が大きいとき、このアルゴリズムは実は足りないので、時間の複雑さが比較的高いです.
どうやって解決しますか?まず「フェルマの小さな定理」を理解してみましょう.1つの素数pがあり,もう1つの数aとpの相互素があると仮定すると,ap−1≡1(mod p)が得られる.この定理は巧みですね.ある人は考えました.フェルマの定理で一つの数が素数かどうかを判断できますか.すなわち,1つの数pが素数であるか否かを判断するには,ap−1≡1(mod p)が成立するか否かを判断するだけでよい.ここでのaは任意の数であるので,いっそ2に等しくすると,1つの数pが素数であるか否かを判断して2 p−1≡1(mod p)が成り立つか否かを判断する.一見、これは問題ないようです.この式が成立しないとき、pは必ず合数であり、これは問題ない.しかし式が成立するとpは必ず素数ですか?反例を挙げましょう.p＝341では2340≡1(mod 341)が成り立つが,あいにく341＝11＊31は純粋な合数である.これが数学でいう,すべてのaに対して対応する擬素数が存在する.(ps:この問題は基数を完全に変えることで解決できない)
どうすればいいの?実は簡単で、「二次探査」をして偽素数をつかむだけでOKです.これは乱改ではなく,pが素数である場合,方程式x 2≡1(mod p)にはx=1とx=p−1の2本があるという根拠がある.この2つの根は私たちに奇妙な名前を与えられた:平凡な平方根.では,一つの数pが素数であるか否かを判断する問題はまた我々に転化され,モジュールpの意味で1が存在するか否かを判断する非平凡な平方根となり,存在すればpが合数であり,逆に素数となる.このテストは私たちに「親切に」「Miller-Rabinテスト」と呼ばれています.
具体的な手順は次のとおりです.
1複数の基数aを選択してテストする.
2型pが1の非平凡な平方根を探す.p−1=2 t*u(t>=1,uを奇数)、ap−1=a 2 t*u=a 2 tとし、x=au(mod p)を算出し、xを2乗t回、pを型上するたびに、長さt+1のシーケンスを得た.私たちはこのシーケンスが1で終わることを望んでいます.中間のいずれかが1である場合、この項の前の項は1またはn-1でなければならない.そうしないと、pは合数である.
Miller‐Rabin試験でs回試験を行ったが,これはこの試験が単純にFerma小定理を検証したことを意味するものではなく,誤りの確率を大幅に低減し,Miller‐Rabin試験の誤り確率は2−sまでと非常に小さいことが明らかになった.正確さと厳格さを心配する必要はありません
コードは次のとおりです.

#include
using namespace std;

int pow(long long a, long long b, long long n) {
	long long ans = 1;
	while (b) {
		if (b & 1) {
			ans = ans * a % n;
		}
		a = a * a % n;
		b >>= 1;
	}
	return ans;
}

bool judge(long long n, long long a) {
	long long u = 0, t = n - 1;
	while (t % 2 == 0) {u++; t /= 2;}
	long long x = pow(a, t, n);
	
	for (int i = 1; i <= u; i++) {
		long long nx = x * x % n;
		if ((nx == 1) && (x != 1) && (x != n - 1))
			return true;
		x = nx;
	}
	if (x != 1) return true;
	return false;
}

bool miller(long long n, int s) {
	if (n == 2) return true;
	if (n < 2 || n % 2 == 0) return false;
	for (int i = 1; i <= s; i++) {
		long long a = rand() % (n - 2) + 2;
		if (judge(n, a)) return false;
	}
	return true;
}

int main() {
	int t;
	cin >> t;
	long long a;
	while (t--) {
		cin >> a;
		if (miller(a, 10)) {
			cout << "yes" << endl;
		}
		else cout << "no" << endl;
	}
	return 0;
}