Modular multiplicative inverse

Question

I calculating ((A^B)/C)%M, but my code is not working when A,B,C,M are large in numbers. This code is giving right answer when A,B,C,D is small int.

What is wrong here?

Here C and M is co-prime

Sample input 2 3 4 5 Sample output 2

Code fails for these input 969109092 60139073 122541116 75884463

C program

#include <stdio.h>

int d,x,y;

Modular exponential (A^B)%M

int power(int A, int B, int M)
{
    long long int result=1;
    while(B>0)
    {
        if(B % 2 ==1)
        {
            result=(result * A)%M;
        }
        A=(A*A)%M;
        B=B/2;
    }
    return result;
}

Modular multiplicative inverse

void extendedEuclid(int A, int B)
{
    if(B == 0)
    {
        d = A;
        x = 1;
        y = 0;
    }
    else
    {
        extendedEuclid(B,A%B);
        int temp = x;
        x = y;
        y = temp - (A/B)*y;
    }
}

int modInv(int A, int M)
{
    extendedEuclid(A,M);
    return (x%M+M)%M;
}

main()

int main()
{
    int A,B,C,M;
    scanf("%d %d %d %d",&A,&B,&C,&M);
    int inv = modInv(C,M)%M;
    printf("%d\n",inv);
    long long int p = (power(A,B,M))%M;
    printf("%d\n",p);
    long long int ans = (p * inv)%M;
    //printf("%d",((modInv(C,M)*(power(A,B,M))))%M);
    printf("%lld",ans);
    return 0;
}

Answer 1

Code has at least the following issues:

int overflow in A*A. Code needs to calculate the product A*A using wider math. That is why code works with small values, but not large.

// A=(A*A)%M;
A = ((long long)A*A) % M;
// or 
A = (1LL*A*A) % M;

---

Wrong print specifier. This implies compiler warnings are not fully enabled. Save time, Enable them all.

long long int p = (power(A,B,M))%M;
// printf("%d\n",p);
printf("%lld\n",p);

---

Code is amiss with negative values. Rather than patch that int hole, use unsigned types.

unsigned power(unsigned A, unsigned B, unsigned M) {
  unsigned long long result = 1;
  ...

---

Failed corner case in power(A,0,1). result should be 0 when M==1.

// long long int result=1;
long long int result=1%M;

Answer 2

The value of int is probably not large enough, try with long, or double.

Be careful because power returns an int not long long int

Answer 3

You can try the mod_inv C function :

// return a modular multiplicative inverse of n with respect to the modulus.
// return 0 if the linear congruence has no solutions.
unsigned mod_inv(unsigned ra, unsigned rb) {
    unsigned rc, sa = 1, sb = 0, sc, i = 0;
    if (rb > 1) do {
            rc = ra % rb;
            sc = sa - (ra / rb) * sb;
            sa = sb, sb = sc;
            ra = rb, rb = rc;
        } while (++i, rc);
    sa *= (i *= ra == 1) != 0;
    sa += (i & 1) * sb;
    return sa;
}

This is basically the standard algorithm, to avoid overflows the signs are stored into the d variable, you could use a struct to do this. Also, when n = 1 and mod = 0 the output is 0, not 1, i think we have not many computations to execute modulo 0.

The modular multiplicative inverse of an integer N modulo m is an integer n such as the inverse of N modulo m equals n, if a modular inverse exists then it is unique. To calculate the value of the modulo inverse, use the extended euclidean algorithm which finds solutions to the Bezout identity.

Example of usage :

#include <assert.h>

int main(void) {
    unsigned n, mod, res;

    n = 52, mod = 107;
    res = mod_inv(n, mod);
    assert(res == 35); //  35 is a solution of the linear congruence.

    n = 66, mod = 123;
    res = mod_inv(n, mod);
    assert(res == 0); // 66 does note have an inverse modulo 123.
}

/*
    n =     7 and mod = 45    then res = 13    so 1 == (   13 * 7    ) % 45   
    n =    52 and mod = 107   then res = 35    so 1 == (   35 * 52   ) % 107  
    n =   213 and mod = 155   then res = 147   so 1 == (  147 * 213  ) % 155  
    n =   392 and mod = 45    then res = 38    so 1 == (   38 * 392  ) % 45   
    n =   687 and mod = 662   then res = 53    so 1 == (   53 * 687  ) % 662  
    n =   451 and mod = 799   then res = 512   so 1 == (  512 * 451  ) % 799  
    n =  1630 and mod = 259   then res = 167   so 1 == (  167 * 1630 ) % 259  
    n =  4277 and mod = 4722  then res = 191   so 1 == (  191 * 4277 ) % 4722
*/

Source