Fast Exponentiation

Modexp RSA Encrypt

Use square-and-multiply for RSA encryption. 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

Use square-and-multiply for RSA encryption.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

base, exponent, modulus(7, 3, 55)\begin{array}{c|c}\text{base, exponent, modulus}&\text{(7, 3, 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}

Final Step — Result

Compute the highlighted cryptography value.

result13\begin{array}{c|c}\text{result}&\hlmath{\text{13}}\end{array}