Polynomial division finds a quotient q and remainder r for polynomials a and b, reducing r until its degree is lower than deg(b). Over a finite field, each leading-coefficient division is performed modulo the field characteristic. This supplies the low-level arithmetic needed for slopes and point addition in extension-field elliptic-curve computations. section 10.0 section 10.1
Figure 10.1 Polynomial Euclid’s algorithm, which is the guts of inversion in elliptic curve pairing algorithms.
The flow is repeated leading-term cancellation: initialize r to a and q to zero, then stop once r has lower degree than b. section 10.1
For a nonzero divisor b, perform Euclidean division as a degree-reduction loop:
- Set r ← a and q ← 0. If deg(a) < deg(b), return q = 0 and r = a. section 10.1 section 10.3
- Compute s = lc(r)/lc(b), the quotient coefficient that cancels r’s leading term. section 10.1
- Store s at q[deg(r) − deg(b)], aligning the quotient term with the difference in degrees. section 10.1
- Replace r with r − s·b·x^(deg(r) − deg(b)); repeat until r has sufficiently low degree. section 10.1 section 10.3
Leading-term cancellation modulo 7
For a = x³ + 2x² + 3x + 1 and b = 5x³ + x + 6, begin with r = a and q = 0. Because 1/5 mod 7 = 3 and the degrees match, set q = 3, then subtract 3b from r to remove its x³ term. Subsequent iterations apply the same alignment and subtraction. section 10.1
The remainder also drives polynomial gcd: repeatedly divide the larger working polynomial by the smaller and replace the pair with divisor and remainder. A gcd of 1 indicates no nonconstant common factor, supporting irreducible-polynomial searches. section 10.4 section 10.8
Modulo an irreducible polynomial, division is implemented as inversion followed by multiplication: a/b = a·(1/b). Extended Euclid maintains a coefficient t until t·b = 1 modulo the irreducible polynomial; t is then the inverse. The division wrapper computes that inverse and multiplies it by the numerator. section 10.2 section 10.6
