C ++程序进行Fermat原始性测试

Fermat Primality测试执行以检查给定数字是否为质数。这是此算法的C ++代码。

算法

Begin    modulo(base, e, mod)    a = 1    b = base    while (e > 0)       if (e mod 2 == 1)          a = (a * b) % mod          b = (b * b) % mod          e = e / 2       return a % mod End  Begin    Fermat(ll m, int iterations)    if (m == 1)       return false    done    for (int i = 0; i < iterations; i++)       ll x = rand() mod (m - 1) + 1       if (modulo(x, m - 1, m) != 1)          return false       done    return true End

范例程式码

#include <cstring> #include <iostream> #include <cstdlib> #define ll long long using namespace std; ll modulo(ll base, ll e, ll mod) {    ll a = 1;    ll b = base;    while (e > 0) {       if (e % 2 == 1)          a = (a * b) % mod;          b = (b * b) % mod;          e = e / 2;    }    return a % mod; } bool Fermat(ll m, int iterations) {    if (m == 1) {       return false;    }    for (int i = 0; i < iterations; i++) {       ll x = rand() % (m - 1) + 1;       if (modulo(x, m - 1, m) != 1) {          return false;       }    }    return true; } int main() {    int iteration = 70;    ll num;    cout<<"Enter integer to test primality: ";    cin>>num;    if (Fermat(num, iteration))       cout<<num<<" is prime"<<endl;    else       cout<<num<<" is not prime"<<endl;    return 0; }

输出结果

Enter integer to test primality: 13 is prime