ソロベイ-シュトラッセン素数性テストを実装して、指定された数が素数であるかどうかを確認するC++プログラム

Solovay-Strassen Primality Testは、数値が合成数であるか素数であるかをテストするために使用されます。

アルゴリズム

Begin
   Declare a function modulo to the long datatype to perform binary calculation.
      Declare m_base, m_exp, m_mod of long datatype and pass them as a parameter.
      Declare two variables a, b of long datatype.
         Initialize a = 1, b = m_base.
      while (m_exp > 0) do
         if (m_exp % 2 == 1) then
            a = (a * b) % m_mod.
         b = (b * b) % m_mod.
         m_exp = m_exp / 2.
      Return a % m_mod.
End
Begin
   Declare a function Jecobian of the int datatype to calculate Jacobian symbol of a given number.
   Declare CJ_a, CJ_n of the long datatype and pass them as a parameter.
   if (!CJ_a) then
      return 0.
   Declare answer of the integer datatype.
      Initialize answer = 1.
   if (CJ_a < 0) then
      CJ_a = -CJ_a.
      if (CJ_n % 4 == 3) then
         answer = -answer.
   if (CJ_a == 1) then
      return answer.
   while (CJ_a) do
      if (CJ_a < 0) then
         CJ_a = -CJ_a.
         if (CJ_n % 4 == 3) then
         answer = -answer.
   while (CJ_a % 2 == 0) do
      CJ_a = CJ_a / 2;
      if (CJ_n % 8 == 3 || CJ_n % 8 == 5) then
         answer = -answer.
   swap(CJ_a, CJ_n)
   if (CJ_a % 4 == 3 && CJ_n % 4 == 3) then
      answer = -answer.
         CJ_a = CJ_a % CJ_n;
   if (CJ_a > CJ_n / 2) then
      CJ_a = CJ_a - CJ_n.
   if (CJ_n == 1) then
      return answer.
End
Begin
   Declare a function Solovoystrassen to the Boolean datatype to perform the Solovay-Strassen Primality Test.
      Declare SS_p to the long datatype and pass as a parameter.
      Declare itr to the integer datatype and pass them as a parameter.
      if (SS_p < 2) then
         return false.
      if (SS_p != 2 && SS_p % 2 == 0) then
         return false.
      for (int i = 0; i < itr; i++)
         long a = rand() % (SS_p - 1) + 1;
         long jacob = (SS_p + Jacobian(a, SS_p)) % SS_p;
         long mod = modulo(a, (SS_p - 1) / 2, SS_p);
      if (!jacob || mod != jacob) then
         return false
      return true.
End
Begin
   Declare iter of the integer datatype.
      Initialize iter = 50.
   Declare num1, num2 of the long datatype.
   Print “Enter the first number:”
   Input the value of num1.
   if (Solovoystrassen(num1, iter)) then
      print the value of num1 and ”is a prime number”.
   Else
      print the value of num1 and ”is a composite number”.
   Print “Enter another number:”
      Input the value of num2.
   if (Solovoystrassen(num2, iter)) then
      print the value of num2 and ”is a prime number”.
   Else
      print the value of num2 and ”is a composite number”.
End.

例

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
long modulo(long m_base, long m_exp, long m_mod) // modulo
function to perform binary calculation {
   long a = 1;
   long b = m_base;
   while (m_exp > 0) {
      if (m_exp % 2 == 1)
         a = (a * b) % m_mod;
      b = (b * b) % m_mod;
      m_exp = m_exp / 2;
   }
   return a % m_mod;
}
int Jacobian(long CJ_a, long CJ_n) { // calculate Jacobian symbol of a given number 
   if (!CJ_a)
      return 0;// (0/n) = 0
   int answer = 1;
   if (CJ_a < 0) {
      CJ_a = -CJ_a; // (a/n) = (-a/n)*(-1/n)
      if (CJ_n % 4 == 3)
         answer = -answer; // (-1/n) = -1 if n = 3 (mod 4)
   }
   if (CJ_a == 1)
      return answer; // (1/n) = 1
   while (CJ_a)  {
      if (CJ_a < 0) {
         CJ_a = -CJ_a; // (a/n) = (-a/n)*(-1/n)
         if (CJ_n % 4 == 3)
            answer = -answer; // (-1/n) = -1 if n = 3 (mod 4)
      }
      while (CJ_a % 2 == 0) {
         CJ_a = CJ_a / 2;
         if (CJ_n % 8 == 3 || CJ_n % 8 == 5)
            answer = -answer;
      }
      swap(CJ_a, CJ_n);
      if (CJ_a % 4 == 3 && CJ_n % 4 == 3)
         answer = -answer;
      CJ_a = CJ_a % CJ_n;
         if (CJ_a > CJ_n / 2)
            CJ_a = CJ_a - CJ_n;
   }
   if (CJ_n == 1)
      return answer;
   return 0;
}
bool Solovoystrassen(long SS_p, int itr) { //perform the Solovay- Strassen Primality Test
   if (SS_p < 2)
      return false;
   if (SS_p != 2 && SS_p % 2 == 0)
      return false;
   for (int i = 0; i < itr; i++) {
      // Generate a random number a
      long a = rand() % (SS_p - 1) + 1;
      long jacob = (SS_p + Jacobian(a, SS_p)) % SS_p;
      long mod = modulo(a, (SS_p - 1) / 2, SS_p);
      if (!jacob || mod != jacob)
         return false;
   }
   return true;
}
// Driver Code
int main() {
   int iter = 50;
   long num1;
   long num2;
   cout<< "Enter the first number: ";
   cin>>num1;
   cout<<endl;
   if (Solovoystrassen(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 (Solovoystrassen(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: 24
24 is a composite number
Enter another number: 23
23 is a prime number