Published by Dimitris Kougioumtzis · Updated
Square the base and halve the exponent, multiplying the result for odd exponents.
Consume exponent bits while squaring the base and multiplying only for set bits; reduce residues after each operation.
When to use Modular exponentiation
Efficient modular powers.
Choosing an alternative
Ordinary exponentiation can produce enormous intermediate integers.
Worked example: input and state changes
Example input
7, 13, 17
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ 1, 7, 13 ], "active": [] }Step 2: Square base and halve exponent. State: result, base, exponent.
State at this checkpoint
{ "values": [ 7, 15, 6 ], "active": [ 1, 2 ] }Step 4: Odd exponent: multiply accumulator modulo the modulus.
State at this checkpoint
{ "values": [ 11, 4, 3 ], "active": [ 0 ] }Step 6: Odd exponent: multiply accumulator modulo the modulus.
State at this checkpoint
{ "values": [ 6, 16, 1 ], "active": [ 0 ] }Step 8: Modular result = 6.
State at this checkpoint
{ "values": [ 6, 1, 0 ], "active": [ 0 ] }
Expected final state
Modular result = 6.
Complexity and input bounds
Family: Number theory. Time complexity: O(log exponent).
Space complexity: O(1) iterative state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Three integers: base (0–99), exponent (0–99), modulus (1–99).
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Exponent zero and modulus one require care; the small-number reference is not a cryptographic big-integer implementation.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 | // base and exponent: 0–99; modulus: 1–99. Returns base^exponent modulo modulus. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(base, exponent, modulus) { let result = 1 % modulus; base %= modulus; while (exponent > 0) { if (exponent % 2 == 1) { result = result * base % modulus; } base = base * base % modulus; exponent = Math.floor(exponent / 2); } return result; } |
Source
No original paper has been verified for this entry. This source is a reference text or teaching reference, not an asserted original publication.
- The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition)
Donald E. Knuth (1997). Reference book.