Hello all ,

Hope you all are doing well .

I am looking for an efficient way to multiply two numbers A and B mod C where A,B,C can be in the range [1,10¹⁵] .

Here are the list of the solution which i think can think off but there must be some more fast methods .

Solution 1 : simplest and easiest solution is two switch language to jave,python or to use big int in c++ . I don't fill it is a good technique and would like to do it in c .

Solution 2 : Russian Peasant Multiplication

long long int mulmod(long long int a,long long int b) {
    if (M <= 1000000009) return a * b % M;
 
    long long int res = 0;
    while (a > 0) {
        if (a & 1) {
            res += b;
            if (res >= M) res -= M;
        }
        a >>= 1;
        b <<= 1;
        if (b >= M) b -= M;
    }
    return res;
}

which works in O(log(min(A,B))) time .

I heard of karatsuba algorithm which is very fast. Is it faster than the russian multiplication .. can anyone provide me some implementation stuff or some motivation ..

Any kind of help is appreciated :D :D

EDIT1

EDIT2

long long int mulmod(long long int val, long long int n,long long int mod)
{
    long long int q=((double)val*(double)n/(double)mod);
    long long int res=val*n-mod*q;
    res=(res%mod+mod)%mod;
    return res;
}