C ++中大数的模数化指数 [英] Modular Exponentiation for high numbers in C++

问题描述

所以我最近一直在实施米勒 - 拉宾素性测试。我把它限制在所有32位数字的范围，因为这是一个只是为了乐趣的项目，我正在做的是熟悉c ++，我不想与任何64位工作一会儿。另外一个好处是，该算法对所有32位数字都是确定性的，所以我可以显着提高效率，因为我知道什么证人要测试。

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.

数字，算法工作异常好。然而，过程的一部分依赖于模幂运算，即（num ^ pow）％mod。因此，例如

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;

}

正如你可能已经猜到的，都是特别大的数字。例如，如果我想测试数字673109为原始性，我将在某一时刻必须找到：

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

(2 ^ 168277) % 673109

现在2 ^ 168277是一个非常大的数字，在过程中它溢出测试，这导致不正确的评估。

now 2 ^ 168277 is an exceptionally large number, and somewhere in the process it overflows test, which results in an incorrect evaluation.

在反面，参数如

4000111222 ^ 3％1608

4000111222 ^ 3 % 1608

同样的原因。

有没有人有建议的模幂运算可以防止这种溢出和/或操纵它产生正确的结果？ （我看到它，溢出只是另一种形式的模，即num％（UINT_MAX + 1））

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))

推荐答案

通过平方的指数仍然有效用于模幂运算。你的问题不是 2 ^ 168277 是一个非常大的数字，这是你的中间结果之一是一个相当大的数字（大于2 ^ 32），因为673109大于2 ^ 16。

Exponentiation by squaring still "works" for modulo exponentiation. Your problem isn't that 2 ^ 168277 is 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.

所以我认为下面会做。这可能是我错过了一个细节，但基本的想法是有效的，这是如何真正的加密代码可能做大的mod取幂（虽然不是32和64位数字，而是bignums不必大于2 * log（modulus））：

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)):

• 开始乘以指数乘以平方。


• 在64位无符号整数中执行实际的平方。


• 在每个步骤减少模673109，返回到32位范围内。

显然，如果你的C ++实现没有一个64位整数，这有点尴尬，虽然你总是可以假一个。

Obviously that's a bit awkward if your C++ implementation doesn't have a 64 bit integer, although you can always fake one.

幻灯片22的示例如下： http：/ /www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf ，虽然它使用非常小的数字（小于2 ^ 16），所以它可能不会说明你不'

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.

您的其他示例， 4000111222 ^ 3％1608 将在您当前的代码中工作在开始之前减少 4000111222 modulo 1608 。 1608 足够小，可以安全地乘以32位整数中的任意两个mod-1608数字。

Your other example, 4000111222 ^ 3 % 1608 would work in your current code if you just reduce 4000111222 modulo 1608 before you start. 1608 is small enough that you can safely multiply any two mod-1608 numbers in a 32 bit int.

这篇关于C ++中大数的模数化指数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！