homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightNumber theory

Modular exponentiation

The calculator performs modular exponentiation of big numbers.

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

PLANETCALC, Modular exponentiation

Modular exponentiation

Result
 

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 are going to 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 power tree. It allows to extremely minimise number of multiplication operations. However, it cannot be used 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 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 one (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
URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Modular exponentiation

Comments