An inverse is a polynomial that multiplies with another polynomial to produce 1 modulo a specified irreducible polynomial. This operation supports division and elliptic-curve calculations over extension fields. section 10.2 section 2.1
The extended Euclidean algorithm supplies the inverse. It maintains t · b = r while repeatedly replacing the current polynomials with Euclidean quotients and remainders. When r becomes 1, t · b = 1 modulo irrd, so t is the inverse of b. section 10.2
Equation 10.6
\[\begin{gathered} \begin{split} (q, r) = v/u\\ \rho = 1/lc(r)\\ r \longleftarrow \text{normal}(r)\\ t \longleftarrow \rho(w - q y)\\ w \longleftarrow y\\ y \longleftarrow t\\ v \longleftarrow u\\ u \longleftarrow r\\ \text{until }r = 1 \end{split}\label{eainv2} \end{gathered}\]The loop normalizes each remainder, updates the coefficient tracking the inverse, copies the new Euclidean state, and stops when the remainder equals one. section 10.2 section 10.5
A practical inversion routine follows this execution flow:
- Initialize the irreducible polynomial as v, the input polynomial as u, zero-valued tracking polynomials, and the constant polynomial one. section 10.2 section 10.5
- Compute the Euclidean quotient and remainder, invert the remainder’s leading coefficient, and normalize the remainder. section 10.2 section 10.5
- Update the inverse coefficient with w − q·y, scale it by rho, copy the new state, and test whether r equals one. section 10.5
- Save the final coefficient as the output and clear temporary variables to prevent memory leaks. section 10.5
Listing 10.5 Inversion main loop
poly_init(&tmp);
done = 0; #1
while(!done) #1
{
poly_euclid(&q, &r, v, u); #2
minv(rho, r.coef[r.deg]); #3
poly_normal(&r); #4
poly_mul(&tmp, q, y); #5
poly_sub(&t, w, tmp); #5
for(i=0; i<=t.deg; i++) #6
mmul(t.coef[i], t.coef[i], rho); #6
poly_copy(&w, y); #7
poly_copy(&y, t); #7
poly_copy(&v, u); #7
poly_copy(&u, r); #7
done = poly_cmp(r, one); #8
}
poly_copy(a, t); #9
mpz_clear(rho); #10
poly_clear(&r); #10
poly_clear(&u); #10
poly_clear(&q); #10
poly_clear(&one); #10
poly_clear(&t); #10
poly_clear(&w); #10
poly_clear(&tmp);
poly_clear(&y);
poly_clear(&v);
}
The implementation separates initialization, the Euclidean main loop, termination detection, output copying, and resource cleanup. section 10.5
