Modular Arithmetic

Modular Inverse by Search

Find an inverse by trying residues. 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

Find an inverse by trying residues.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

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

Step 2 — Trial 1

Compute the highlighted cryptography value.

x, ax, ax mod m(1, 3, 3)\begin{array}{c|c}\text{x, ax, ax mod m}&\hlmath{\text{(1, 3, 3)}}\end{array}

Step 3 — Trial 2

Compute the highlighted cryptography value.

x, ax, ax mod m(2, 6, 6)\begin{array}{c|c}\text{x, ax, ax mod m}&\hlmath{\text{(2, 6, 6)}}\end{array}

Step 4 — Trial 3

Compute the highlighted cryptography value.

x, ax, ax mod m(3, 9, 2)\begin{array}{c|c}\text{x, ax, ax mod m}&\hlmath{\text{(3, 9, 2)}}\end{array}

Step 5 — Trial 4

Compute the highlighted cryptography value.

x, ax, ax mod m(4, 12, 5)\begin{array}{c|c}\text{x, ax, ax mod m}&\hlmath{\text{(4, 12, 5)}}\end{array}

Step 6 — Trial 5

Compute the highlighted cryptography value.

x, ax, ax mod m(5, 15, 1)\begin{array}{c|c}\text{x, ax, ax mod m}&\hlmath{\text{(5, 15, 1)}}\end{array}

Final Step — Inverse

Compute the highlighted cryptography value.

inverse5\begin{array}{c|c}\text{inverse}&\hlmath{\text{5}}\end{array}