FoundationSource checked

Modular Exponentiation

Computes large powers modulo an integer without constructing the full power.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Cryptography
Difficulty: Beginner
Family: Modular Arithmetic
Tier: Foundation
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 10
Code example: Ready
Visualization: Ready

Overview

Modular Exponentiation combines exponentiation by squaring with a modulo reduction after each multiplication, keeping intermediate values bounded.

Core Concepts

modulusrepeated squaringbounded intermediatebinary exponent

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(log e)

Average

O(log e * M(k))

Worst

O(log e * M(k))

Space

O(k)

When to Use

Use it when powers are needed under a modulus.
Use it for RSA, Diffie-Hellman, primality tests, and modular arithmetic routines.
Use constant-time implementations when secrets influence the exponent.

When Not to Use

Avoid building the full power before reducing modulo m.
Avoid non-constant-time implementations for secret exponents in cryptographic code.
Avoid it when the modulus is zero or not validated.

What It Does

Computes base^exponent mod modulus
Keeps intermediates bounded with modular reduction

Use Cases

Public-key cryptography
Primality testing
Number-theory algorithms

Inputs

Message, key, modulus, seed, or public parameters
Security parameter or nonce when required

Outputs

Cryptographic value such as signature, random bits, proof, or modular result

Pseudocode

1.Set result to 1 mod modulus.
2.Set base to base mod modulus.
3.While exponent is greater than zero:
4.If exponent is odd, set result to result * base mod modulus.
5.Set base to base * base mod modulus.
6.Divide exponent by 2 using integer division.
7.Return result.

Canonical Example

Input: base = 5, exponent = 13, modulus = 23
Output: 21
Explanation: Repeated squaring computes 5^13 while reducing after each multiplication, yielding 21 modulo 23.

Implementation Notes

Reduce the base modulo m before the loop.
After each multiplication or squaring, reduce modulo m.
Use constant-time library routines for cryptographic secret exponents.

Common Pitfalls

Overflowing intermediate products before reduction.
Forgetting the exponent-zero case.
Leaking exponent bits through branches or timing in cryptographic contexts.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show applying exponentiation by squaring under a modulus on a small fast modular exponentiation example.

Step 1 of 7: Set result to 1 mod modulus.

cryptography-mechanism

Notes

Cryptographic modular exponentiation needs side-channel-resistant implementation, not just the mathematically correct loop.

Sources (2)

What each reference supports for this entry.

Handbook of Applied Cryptography

Book

Cryptographic reference for Modular Exponentiation's number-theoretic primitive, modular arithmetic, primality, or factorization context.

Open source

Modern Computer Arithmetic

Book

Reference for Modular Exponentiation's arithmetic operations, modular arithmetic, multiplication, division, or number-theoretic implementation details.

Open source