Modular Arithmetic

Modular Inverse by Search

Find an inverse by trying residues. This is toy arithmetic only, not deployable security.

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