Modular exponentiation is the computation of an integer power followed by reduction modulo a positive integer. Given a base , a nonnegative exponent , and a modulus , it finds the unique integer satisfying
Its defining computational advantage is that intermediate results can be reduced modulo , avoiding construction of the potentially enormous integer . It is a fundamental operation in number theory, computational mathematics, and public-key cryptography.
Definition and basic properties
In modular arithmetic, integers that differ by a multiple of represent the same residue class. Modular exponentiation depends only on the residue class of the base:
for every nonnegative integer .
The usual exponent laws remain valid:
In particular, the identity
allows reduction after every multiplication.
For , modular exponentiation algorithms use the empty-product convention , including when . The returned residue is therefore . If , every result is . A modulus of zero is not permitted.
For example,
Consequently,
without needing to construct the 85-digit integer .
Binary exponentiation
The standard efficient algorithm is binary exponentiation, also called exponentiation by squaring or square-and-multiply. It uses the identities
Rather than performing approximately multiplications, it processes the digits of in binary notation, requiring only a number of modular multiplications proportional to the bit length of .
A right-to-left version is:
modular_power(a, e, m):
require e >= 0 and m >= 1
result = 1 mod m
base = a mod m
while e > 0:
if e is odd:
result = (result * base) mod m
e = floor(e / 2)
base = (base * base) mod m
return result
At the start of each iteration, the loop maintains
where and are the original inputs. When the remaining exponent becomes zero, this invariant establishes that result is the required residue. A formal correctness argument follows by mathematical induction over the iterations.
A left-to-right version scans exponent bits from most significant to least significant. Starting with , it squares for each bit and then multiplies by if that bit is .
Worked example
To compute , write
Successive squaring gives
Multiplying the powers corresponding to the nonzero binary digits yields
Computational complexity
For , let
be the exponent’s bit length. Binary exponentiation uses modular multiplications, in big-O notation. An implementation that initializes its accumulator with the leading power can use squarings and one additional multiplication for each remaining nonzero exponent bit.
This operation count is not the same as bit complexity. Let be the bit length of . Reduced residues occupy at most bits, while their unreduced products can occupy approximately bits. With schoolbook multiplication and conventional division-based reduction, each modular multiplication costs bit operations, giving an overall bound of
apart from initial input reduction.
More generally, if is the cost of multiplying and reducing two -bit residues, the running time is
Faster multiplication and reduction methods improve this cost.
The basic algorithm stores only a constant number of large integers, although it also needs access to the exponent and temporary workspace. Window-based variants trade additional storage and precomputation for fewer multiplications.
Faster implementation methods
Addition chains and window methods
An addition chain for is a sequence beginning with and ending with , in which each new term is the sum of two earlier terms. Each term corresponds to a power that can be obtained by multiplying two previously computed powers.
Binary exponentiation provides one such chain, but not always the shortest. For example, the chain
computes in five multiplications, whereas the straightforward binary chain takes six.
Fixed-window and sliding-window methods process several exponent bits together and precompute selected powers of the base. They can reduce the multiplication count for large exponents, especially when precomputed values can be reused.
Modular reduction
Montgomery multiplication replaces repeated division by the modulus with operations in a transformed representation. It requires an auxiliary radix coprime to . With a power-of-two radix, this means that must be odd.
Barrett reduction instead uses a precomputed approximation to the reciprocal of the modulus to accelerate reduction. It does not require an odd modulus.
Both techniques are particularly useful when many multiplications share the same modulus, as happens within a modular exponentiation.
Exponent reduction and periodicity
Reducing the base modulo is always valid. Reducing the exponent requires additional conditions.
If the greatest common divisor satisfies , Euler’s theorem gives
where counts the residue classes coprime to . Thus, for nonnegative ,
For a prime modulus with , Fermat’s little theorem specializes this to
More precisely, the powers of an invertible residue repeat with period equal to its multiplicative order: the smallest positive integer such that . This is an instance of the order of an element in group theory.
If and are not coprime, reduction modulo can fail. For example,
but reducing the exponent modulo would incorrectly give
For any fixed base and modulus, the sequence of nonnegative powers is eventually periodic, but it need not be periodic from exponent zero.
When a modulus is decomposed into pairwise coprime factors, powers can be computed separately modulo those factors and recombined using the Chinese remainder theorem.
Negative exponents
A negative exponent is defined modulo only when the base has a multiplicative inverse. Such an inverse exists exactly when
Writing the inverse as , one defines
for positive .
The inverse can be found using the extended Euclidean algorithm. For example,
because , so
If the inverse does not exist, an ordinary single-valued modular power with a negative exponent is undefined.
Applications and security
Modular exponentiation is central to several computational tasks:
- Public-key cryptography. RSA uses exponentiation modulo a product of large primes. Diffie–Hellman key exchange in multiplicative groups uses powers of a shared base modulo a suitable prime.
- Primality testing. Tests such as the Miller–Rabin test examine modular powers for properties expected of prime moduli.
- Computational number theory. Modular powers occur in factorization methods, order computations, and calculations in finite fields.
- Discrete logarithms. Computing is efficient, while recovering from an appropriate group element can be difficult in suitably chosen groups. This contrast underlies discrete-logarithm-based cryptographic systems.
A mathematically correct implementation is not necessarily secure when an exponent is secret. Ordinary square-and-multiply performs different operations for different exponent bits; timing, power consumption, electromagnetic emissions, or memory-access patterns may reveal information about those bits.
Cryptographic implementations therefore use carefully designed operation schedules, constant-time table selection, and, where appropriate, blinding. A fixed multiplication count alone does not establish resistance to leakage: the underlying multiplication, reduction, and memory operations must also be considered.
Integer representation matters as well. In fixed-width machine arithmetic, a product may overflow before the reduction is performed. Implementations use suitably wide intermediates, multiprecision arithmetic, or modular multiplication procedures that avoid overflow. Computing a large integer power approximately with floating-point arithmetic and then taking its remainder is not a substitute for exact modular exponentiation.
Algebraic generalizations
Exponentiation by squaring relies on associativity and an identity element, not specifically on integer multiplication. The same method therefore applies to elements of a ring, including matrices and polynomials reduced modulo another polynomial.
For matrices with entries reduced modulo , binary powering efficiently computes . This supports calculations involving recurrence relations and repeated discrete transformations. Unlike scalars, matrices need not commute with one another, but powers of one fixed matrix still satisfy the identities required by the algorithm.