C ++程序实施Rabin-Miller素性测试以检查给定数字是否为素数

Rabin-Miller素数测试用于检查给定数字是否为素数。它类似于格式素数和Solovay-Stressen检验。这项测试最早是由俄罗斯数学家MM Artjuhov发现的。

算法

Begin    ll mulmod(ll a, ll b, ll m)    ll x = 0,y = a mod m    while (b > 0)       if (b mod 2 == 1)          compute x = (x + y) mod m          y = (y * 2) mod m          b = b/ 2    return x mod m. End  Begin    ll modulo(ll base, ll e, ll m)    Initialize:    ll x = 1    ll y = base    while (e > 0)       if (e mod 2 == 1)          x = (x * y) mod m          y = (y * y) mod m          e = e / 2;    return x mod m End  Begin    bool Miller(ll p, int iteration)    if (p < 2)       return false    if (p != 2 and p mod 2==0)       return false;       Compute: ll s = p - 1    while (s mod 2 == 0)       s = s/ 2;       for i = 0 to iteration - 1          Do             ll a = rand() mod (p - 1) + 1, temp = s             ll mod = modulo(a, temp, p)             while (temp != p - 1 and mod != 1 and mod != p - 1)                mod = mulmod(mod, mod, p);                temp *= 2;             if (mod != p - 1 && temp % 2 == 0)                return false             else                return true End

范例程式码

#include <iostream> #include<stdlib.h> #define ll long long using namespace std; ll mulmod(ll a, ll b, ll m)//It returns true if number is prime otherwise false {    ll x = 0,y = a % m;    while (b > 0) {       if (b % 2 == 1) {          x = (x + y) % m;       }       y = (y * 2) % m;       b /= 2;    }    return x % m; }  ll modulo(ll base, ll e, ll m) {    ll x = 1;    ll y = base;    while (e > 0) {       if (e % 2 == 1)          x = (x * y) % m;          y = (y * y) % m;          e = e / 2;    }    return x % m; }  bool Miller(ll p, int iteration) {    if (p < 2) {       return false;    }    if (p != 2 && p % 2==0) {       return false;    }    ll s = p - 1;    while (s % 2 == 0) {       s /= 2;    }    for (int i = 0; i < iteration; i++) {       ll a = rand() % (p - 1) + 1, temp = s;       ll mod = modulo(a, temp, p);       while (temp != p - 1 && mod != 1 && mod != p - 1) {          mod = mulmod(mod, mod, p);          temp *= 2;       }       if (mod != p - 1 && temp % 2 == 0) {          return false;       }    }    return true; }  int main() {    int iteration = 10;    ll num;    cout<<"Enter integer to test primality: ";    cin>>num;    if (Miller(num, iteration))       cout<<num<<" is prime"<<endl;    else       cout<<num<<" is not prime"<<endl;    return 0; }

输出结果

Enter integer to test primality: 26 26 is not prime