C ++程序执行Baillie-PSW原始性测试
Baillie-PSW原始性测试，该测试以RobertBaillie，CarlPomerance，JohnSelfridge和SamuelWagstaff的名字命名。这是一项测试，测试数字是合成数字还是可能是质数。
算法
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