Chương trình C ++ để thực hiện kiểm tra tính nguyên bản Baillie-PSW

Bài kiểm tra tính nguyên sinh Baillie-PSW, bài kiểm tra này được đặt theo tên của Robert Baillie, Carl Pomerance, John Selfridge và Samuel Wagstaff. Đây là một bài kiểm tra để kiểm tra xem một số là số tổng hợp hay có thể là số nguyên tố.

Thuật toán

MillerTest ()

Begin
   Declare a function MillerTest of Boolean type.
   Declare MT_dt and MT_num of integer datatype and pass as the parameter.
   Declare MT_a and MT_x of integer datatype.
      Initialize MT_a = 2 + rand( ) % (MT_num - 4).
      Initialize MT_x = pow(MT_a, MT_dt, MT_num).
   if (MT_x == 1 || MT_x == MT_num - 1) then
      return true.
   while (MT_dt != MT_num - 1) do
      MT_x = (MT_x * MT_x) % MT_num.
      MT_dt *= 2.
      if (MT_x == 1) then
         return false;
      if (MT_x == MT_num - 1) then
         return true.
      return false.
End.

Ví dụ

#include <iostream>
#include<stdlib.h>
using namespace std;
int pow(int pow_a, unsigned int pow_b, int pow_c) {
   int result = 1;
   pow_a = pow_a % pow_c;
   while (pow_b > 0) {
      if (pow_b & 1)
      result = (result * pow_a) % pow_c;
      pow_b = pow_b >> 1;
      pow_a = (pow_a * pow_a) % pow_c;
   }
   return result;
}
bool MiillerTest(int MT_dt, int MT_num) {
   int MT_a = 2 + rand( ) % (MT_num - 4);
   int MT_x = pow(MT_a, MT_dt, MT_num);
   if (MT_x == 1 || MT_x == MT_num - 1)
      return true;
   while (MT_dt != MT_num - 1) {
      MT_x = (MT_x * MT_x) % MT_num;
      MT_dt *= 2;
      if (MT_x == 1)
         return false;
      if (MT_x == MT_num - 1)
         return true;
   }
   return false;
}
bool prime(int P_N, int P_K) {
   if (P_N <= 1 || P_N == 4)
      return false;
   if (P_N <= 3)
      return true;
   int P_D = P_N - 1;
   while (P_D % 2 == 0)
      P_D /= 2;
   for (int i = 0; i < P_K; i++)
      if (MiillerTest(P_D, P_N) == false)
         return false;
      return true;
}
int main() {
   int iter = 50;
   long num1;
   long num2;
   cout<< "Enter the first number: ";
   cin>>num1;
   cout<<endl;
   if (prime(num1, iter))
      cout<<num1<<" is a prime number\n"<<endl;
   else
      cout<<num1<<" is a composite number\n"<<endl;
   cout<<"Enter another number: ";
   cin>>num2;
   cout<<endl;
   if (prime(num2, iter))
      cout<<num2<<" is a prime number\n"<<endl;
   else
      cout<<num2<<" is a composite number\n"<<endl;
   return 0;
}

Đầu ra

Enter the first number: 23
23 is a prime number
Enter another number: 45
45 is a composite number