Fast Exponentiation

Square and Multiply

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

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}
cryptography The values in this lesson are deliberately tiny so every modular arithmetic step can be checked exactly.