Euclid’s algorithm repeatedly divides polynomials, retaining each remainder until the remainder degree is smaller than the divisor. It supplies quotient and remainder routines for polynomial arithmetic over finite fields, including elliptic-curve extension fields. section 10.0 section 10.1
A polynomial division pass follows this execution flow:
- Initialize the remainder r to a and the quotient q to zero. section 10.1
- While deg(r) ≥ deg(b), divide the leading coefficients, place the result at degree deg(r) − deg(b), and subtract the shifted multiple of b. section 10.1
- Stop when the remainder degree is lower than the divisor; the remaining r is the division remainder. section 10.1 section 10.3
- For the polynomial gcd, repeatedly replace the higher-degree argument with the lower-degree argument and the remainder, handling zero inputs first. section 10.1
Figure 10.1 Polynomial Euclid’s algorithm, which is the guts of inversion in elliptic curve pairing algorithms.
Use the flow diagram to connect degree comparisons, leading-coefficient division, shifted subtraction, and termination. section 10.1
The low-level C routine separates initialization, the degree-checked main loop, temporary-polynomial subtraction, and cleanup. An extra r-degree check handles division by a degree-zero polynomial. section 10.3
The extended form feeds quotient and remainder data into polynomial inversion. It tracks prior values, normalizes remainders, and stops when the remainder becomes one; division modulo an irreducible polynomial then becomes inversion followed by multiplication. section 10.5 section 10.8
