Modular Arithmetic

Modular Add and Multiply

Reduce sums and products modulo a small modulus. 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

Reduce sums and products modulo a small modulus.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

m, a, b(7, 5, 4)\begin{array}{c|c}\text{m, a, b}&\text{(7, 5, 4)}\end{array}

Step 2 — Raw sum

Compute the highlighted cryptography value.

a+b9\begin{array}{c|c}\text{a+b}&\hlmath{\text{9}}\end{array}

Step 3 — Sum residue

Compute the highlighted cryptography value.

(a+b) mod m2\begin{array}{c|c}\text{(a+b) mod m}&\hlmath{\text{2}}\end{array}

Step 4 — Raw product

Compute the highlighted cryptography value.

a*b20\begin{array}{c|c}\text{a*b}&\hlmath{\text{20}}\end{array}

Step 5 — Product residue

Compute the highlighted cryptography value.

(a*b) mod m6\begin{array}{c|c}\text{(a*b) mod m}&\hlmath{\text{6}}\end{array}