C ++程序实施Solovay-Strassen素性测试以检查给定数字是否为素数
Solovay-Strassen素数测试用于测试数字是复数还是素数。
演算法
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 “输入第一个数字：”
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 “输入另一个号码：”
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++) {
//生成一个随机数
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;
}
//驱动程式码
int main() {
int iter = 50;
long num1;
long num2;
cout<< "输入第一个数字： ";
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<<"输入另一个号码： ";
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;
}输出结果
输入第一个数字： 24 24 is a composite number 输入另一个号码： 23 23 is a prime number