Euclid

Extended Euclid Table

Track Bezout coefficients while Euclid runs. This is toy arithmetic only, not deployable security.

Example

Track Bezout coefficients while Euclid runs.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

a, b(40, 3)\begin{array}{c|c}\text{a, b}&\text{(40, 3)}\end{array}

Step 2 — Table row

Compute the highlighted cryptography value.

r, s, t(40, 1, 0)\begin{array}{c|c}\text{r, s, t}&\hlmath{\text{(40, 1, 0)}}\end{array}

Step 3 — Table row

Compute the highlighted cryptography value.

r, s, t(3, 0, 1)\begin{array}{c|c}\text{r, s, t}&\hlmath{\text{(3, 0, 1)}}\end{array}

Step 4 — Table row

Compute the highlighted cryptography value.

r, s, t(1, 1, -13)\begin{array}{c|c}\text{r, s, t}&\hlmath{\text{(1, 1, -13)}}\end{array}

Step 5 — Table row

Compute the highlighted cryptography value.

r, s, t(0, -3, 40)\begin{array}{c|c}\text{r, s, t}&\hlmath{\text{(0, -3, 40)}}\end{array}

Final Step — Bezout row

Compute the highlighted cryptography value.

gcd, s, t(1, 1, -13)\begin{array}{c|c}\text{gcd, s, t}&\hlmath{\text{(1, 1, -13)}}\end{array}
cryptography The values in this lesson are deliberately tiny so every modular arithmetic step can be checked exactly.