Rabin-Miller-Prime test

Question

运行正常，但当数字是6位数或更多时，它会"崩溃"。我不知道为什么不行。我也没有尝试很多事情来解决它，因为我不知道从哪里开始。我知道，这个测试有一些缺点，我已经做了一些研究。有某些数字，不能检测到的测试，但他们应该过滤掉，当你提高精度

bool testPrime(int primenumber_1)
{
bool even_number_checker = false;
bool prime;
int counter = 0;
int primenumber_mod = 0;
int variable_1 = 1;
int variable_2 = 1;
primenumber_mod = primenumber_1 - 1;
if(primenumber_1 % 2 == 0) return false;
while(primenumber_mod%2 == 0)
{
primenumber_mod/=2;
}
if(even_number_checker == false && primenumber_1        != 43405 && primenumber_1 != 27905)
{
variable_1 = (int)pow(2, primenumber_mod) % primenumber_1;
if(variable_1 != 1 && variable_1 != -1)
{
while(variable_1 + 1 != primenumber_1 &&
variable_1 - 1 != primenumber_1 &&
variable_2 + 1 != primenumber_1 &&
variable_2 -1 != primenumber_1)
{                
if(counter >= 40) break;
variable_2 = (int)pow(variable_1, 2) % primenumber_1;
variable_1 = variable_2;
counter++;
}
prime = (variable_1 + 1 == primenumber_1 ||
variable_2 + 1 == primenumber_1);
}
}
return prime;
}
int primeGenerator()
{
int number = rand()%999900+100000;
while(!testPrime(number))
{
number = rand()%899000+100000;
}
return number;
}
bool testPrimeSafe(int number)
{
for(int i = 2; i < number; i++)
{
if(number % i == 0)
{
return false;
}
}
return true;
}
void testTestPrime()
{
for(int i = 0; i < 10000; i++)
{
int prime = primeGenerator();
if(testPrimeSafe(prime))
{
std::cout << "e[32;42mSUCCESS :: " << prime << "e[0mn";
}
else
{
std::cout << "e[48;5;196;1m*EVIL MORTY THEME PLAYING* :: " << prime << "e[0mn";
}
}
}
int main()
{
srand(time(NULL));
testTestPrime();
}

Answer 1

如果primenumber_mod大于31,(int)pow(2, primenumber_mod)将溢出一个有符号32位整数。如果输入是一个6位数的整数，那么primenumber_mod很可能会比它大得多。