Module poly 

Exact univariate polynomials over ℚ — the algebra under the real algebraic numbers.

A Poly is a little-endian vector of exact Rational coefficients with no trailing zeros (the zero polynomial is empty), so equal polynomials are structurally equal and Eq/Hash are derived. Beside the ring operations it carries what exact real-root arithmetic needs:

• Sturm chains on the squarefree part count the distinct real roots in any half-open interval (lo, hi], and bisection on those counts isolates every real root in a RootInterval holding exactly one;
• resultants by the Euclidean identity res(f, g) = (−1)^{mn}·lc(g)^{m − deg r}·res(g, r), r = f mod g, which is how the polynomial of a sum or product of two roots is built;
• factorization over ℤ (Zassenhaus): Yun’s squarefree decomposition, Berlekamp’s algorithm modulo a small prime, linear Hensel lifting past the Mignotte bound 2·|lc|·2ⁿ·‖f‖₁, and recombination of lifted factors by trial division — so a root’s defining polynomial can always be cut down to its minimal polynomial.

Everything is exact and deterministic: no floating point, and the prime and every split are chosen by a fixed order, so every run (and every tier mirroring this file) factors identically.

Structs

Poly

A polynomial over ℚ: c[i] is the coefficient of xⁱ. INVARIANT: no trailing zero.

RootInterval

One isolated real root. lo == hi is the root itself (a rational root the bisection landed on); otherwise the root is the only root in the open interval (lo, hi) and neither end is a root, so the squarefree part changes sign across it.