Extended Euclid Table - Cryptography Step by Step

Track Bezout coefficients while Euclid runs. 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

Track Bezout coefficients while Euclid runs.

highlighted = computed this step

Step 1 — Set up

Set up the exact toy cryptography values.

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

Step 2 — Table row

Compute the highlighted cryptography value.

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

Step 3 — Table row

Compute the highlighted cryptography value.

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

Step 4 — Table row

Compute the highlighted cryptography value.

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

Step 5 — Table row

Compute the highlighted cryptography value.

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

Final Step — Bezout row

Compute the highlighted cryptography value.

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