c - 大整数模幂

Question

如何用 1 计算 (x^y) mod z<= x, y <= 10¹⁰⁰⁰ 和 z 任何正整数 1 <= z < 2³¹ ?

到目前为止我所做的是:将 x 和 y 作为字符串扫描，获取模数，然后计算 (x^y) mod z。

我知道这是错误的，因为 (x^y) mod z 不等于 ((x mod z)^{(y mod z)}) mod z。那我该如何解决呢？

编辑:抱歉，我在创建问题时将 x 和 y 的底部约束设置得如此之高。我只想让其他人关注大整数问题，而不是模幂:)。

#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 1

由于模指数的使用如此之多，因此有它的库。以下是读取 a、b 和 c 并使用 GMP 输出 a^b mod c 的示例.

#include <stdio.h>
#include <gmp.h>

int main(void)
{
  mpz_t a, b, c, d;
  mpz_inits (a, b, c, d, NULL);
  printf ("a: ");
  mpz_inp_str (a, stdin, 10);
  printf ("b: ");
  mpz_inp_str (b, stdin, 10);
  printf ("c: ");
  mpz_inp_str (c, stdin, 10);
  mpz_powm (d, a, b, c); // compute d = a ^ b mod c
  gmp_printf ("a ^ b mod c = %Zd\n", d);
  return 0;
}

用-lgmp编译它。

顺便说一下，a^b ≡ a^{b mod Φ(c)} (mod c)，其中 Φ 是 Euler's totient function