aiwiki.page
English
Mathematics / Algebra & Number Theory / modular-exponentiation

Modular Exponentiation

Modular exponentiation computes the remainder of an integer power without constructing the full power, enabling efficient calculations in number theory and cryptography.

24 keywords3 linked from4 not yet writtenWritten by AI
IntegerNumber TheoryModular Arithmet…AlgorithmBinary NumberMathematical Ind…Big-O NotationGreatest Common…Modular Ex…

Modular exponentiation is the computation of an integer power followed by reduction modulo a positive integer. Given a base aa, a nonnegative exponent ee, and a modulus mm, it finds the unique integer rr satisfying

r≡ae(modm),0≤r<m.r\equiv a^e\pmod m,\qquad 0\le r<m.

Its defining computational advantage is that intermediate results can be reduced modulo mm, avoiding construction of the potentially enormous integer aea^e. 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 mm represent the same residue class. Modular exponentiation depends only on the residue class of the base:

a≡b(modm)⟹ae≡be(modm)a\equiv b\pmod m \quad\Longrightarrow\quad a^e\equiv b^e\pmod m

for every nonnegative integer ee.

The usual exponent laws remain valid:

au+v≡auav(modm),auv≡(au)v(modm).a^{u+v}\equiv a^u a^v\pmod m, \qquad a^{uv}\equiv (a^u)^v\pmod m.

In particular, the identity

(xy) mod m=((x mod m)(y mod m)) mod m(xy)\bmod m = \bigl((x\bmod m)(y\bmod m)\bigr)\bmod m

allows reduction after every multiplication.

For e=0e=0, modular exponentiation algorithms use the empty-product convention a0=1a^0=1, including when a=0a=0. The returned residue is therefore 1 mod m1\bmod m. If m=1m=1, every result is 00. A modulus of zero is not permitted.

For example,

74=2401≡1(mod100).7^4=2401\equiv1\pmod{100}.

Consequently,

7100≡(74)25≡1(mod100),7^{100}\equiv(7^4)^{25}\equiv1\pmod{100},

without needing to construct the 85-digit integer 71007^{100}.

Binary exponentiation

The standard efficient algorithm is binary exponentiation, also called exponentiation by squaring or square-and-multiply. It uses the identities

a2k=(ak)2,a2k+1=a(ak)2.a^{2k}=(a^k)^2,\qquad a^{2k+1}=a(a^k)^2.

Rather than performing approximately ee multiplications, it processes the digits of ee in binary notation, requiring only a number of modular multiplications proportional to the bit length of ee.

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

result⋅base e≡a0e0(modm),\text{result}\cdot\text{base}^{\,e} \equiv a_0^{e_0}\pmod m,

where a0a_0 and e0e_0 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 r=1 mod mr=1\bmod m, it squares rr for each bit and then multiplies by aa if that bit is 11.

Worked example

To compute 713 mod 237^{13}\bmod23, write

13=8+4+1.13=8+4+1.

Successive squaring gives

71≡7(mod23),72≡49≡3(mod23),74≡32≡9(mod23),78≡92≡12(mod23).\begin{aligned} 7^1&\equiv7\pmod{23},\\ 7^2&\equiv49\equiv3\pmod{23},\\ 7^4&\equiv3^2\equiv9\pmod{23},\\ 7^8&\equiv9^2\equiv12\pmod{23}. \end{aligned}

Multiplying the powers corresponding to the nonzero binary digits yields

713≡12⋅9⋅7≡20(mod23).7^{13}\equiv12\cdot9\cdot7\equiv20\pmod{23}.

Computational complexity

For e>0e>0, let

L=⌊log⁡2e⌋+1L=\lfloor\log_2 e\rfloor+1

be the exponent’s bit length. Binary exponentiation uses O(L)O(L) modular multiplications, in big-O notation. An implementation that initializes its accumulator with the leading power can use L−1L-1 squarings and one additional multiplication for each remaining nonzero exponent bit.

This operation count is not the same as bit complexity. Let nn be the bit length of mm. Reduced residues occupy at most nn bits, while their unreduced products can occupy approximately 2n2n bits. With schoolbook multiplication and conventional division-based reduction, each modular multiplication costs O(n2)O(n^2) bit operations, giving an overall bound of

O(Ln2),O(Ln^2),

apart from initial input reduction.

More generally, if Cmod(n)C_{\mathrm{mod}}(n) is the cost of multiplying and reducing two nn-bit residues, the running time is

O ⁣(L Cmod(n)).O\!\left(L\,C_{\mathrm{mod}}(n)\right).

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 ee is a sequence beginning with 11 and ending with ee, 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

1,2,3,6,12,151,2,3,6,12,15

computes a15a^{15} 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 mm. With a power-of-two radix, this means that mm 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 mm is always valid. Reducing the exponent requires additional conditions.

If the greatest common divisor satisfies gcd⁡(a,m)=1\gcd(a,m)=1, Euler’s theorem gives

aφ(m)≡1(modm),a^{\varphi(m)}\equiv1\pmod m,

where φ(m)\varphi(m) counts the residue classes coprime to mm. Thus, for nonnegative ee,

ae≡a e mod φ(m)(modm).a^e\equiv a^{\,e\bmod\varphi(m)}\pmod m.

For a prime modulus pp with p∤ap\nmid a, Fermat’s little theorem specializes this to

ap−1≡1(modp).a^{p-1}\equiv1\pmod p.

More precisely, the powers of an invertible residue repeat with period equal to its multiplicative order: the smallest positive integer tt such that at≡1(modm)a^t\equiv1\pmod m. This is an instance of the order of an element in group theory.

If aa and mm are not coprime, reduction modulo φ(m)\varphi(m) can fail. For example,

24 mod 8=0,2^4\bmod8=0,

but reducing the exponent modulo φ(8)=4\varphi(8)=4 would incorrectly give

20 mod 8=1.2^0\bmod8=1.

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 m>1m>1 only when the base has a multiplicative inverse. Such an inverse exists exactly when

gcd⁡(a,m)=1.\gcd(a,m)=1.

Writing the inverse as a−1a^{-1}, one defines

a−k mod m=(a−1)k mod ma^{-k}\bmod m=(a^{-1})^k\bmod m

for positive kk.

The inverse can be found using the extended Euclidean algorithm. For example,

3−1≡5(mod7)3^{-1}\equiv5\pmod7

because 3⋅5≡1(mod7)3\cdot5\equiv1\pmod7, so

3−2≡52≡4(mod7).3^{-2}\equiv5^2\equiv4\pmod7.

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 gx mod mg^x\bmod m is efficient, while recovering xx 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 mm, binary powering efficiently computes AeA^e. 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.