Miller Rabin

素性檢測，用來判斷一個數 \(num\) 是否為質數，但提前說明，這是一個充分不必要條件，也就是說， \(num\) 為質數，一定能通過素性檢測，但通過素性檢測的不一定都是質數。

筆者向來喜歡 define int long long ，是以不用擔心本篇文章的資料。

先給出兩個小定理

我們很顯然的知道除了 \(2\) 是一個質數外，其他的偶數必然是合數，那麼我們就能夠知道其他的質數必然是奇數(我們對于 \(2\) 直接特判一下即可) ， 我們就可以将該數 \(n\) 一定可以被表示為 \(n = d\times 2^r + 1\) ,也就是 \(n - 1 = d\times 2^r\)

則以下兩個式子任意滿足一個就說明其實可以通過素性測試的。

\[\begin{cases}

a^d \equiv 1 (mod \ \ n) \\

\exists \ \ 0 \leq i < r , a^{d\times 2^{i}} \equiv -1 (mod \ \ n)

\end{cases}

\]

根據前人的經驗：我們選擇 \(a\) 為100以内的大概 \(10\) 個質數的時候，在 \(long \ \ long\) 範圍内極極極極極小機率會出錯。

滿足其中一個就可以說明通過素性檢測了，但不代表通過素性檢測就是一個素數，哪怕是兩個都滿足，這兩個均為充分不必要條件。

\(Code\)

bool miller_rabin(int n , int a) //檢測 $a$ 這個數是否能讓 $n$ 通過素性測試 
{
	int d = n - 1 , r = 0 ; 
	while(!(d % 2)) {d /= 2 ; r++ ; } // 取出 $d$ 和 $r$ 
	int x = quick(a , d , n) ; // a ^ d % n  
	for(qwq int i = 0 ; i <= r - 1 ; i++) 
	{
		if(x == n - 1) return true ; 
		x = x * x % n ; //這裡應用快速乘 
	} 
	return false ; 
} 
           

另外一種小檢測(更好寫)

費馬小定理，因為前面的兩個小定理都是費馬小定理的擴充形式，那同時是不是說明，我們可以直接通過費馬小定理亂搞呢？這答案經過驗證是可行的。

過程： 我們随機出來一個 \(a\) , 然後我們判斷一下 \(a^{num - 1} \equiv 1(mod \ \ num )\) 是否成立，如果成立我們就認為通過測試了，如果不通過測試，那麼就說明 \(num\) 一定不是質數。然後我們多來幾次，我們就大機率認為其 \(num\) 為質數了。亂搞。！！！

• \(quick\) 表示快速幂

bool query(int num){
    if(num == 2) return true ; 
    for(qwq int i  = 0 ; i  < base ; i++) 
    {
    	int x = rand() % (num - 2) + 2;
    	if(quick(x ,num , num) != x) return false ;
	}
	return true ; 
}
           

其他的素數判斷方法就不必了