Polynomial pseudo-division divides A by B without inverting coefficients. If d = lc(B), it computes Q and R such that d^(deg(A)-deg(B)+1)A = BQ + R, with deg(R) < deg(B). Scaling by powers of d keeps the procedure suitable for coefficient domains where inverses are unavailable. section 12.1
The routine supports resultant computation, which determines whether a polynomial is a quadratic residue modulo an irreducible prime polynomial. That test is used when finding square roots and points on elliptic curves over polynomial extension fields. section 12.0 section 12.4
Implement the procedure in three phases:
- Initialize temporary polynomials S and T, copy A into R, zero Q, set e = deg(A) - deg(B) + 1, and store d = lc(B). section 12.2.2
- While deg(R) ≥ deg(B), set S to the leading coefficient of R at degree deg(R) - deg(B), scale Q and R by d, and add S to Q. section 12.2.2
- Shift and scale B by S, subtract it from R, decrement e, and clear S’s temporary coefficient; the loop lowers the remainder degree. section 12.2.2
- After termination, multiply Q and R by d^e when e is positive, then release temporary coefficients and polynomials. section 12.2.2
Operational interpretation
At each iteration, the leading term of R determines how far B is shifted and which coefficient scales it. Scaling the existing Q and R by d preserves the pseudo-division identity without dividing by d; subtracting the shifted product removes the current leading term. section 12.1 section 12.2.2
Figure 12.4 Pseudo-division algorithm
Use the pseudo-division flow diagram to track initialization, repeated quotient and remainder updates, termination, and cleanup. section 12.1
