算法实现/数学/模幂运算

算法

这里展示了整数的模幂运算算法 - 一种高效计算 a^e (mod n) 的方法。该通用算法也可用于具有乘法和幂运算的其他代数结构，并且在值的范围有上限 - 模数时效率很高。可以使用此基本算法的其他结构包括具有浮点系数的矩阵幂运算以及有限域上的椭圆曲线计算（虽然在这种情况下操作称为乘法，而不是幂运算）。

低位到高位算法

这是最直观的算法。该算法逐位扫描指数，如果第 n 位的值为 1，则将累加器乘以 a^{2^n}，该累加器是通过在遍历指数时进行连续平方而计算得到的。

伪代码描述如下

function powmod(a, e, n)
    accum := 1
    x = e    // Scan the bits of the exponents
    apow := a // Successive powers, a^(2^n)
    while (x ≠ 0)
         if (x is odd)
              accum := accum × apow (mod n)
         Divide x by 2
         apow : = apow^2 (mod n)
    return accum

高位到低位算法

该算法使用的内存略少 - 不需要单独存储 a 的幂，并且如果底数 a 具有特殊结构（例如，很小），使其易于乘法，则该算法效率更高。该算法从紧随最高位的位到低阶位逐位扫描指数。

伪代码描述如下

function powmod(a, e, n)
    accum := a
    if (e = 0) return 1  // A special case
    for (bitptr := highbit(e) - 1;   bitptr >= 0;  bitptr--)
         accum := accum^2 (mod n)
         if (e[bitptr] = 1)
              accum := accum × a (mod n)
    return accum

C

低位到高位算法

long powmod(long a, long e, long n) {
  long accum = 1, apow, x;
  apow = a; x = e;
  while (x != 0) {
	if (x & 0x01)
      accum = (accum*apow) % n;
	x >>= 1;
	apow = (apow * apow) % n;
  };
  return accum;
}

使用 GMP 的低位到高位算法

GMP 允许使用任意精度进行计算。GMP 库有一个 mpz_powm(result,a,e,n) 函数，因此不需要此函数，但它仅用于说明目的。

// High to Low powmod algorithm
void powmod(mpz_t result, mpz_t a, mpz_t e, mpz_t n) {
  // Use result as accum (temp variable)
  if (mpz_cmp_si(e, 0) == 0) { // If exponent is zero
	mpz_set_ui(result, 1); // Set result to 1
  };
  mpz_set(result, a); // Set value of accum to a
 
  int bitptr = mpz_sizeinbase(e,2) - 1; // Find top bit in exponent
 
  for (bitptr--; bitptr >= 0; bitptr--) {
	mpz_mul(result, result, result); // result <-- result^2
	mpz_fdiv_r(result, result, n);   // result <-- result (mod n)
	if (mpz_tstbit(e,bitptr)) { // Is bit e[bitptr] == 1?
  	   mpz_mul(result, result, a);  	// result <-- result*a
  	   mpz_fdiv_r(result, result, n);   // result <-- result (mod n)
	};
  };
}

Java

低位到高位算法

public static long powmod(long a, long e, long n){
   long accum = 1;
   long x = e;
   long apow = a;
   while (x != 0){
      if ((x & 0x01) == 0x01){
         accum = (accum * apow) % n;
      };
      x >>= 1;
      apow = (apow * apow) % n;
   };
   return accum;
}

使用 BigInteger 的低位到高位算法

Java BigInteger 类有一个 modPow(e, n) 方法，因此不需要此函数，但它仅用于说明目的。

// High to low powmod algorithm
public static BigInteger POWMOD(BigInteger a, BigInteger e, BigInteger n) {
    BigInteger accum = a;
    if (e.equals(BigInteger.ZERO))
        return BigInteger.ONE;
    int bitptr = e.bitLength()-1;
    for (bitptr--; bitptr >= 0; bitptr--) {
        accum = accum.multiply(accum).mod(n);
        if (e.testBit(bitptr)) {
            accum = accum.multiply(a).mod(n);
        };
    };
    return accum;
}

Python

低位到高位算法

Python 有一个 pow(a, e, n) 函数，因此不需要此函数，但它仅用于说明目的。

def powmod(a: int, e: int, n: int) -> int:
    accum: int = 1
    apow2: int = a
    while e > 0:
        if e & 1:
            accum = (accum * apow2) % n
        apow2 = (apow2 * apow2) % n
        e = e >> 1
    return accum