1

我正在 C 程序中执行以下模除运算：

(5^6) 模 23 = 8

(5^15) 模 23 = 19

为方便起见，我正在使用以下功能：

int mod_func(int p, int g, int x) {
    return ((int)pow((double)g, (double)x)) % p;
}

但是调用函数时的操作结果不正确：

mod_func(23, 5, 6) //returns 8
mod_func(23, 5, 15) //returns -6

模运算符是否对操作数的大小有一些限制？

4

4 回答 4

3

的整数部分pow(5, 15)不能用 an 表示int（假设 的宽度int是 32 位）。在 C 和 C++ 中，转换（转换表达式中的 fromdouble到）是未定义的行为。int

为了避免未定义的行为，您应该使用fmod函数来执行浮点余数运算。

于 2012-12-19T21:59:00.570 回答
3

5 的 15 次方是 30,517,578,125

您可以存储的int最大值是 2,147,483,647

您可以使用 64 位整数，但请注意double最终转换时会出现精度问题。

从记忆中，数论中有一条关于您正在执行的计算的规则，这意味着您不需要计算全部幂展开来确定模结果。但我可能是错的。自从我学会了这些东西已经太多年了。

啊，这里是：模幂运算

阅读并停止使用doubleand pow=)

int mod_func(int p, int g, int x)
{
    int r = g;
    for( int i = 1; i < x; i++ ) {
        r = (r * g) % p;
    }
    return r;
}
于 2012-12-19T22:02:26.527 回答
1

我的猜测是问题是 5 ^ 15 = 30517578125 大于INT_MAX(2147483647)。您目前正在将其转换为int，这是失败的原因。

于 2012-12-19T22:01:04.720 回答
0

如前所述，您的第一个问题是

int mod_func(int p, int g, int x) {
    return ((int)pow((double)g, (double)x)) % p;
}

是pow(g,x)经常超出int范围，然后您有未定义的行为将该结果转换为int，无论结果int是什么，都没有理由相信它与所需的模数有任何关系。

下一个问题是pow(g,x)as a的结果double可能不准确。除非是 2 的幂，否则即使它在范围内，对于足够大的指数g，数学结果也不能精确表示为 a ，但如果数学结果可以精确表示（取决于 的实现），它也可能发生。doublepow

如果您进行数论计算 - 并且计算幂模整数的余数是一 - 您应该只使用整数类型。

对于手头的情况，您可以通过重复平方来使用取幂，计算所有中间结果的残差。如果模数p足够小而(p-1)*(p-1)不会溢出，

int mod_func(int p, int g, int x) {
    int aux = 1;
    g %= p;
    while(x > 0) {
        if (x % 2 == 1) {
            aux = (aux * g) % p;
        }
        g = (g * g) % p;
        x /= 2;
    }
    return aux;
}

可以。如果p可以更大，则需要使用更宽的类型进行计算。

于 2012-12-19T22:19:03.210 回答