时间戳

首页 > 解决方案 > 模幂函数为 c 中的大输入生成不正确的结果

c - 模幂函数为 c 中的大输入生成不正确的结果

问题描述

我尝试了两个用于大基数的模幂运算的函数返回错误结果，其中一个函数是：

uint64_t modular_exponentiation(uint64_t x, uint64_t y, uint64_t p) 
{ 
    uint64_t res = 1;      // Initialize result 
    x = x % p;  // Update x if it is more than or  
                // equal to p 
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x) % p;   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
}

对于输入x = 1103362698 ,y = 137911680 , p=1217409241131113809; 它返回值(x^y mod p)：（749298230523009574不正确）。

正确的值为：152166603192600961

我尝试的另一个函数给出了相同的结果，这些函数有什么问题？另一个是：

long int exponentMod(long int A, long int B, long int C) 
{ 
    // Base cases 
    if (A == 0) 
        return 0; 
    if (B == 0) 
        return 1; 
    // If B is even 
    long int y; 
    if (B % 2 == 0) { 
        y = exponentMod(A, B / 2, C); 
        y = (y * y) % C; 
    } 
    // If B is odd 
    else { 
        y = A % C; 
        y = (y * exponentMod(A, B - 1, C) % C) % C; 
    }   
    return (long int)((y + C) % C); 
}

标签： cmodular-arithmeticmodexp

解决方案

当p= 1217409241131113809 时，这个值以及任何中间值res都x将大于 32 位。这意味着将这些数字中的两个相乘可能会导致大于 64 位的值溢出您正在使用的数据类型。

如果将参数限制为 32 位数据类型并将 64 位数据类型用于中间值，则该函数将起作用。否则，您将需要使用大数字库来获得正确的输出。

推荐阅读