C++ 中高数的模幂
所以我最近一直致力于米勒-拉宾素性测试的实现。我将其限制在所有 32 位数字的范围内，因为这是一个只是为了好玩的项目，我正在做这个项目来熟悉 C++，并且我不想使用任何 64 位数字一会儿。额外的好处是，该算法对于所有 32 位数字都是确定性的，因此我可以显着提高效率，因为我确切地知道要测试哪些见证人。
因此，对于较小的数字，该算法效果非常好。然而，该过程的一部分依赖于模幂，即 (num ^ pow) % mod。例如，
3 ^ 2 % 5 =
9 % 5 =
4
下面是我用于模幂运算的代码：
unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
unsigned test;
for(test = 1; pow; pow >>= 1)
{
if (pow & 1)
test = (test * num) % mod;
num = (num * num) % mod;
}
return test;
}
正如您可能已经猜到的，当参数都是异常大的数字时，就会出现问题。例如，如果我想测试数字 673109 的素数，我将在某一时刻必须找到：
(2 ^ 168277) % 673109
现在 2 ^ 168277 是一个非常大的数字，并且在该过程中的某个地方它溢出了测试，这导致错误的评估。
另一方面，
诸如4000111222 ^ 3 % 1608
出于同样的原因，
之类的参数也会错误地计算。有没有人对模幂提出建议，以防止这种溢出和/或操纵它产生正确的结果？ （在我看来，溢出只是模数的另一种形式，即 num % (UINT_MAX+1)）
So I've been working recently on an implementation of the Miller-Rabin primality test. I am limiting it to a scope of all 32-bit numbers, because this is a just-for-fun project that I am doing to familiarize myself with c++, and I don't want to have to work with anything 64-bits for awhile. An added bonus is that the algorithm is deterministic for all 32-bit numbers, so I can significantly increase efficiency because I know exactly what witnesses to test for.
So for low numbers, the algorithm works exceptionally well. However, part of the process relies upon modular exponentiation, that is (num ^ pow) % mod. so, for example,
3 ^ 2 % 5 =
9 % 5 =
4
here is the code I have been using for this modular exponentiation:
unsigned mod_pow(unsigned num, unsigned pow, unsigned mod)
{
unsigned test;
for(test = 1; pow; pow >>= 1)
{
if (pow & 1)
test = (test * num) % mod;
num = (num * num) % mod;
}
return test;
}
As you might have already guessed, problems arise when the arguments are all exceptionally large numbers. For example, if I want to test the number 673109 for primality, I will at one point have to find:
(2 ^ 168277) % 673109
now 2 ^ 168277 is an exceptionally large number, and somewhere in the process it overflows test, which results in an incorrect evaluation.
on the reverse side, arguments such as
4000111222 ^ 3 % 1608
also evaluate incorrectly, for much the same reason.
Does anyone have suggestions for modular exponentiation in a way that can prevent this overflow and/or manipulate it to produce the correct result? (the way I see it, overflow is just another form of modulo, that is num % (UINT_MAX+1))
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
平方求幂对于模幂仍然“有效”。您的问题不在于
2 ^ 168277是一个异常大的数字，而是您的中间结果之一是一个相当大的数字（大于 2^32），因为 673109 大于 2^16 。所以我认为以下内容就可以了。我可能错过了一个细节，但基本思想是有效的，这就是“真正的”加密代码如何进行大模幂运算（尽管不是使用 32 和 64 位数字，而是使用永远不必大于2 * log（模数））：
显然，如果你的 C++ 实现没有 64 位整数，那就有点尴尬了，尽管你总是可以伪造一个。
第 22 张幻灯片上有一个示例： http://www .cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf，尽管它使用非常小的数字（小于 2^16），所以它可能无法说明任何您尚未说明的内容知道。
您的另一个示例，如果您在开始之前将
4000111222模1608减少，则4000111222 ^ 3 % 1608将适用于您当前的代码。1608足够小，您可以安全地将 32 位 int 中的任意两个 mod-1608 数字相乘。Exponentiation by squaring still "works" for modulo exponentiation. Your problem isn't that
2 ^ 168277is an exceptionally large number, it's that one of your intermediate results is a fairly large number (bigger than 2^32), because 673109 is bigger than 2^16.So I think the following will do. It's possible I've missed a detail, but the basic idea works, and this is how "real" crypto code might do large mod-exponentiation (although not with 32 and 64 bit numbers, rather with bignums that never have to get bigger than 2 * log (modulus)):
Obviously that's a bit awkward if your C++ implementation doesn't have a 64 bit integer, although you can always fake one.
There's an example on slide 22 here: http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf, although it uses very small numbers (less than 2^16), so it may not illustrate anything you don't already know.
Your other example,
4000111222 ^ 3 % 1608would work in your current code if you just reduce4000111222modulo1608before you start.1608is small enough that you can safely multiply any two mod-1608 numbers in a 32 bit int.我最近用 C++ 为 RSA 写了一些东西，不过有点混乱。
以及一个示例用法。
它的速度也很快，并且位数不受限制。
I wrote something for this recently for RSA in C++, bit messy though.
And an example usage.
Its fast too, and has unlimited number of digits.
有两件事：
不，它不会，因为在某一时刻你的代码不起作用，因为在某一时刻你有
num = 2^16并且num = ...导致溢出。使用更大的数据类型来保存这个中间值。如何在每个可能的溢出机会处取模，例如：
test = ((test % mod) * (num % mod)) % mod;编辑：
Two things:
No, it does not, since at one point you have Your code does not work because at one point you have
num = 2^16and thenum = ...causes overflow. Use a bigger data type to hold this intermediate value.How about taking modulo at every possible overflow oppertunity such as:
test = ((test % mod) * (num % mod)) % mod;Edit:
LL代表long long int使用上面的递归函数来查找数字的 mod exp。这不会导致溢出，因为它是以自下而上的方式计算的。
示例测试运行：
a = 2和k = 168277显示输出为 518358，这是正确的，并且该函数在O(log(k))时间内运行；LLis forlong long intUse the above recursive function for finding the mod exp of the number. This will not result in overflow because it calculates in a bottom up manner.
Sample test run for :
a = 2andk = 168277shows output to be 518358 which is correct and the function runs inO(log(k))time;您可以使用以下恒等式：
(a * b) (mod m) === (a (mod m)) * (b (mod m)) (mod m)
尝试使用简单的方式并逐步改进。
You could use following identity:
(a * b) (mod m) === (a (mod m)) * (b (mod m)) (mod m)
Try using it straightforward way and incrementally improve.