c++ - 最少非负残基：大量

Question

我正在尝试构建一个可以解决模块化同余的 C++ 程序：

n^p = x (mod q ),

其中 n 是一个小数，p 和 q 是非常大的任意素数。我曾多次尝试这样做，但我总是遇到内存溢出问题。任何帮助表示赞赏。

Answer 1

b ^ e (mod m )有一个简单的算法：

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := e // 2 # integer division
    return x

您不应该计算b ^ e然后执行模运算，因为中间数字会很大。我会留给您使用适合存储所需大量数据的数据类型翻译成您喜欢的语言。我在我的博客上讨论了这个算法。

Answer 2

查看您对问题的评论，听起来您正试图将非常大的值推入无法容纳那么大值的变量中。

在此处查看有关数据类型及其可以容纳的范围的更多信息：http:
//msdn.microsoft.com/en-us/library/s3f49ktz (v=vs.110).aspx

我发现的非负数的最大数据类型范围是unsigned long long. 它的值范围从 0 到 18,446,744,073,709,551,615。