Modular exponentiation

This calculator performs the exponentiation of a big integer number over a modulus. A fast algorithm is used, described just below the calculator.

Modular exponentiation

Base

Exponent

Modulus

Calculate

Result

 

 Link  Save  Widget

Fast exponentiation algorithms

The simplest implementation of exponentiation requires N-1 multiplication operations, where N is an exponent base. Despite all the power of modern computers, this method does not suit us since we will use numbers for the exponent, even larger than standard 64-bit integers. E.g., Mersenne Prime number: 618970019642690137449562111 used as default exponent value has 89 bits (see Bit length).
To safely handle such exponents, we must use fast exponentiation algorithms.

In the Polynomial power expansion calculator, we already used fast exponentiation algorithm based on a power tree. It allows minimizing the number of multiplication operations extremely. However, we can not use it with huge exponents since the exponentiation tree consumes too much memory.
This calculator uses the bigInt library implementation of the fast modular exponentiation algorithm based on the binary method. The same article describes a version of this algorithm, which processes the binary digits from most significant to less significant one (from left to right). This is inconvenient for our case since we use variable length big integers and do not know the most significant bit position beforehand.

Binary exponentiation algorithm (right to left).

So the algorithm we use handles the exponent bits from least significant to most significant (from right to left).
The algorithm pseudocode:

a //base
e //exponent
m //modulus
 //modular exponentiation
r ⟵ 1      
while (e!=0) {
            if (e mod 2 = 1) r ⟵ r * a mod m;
            e ⟵ e / 2;
            a = a*a mod m;
        }
output ⟵ r