Ronald Sumbayak Ronald Sumbayak - 1 month ago 21
C Question

Big Integer Modular Exponentiation

how to calculate (xy) mod z with 1
<= x, y <= 101000 and z any positive integer 1 <= z < 231

what I have done so far is:
scan x and y as a string, get the modulo, then calculate (xy) mod z.

I know this is wrong cause (xy) mod z not equal with ((x mod z)(y mod z)) mod z. Then how do I solve this?

Edit: sorry I made the bottom constraint of x and y so high when creating the question. I just want to make other focus on the big integer problem, not the modular exponentiation :).

#define MOD z

long long power (long long k, long long n) {
if (n == 1) return k;
else {
long long p = power (k, n/2);
if (n % 2 == 0) return (p * p) % MOD;
else return (((p * p) % MOD) * k) % MOD;
}
}

long long convert (char *n) {
long long number = 0;
int ln = strlen (n);

for (int x = 0; x < ln; x++) {
number = number * 10;
number = (number + (n[x] - '0')) % MOD;
}

return number % MOD;
}

int main () {
char s_x[1111], s_y[1111];
scanf ("%s %s", s_x, s_y);

long long x, y, r;
x = convert (s_x);
y = convert (s_y);
r = power (x, y);

printf ("%lld\n", r);
}

Answer

Thanks to @v7d8dpo4 explanation for Euler's Totient Function. I edited my code as of following:

#define MOD z

long long power (long long k, long long n) {
    if (n == 1) return k;
    else {
        long long p = power (k, n/2);
        if (n % 2 == 0) return (p * p) % MOD;
        else return (((p * p) % MOD) * k) % MOD;
    }
}

long long convert (char *n, int mod) {
    long long number = 0;
    int ln = strlen (n);

    for (int x = 0; x < ln; x++) {
        number = number * 10;
        number = (number + (n[x] - '0')) % mod;
    }

    return number % mod;
}

int main () {
    char s_x[1111], s_y[1111];
    scanf ("%s %s", s_x, s_y);

    long long x, y, r;
    x = convert (s_x, MOD);
    y = convert (s_y, totient (MOD)); // totient (x) is Euler's Totient Function of x
    r = power (x, y);

    printf ("%lld\n", r);
}