The extended Euclidean algorithm computes a polynomial inverse by combining Euclidean division with coefficient updates. For polynomials irrd and b, it maintains t · b = r; when r becomes 1, t is the inverse of b modulo the irreducible polynomial irrd. section 10.2 section 10.8
A polynomial-inversion implementation follows this flow:
- Initialize v = irrd, u = b, coefficient trackers w = 0, y = 0, and normalization data including y₀ = lc(b). section 10.2
- Repeatedly divide v by u to obtain quotient q and remainder r, normalize r, and compute t = ρ(w − qy), where ρ = 1/lc(r). section 10.2
- Shift the coefficient and remainder variables until r = 1; the resulting t satisfies t · b = 1 modulo irrd. section 10.2
Turning inversion into division
To divide polynomials modulo an irreducible polynomial, first compute 1/b with the extended algorithm, then multiply: a/b = a · (1/b). section 10.2 section 10.8
Equation 10.5
\[\begin{gathered} \begin{split} v \longleftarrow irrd\\ u \longleftarrow b\\ r \longleftarrow 0\\ w \longleftarrow 0\\ q \longleftarrow 0\\ t \longleftarrow 0\\ y_0 \longleftarrow lc(b) \end{split}\label{eainv1} \end{gathered}\]Use the initialization equation alongside the loop equation to map each mathematical variable directly to an implementation state. section 10.2
