Chương trình C ++ để thực hiện kiểm tra tính nguyên thủy Rabin-Miller để kiểm tra xem một số đã cho có phải là số nguyên tố hay không

Phép thử Tính nguyên tố Rabin-Miller được sử dụng để kiểm tra xem một Số nhất định có phải là Số nguyên tố hay không. Nó tương tự như tính nguyên thủy của định dạng và bài kiểm tra Solovay-Stressen. Thử nghiệm này lần đầu tiên được phát hiện bởi Nhà toán học Nga M. M. Artjuhov.

Thuật toán

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

Mã mẫu

#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;
}

Đầu ra

Enter integer to test primality: 26
26 is not prime