Baillie-PSW素数性テストを実行するC++プログラム

ベイリー-PSW素数性テスト。このテストは、ロバートベイリー、カールポメランス、ジョンセルフリッジ、サミュエルワグスタッフにちなんで名付けられました。これは、数が合成数であるか素数であるかをテストするテストです。

アルゴリズム

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.

例

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

出力

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