大整数模幂

Question

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

到目前为止我所做的是：扫描 x 和 y 作为字符串，得到 modulo，然后计算 (x^y) mod z.

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

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

#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

首先，我假设 z 相当小（例如，适合 long）。还要注意

(x ^ y) % z = ((x % z) ^ y) % z

所以按照您的方式转换 x 没问题，唯一的问题是 y。方便的是，您只需使用 y 做两件事——将其除以二，然后检查除以二后的余数。如果您将 y 表示为数组，那么这两件事都是微不足道的。首先，为简单起见，反转 y，使最低有效位在前，并在数组中存储数字，而不是数字字符（如存储 5，而不是“5”）。您也可以考虑在每个元素中存储不止一位数字，但这只会提高一个常数。

现在要检查余数，只需检查数组的第一个元素是否可以被二整除（即使它的最低有效位是偶数，该数字也是偶数）。要除以二，请按照以下方式进行操作：

for (int i = 0; i < y_len; ++ i) {
    if (i && y[i] % 2) y[i - 1] += 5;
    y[i] /= 2;
}
if (y_len && y[y_len - 1] == 0) -- y_len;

将此插入到您的 power 例程中，它将正常工作。请注意，您的 power 方法在 y 中是对数的，因此 y 可以达到 10^1000 的事实不会使其变得无法控制地慢。

Answer 2

由于mod平方指数的使用如此之多，所以有它的库。下面是读取a、b、c，输出a^bmodc使用GMP.

的例子

#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

Answer 3

我猜您正在尝试构建一个 Diffie-Hellman Key Exchange 算法。尝试导入 OpenSSL 库，然后使用它的 BN_mod_exp() 函数。

BN_mod_exp() computes a to the p-th power modulo m (r=a^p % m). This function uses less time and space than BN_exp().

来源：https://www.openssl.org/docs/manmaster/crypto/BN_add.html

Answer 4

感谢@v7d8dpo4 对 Euler 的 Totient 函数的解释。我按以下方式编辑了我的代码：

#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);
}

大整数模幂

Big Integer Modular Exponentiation

c

modulus

exponentiation