Pseudoprime numbers(高速べき乗型+素性試験)

6270 ワード

数論

Pseudoprime numbers

Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)

Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

Output

For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Sample Input

Sample Output

no
no
yes
no
yes
yes

タイトル:

pとaを与え,pがaに基づいた偽素数であるか否かを判断する.
すなわち素数ではないが,aを基数とするフェルマの小定理式ap≡a(mod p)a p≡a(m o d p)を満たす

分析:

直接高速べき乗型取りは上式を満たすか否かを判断し,素数でなければ偽素数である.
フェルマの小さな定理を知っている人は、フェルマの小さな定理の公式が実際に書かれていることを知っています.
ap−1≡1 (mod p) a p − 1 ≡ 1 ( m o d p )
でもこの式で満足するかどうか判断できない、wa
この式を満たすにはpがaを除去できないという条件が必要だ.
でもテーマはa両面同乗aは、すべての整数aに対して成立する陳述を得るためであり、この形式はより便利に使用される.
タイトルも与える最初の式は最初の式で判断しましょう.の
code:

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int S = 8;
ll mul_mod(ll a,ll b,ll mod){
    a %= mod;
    b %= mod;
    ll ans = 0;
    while(b){
        if(b & 1){
            ans += a;
            if(ans >= mod) ans -= mod;
        }
        a <<= 1;
        if(a >= mod) a -= mod;
        b >>= 1;
    }
    return ans;
}

ll q_pow(ll a,ll b,ll mod){
    ll ans = 1;
    a %= mod;
    while(b){
        if(b & 1){
            ans = mul_mod(ans,a,mod);
        }
        a = mul_mod(a,a,mod);
        b >>= 1;
    }
    return ans;
}

bool check(ll a,ll n,ll x,ll t){
    ll ret = q_pow(a,x,n);
    ll last = ret;
    for(int i = 1; i <= t; i++){
        ret = mul_mod(ret,ret,n);
        if(ret == 1 && last != 1 && last != n-1) return true;
        last = ret;
    }
    if(ret != 1) return true;
    return false;
}

bool Miller_Rabin(ll n){
    if(n < 2) return false;
    if(n == 2) return true;
    if((n & 1) == 0) return false;
    ll x = n - 1;
    ll t = 0;
    while((x & 1) == 0){
        x >>= 1;
        t++;
    }
    for(int i = 0; i < S; i++){
        ll a = rand() % (n-1) + 1;
        if(check(a,n,x,t))
            return false;
    }
    return true;
}
int main(){
    ll p,a;
    while(scanf("%lld%lld",&p,&a) != EOF){
        if(p == 0 && a == 0) break;
        if(q_pow(a,p,p) == a && !Miller_Rabin(p)){
            printf("yes
");
        }
        else printf("no
");
    }
    return 0;
}

Spring(2)

データベース・ストレージ・ファイルのテスト方法