c++和太大数(Miller-Rabin素数检验;使用pow()计算幂，然后应用模运算符)

Question

我必须写一个代码，通过Miller-Rabin素数检验来确定一个数字是否是素数。

这里的代码:

#include <iostream>
#include <time.h>
#include <cmath>
#include <stdio.h>  
using namespace std;
int main()
{
srand(time(0));
int m, r, st, a, x, t,st2;
cout << "Введите число m: ";
cin >> m;
cout << "Введите число r: ";
cin >> r;
t = m - 1;
st = 0;
while (t % 2 == 0)
{
st = st + 1;
t = t / 2;
}
for (int i = 0; i < r; i++)
{
a = rand() % (m - 1) + 1;
int y = int(pow(a, t));
if ((int(pow(a, t))) == (1 % m))
{
cout << "Number " << m << " is probably prime" << endl;
exit(0);
}
for (int j = 0; j < st - 1; j++)
{
st2 = int(pow(2, i));
x = int(pow(a, st2 * t));
if (x == -1 % m)
{
continue;
}
else
{
cout << "Number " << m << " is composite" << endl;
exit(0);
}
}
}
cout << "Number " << m << " probably prime" << endl;
}

它在221、12等小数字上表现得很好。但我有一堆数字，其中一个，2633，出了问题:这个数字是质数，但程序说它不是。我做了一行一行运行，发现它卡住了if ((double(pow(a, t))) == (1 % m))这里的问题是，它需要对1到2632之间的某个随机数求329次方。例如，我们将取1595(调试期间随机取的一个数字)。现在我们来计算int y = int(pow(a, t))(把它用于调试，看看它的计算结果)，并与Windows计算器一起工作，我们得到这个数字:

5, 1053 e + 1081795295996211569794748579036

，程序得到-2147483648…每次…

我不知道问题到底在哪里-在pow函数或在数字类型。我也试过用double代替int，但是没有用(我猜是因为5 * 10^1053比double的1.5 * 10^308大得多)

我如何解决这个问题并使它工作?

Answer 1

This

if ((int(pow(a, t))) == (1 % m))

是非常错误的。首先，对于任意m > 1,1 % m就是1。事实上，米勒-拉宾需要

if ( int(pow(a, t)) % m == 1 )

类测试。这就是你在编程语言中执行模运算的方式，你应该修改你的算法以在任何地方使用这种方法，例如(x == -1 % m)应该被(x % m == m-1)取代(因为%总是为非负输入返回一个非负值，-1对应于模运算中的m-1)。

其次，是的，这将很快超出范围。对于大数，先求幂再求模算符并不是一种有效的方法。你应该做的是实现一种模幂算法。最简单的解决方法是

int modular_pow(int base, int exponent, int modulus) {
if (modulus == 1) return 0;

int c = 1;
for (int i = 0; i < exponent; i++)
c = (1LL * c * base) % modulus;  // 1LL to avoid overflow
return c;
}

不是很有效，但至少能完成工作。然后点击

if (modular_pow(a,t,m) == 1)

第三，使用int(pow(...))转换，这可能导致数值错误，因为pow返回一个浮点值。但是你需要精确的值来执行精确的模运算。在这种情况下不要使用pow。在这里阅读更多关于整数pow的信息:实现基于整数的幂函数pow(int, int)的最有效方法，尽管让我提醒你，模幂是你真正需要的。

你的Miller-Rabin的执行可能还有其他问题，但这三个是我看到的最大的问题。