素性テスト

3649 ワード

数論

素性テストは主に2つの定理を用いた.
Fermaの小さい定理:pが1つの素数で、しかも0残念ながらこの定理は十分ではありません.だから私たちはもう一つの定理を補充してそれを強化します.
二次検出の定理:pが素数であり,0この定理は実によく理解されている.

x ^ 2             ≡ 1 (mod p)
=    x ^ 2 - 1         ≡ 0 (mod p)
=    (x - 1)(x + 1)     ≡ 0 (mod p)

ランダム化
私たちは今数学の公式を持っていますが、問題は解決されていません.pは非常に大きい可能性があるので、すべてのaやxを列挙することは不可能です.
そこで,aを任意に取り,a^(p−1)をテストすることができ,a^(p−1)が使用すべきO(logp)のアルゴリズムを計算し始めた.このアルゴリズムには平方のステップがあり,このステップに二次プローブを置くことで,(定数レベル)時間を節約できる.
アルゴリズムPrimeがfalseを返す場合、整数nは必ず合数である.一方,アルゴリズムPrimeの戻り値がtrueの場合,整数nは高確率で素数である.任意の可能な合数nは、ランダムに選択された基数aに対して、アルゴリズムはtrueを返す.しかし、上記アルゴリズムの深い解析から、nが十分に大きい場合、このような基数aは(n−9)/4個を超えないことが明らかになった.これにより、上記アルゴリズムは偽3/4の正確なモンテカルロアルゴリズムであることがわかる.

#include 
#include 

using namespace std;

typedef unsigned long long ull;

//  ， power result 。 
bool power_and_square_test(ull &result, const ull a, const ull power, const ull mod) {
    if(power % 2 == 0) {
        if(power_and_square_test(result, a, power / 2, mod)) {
            return false;
        }
        result = result * result % mod;
        //  
        return result != 1;
    } else {
        if(power_and_square_test(result, a, power - 1, mod)) {
            return false;
        }
        result = result * a;
        return true;
    }
}

bool prime_test_step(ull a, ull n) {
    ull result;
    if(power_and_square_test(result, a, n - 1, n)) {
        //  
        return result == 1;
    } else {
        return false;
    }
}

//  
bool prime_test(ull n, ull times) {
    srand(clock());
    for(ull i = 0; i < times; ++i) {
        ull a = rand() % n;
        if(prime_test_step(a, n) == false) {
            return false;
        }
    }
    return true;
}

[Java]伯俊1541号[紛失した括弧]Java

公開-7