Algorithm Implementation/Mathematics/Modular Exponentiation

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Algorithm[edit | edit source]

Here we show the modular exponentiation algorithm for integers - a way to efficiently compute ae (mod n). This general algorithm may also be used for other algebraic structures which have multiplication and exponentiation and is efficient when the size of values has an upper bound - the modulus. Other structures which can use this basic algorithm include matrix exponentiation with floating point coefficients and elliptic curve computations over finite fields (although in that case the operation is called multiplication, not exponentiation).

Low to High Algorithm[edit | edit source]

This is the most intuitive algorithm. The algorithm scans the exponent, a bit at a time, and if the nth bit has the value 1, multiplies the accumulator by a2^n, which is computed by successive squaring as the exponent is traversed.

A pseudocode description is:

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

High to Low Algorithm[edit | edit source]

This algorithm uses slightly less memory - not requiring separate storage of the powers of a, and is also more efficient if the base a has a special structure (such as being small), making multiplication by it easy. The algorithm scans the exponent, a bit at a time, from the bit immediately following the top bit to the low order bit.

A pseudocode description is:

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[edit | edit source]

Low-to-High algorithm[edit | edit source]

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

Low-to-High algorithm with GMP[edit | edit source]

GMP allows for calculating with arbitrary precision. The GMP library has a mpz_powm(result,a,e,n) function, so this is not needed, but is here strictly for expository value.

// 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[edit | edit source]

Low-to-High algorithm[edit | edit source]

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

Low-to-High algorithm with BigInteger[edit | edit source]

The Java BigInteger class has a modPow(e, n) method, so this is not needed, but is here strictly for expository value.

// 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[edit | edit source]

Low-to-High algorithm[edit | edit source]

Python has a pow(a, e, n) function, so this is not needed, but is here strictly for expository value.

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