calgorithmfunctionlong-long

Power for big numbers modulo m in C


I am using the following function to compute powers of big numbers modulo m, where m is any integer,i.e. (a^b)%m

long long power(long long x, long long y, long long p)
{
    long long 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;
}

But, for some numbers even this function is not working. For example, if I call

 power(1000000000000,9897,52718071807);

I get a negative number as the output. It happens because of the following reason: There is a line in the power function:

  x = (x*x) % p;

When x is big, let's say x=46175307575, the value stored in x after executing x=(x * x)%p becomes negative. I don't understand why it happens. Even if the value of (x * x) crosses the upper range of long long int, I am not storing its value anywhere, I am just storing (x*x)%p whose value should lie between 0 to p. Also, since p doesn't crosses the long long range, how does x cross it? Please tell me why this problem occurs and how to solve this.


Solution

  • At GeeksForGeeks is this function:

    // Returns (a * b) % mod
    long long moduloMultiplication(long long a,
                                   long long b,
                                   long long mod)
    {
        long long res = 0;  // Initialize result
    
        // Update a if it is more than
        // or equal to mod
        a %= mod;
    
        while (b)
        {
            // If b is odd, add a with result
            if (b & 1)
                res = (res + a) % mod;
    
            // Here we assume that doing 2*a
            // doesn't cause overflow
            a = (2 * a) % mod;
    
            b >>= 1;  // b = b / 2
        }
    
        return res;
    }
    

    Use it instead of

    x = (x*x) % p;
    

    I.e.,

    x = moduloMultiplication(x, x, p);
    

    and instead of

    res = (res*x) % p
    

    I.e.,

    res = moduloMultiplication(res, x, p);