演算法實現/數學/模冪運算

演算法

這裡展示了整數的模冪運算演算法 - 一種高效計算 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