Fast Exponentiation

Square and Multiply

Evaluate a modular power with an ordered bit table. This is toy arithmetic only, not deployable security.

cryptography The values in this lesson are deliberately tiny so every modular arithmetic step can be checked exactly.

Example

Evaluate a modular power with an ordered bit table.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

base, exponent, modulus(7, 13, 55)\begin{array}{c|c}\text{base, exponent, modulus}&\text{(7, 13, 55)}\end{array}

Step 2 — Bit 1

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(1, 1, 1, 7, 7, 7)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(1, 1, 1, 7, 7, 7)}}\end{array}

Step 3 — Bit 2

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(1, 49, 49, 343, 13, 13)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(1, 49, 49, 343, 13, 13)}}\end{array}

Step 4 — Bit 3

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(0, 169, 4, -, -, 4)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(0, 169, 4, -, -, 4)}}\end{array}

Step 5 — Bit 4

Compute the highlighted cryptography value.

bit, raw square, square mod m, raw multiply, multiply mod m, residue(1, 16, 16, 112, 2, 2)\begin{array}{c|c}\text{bit, raw square, square mod m, raw multiply, multiply mod m, residue}&\hlmath{\text{(1, 16, 16, 112, 2, 2)}}\end{array}

Final Step — Result

Compute the highlighted cryptography value.

result2\begin{array}{c|c}\text{result}&\hlmath{\text{2}}\end{array}