Univariate polynomials

OverviewPolynomial arithmetic over generic rings and its specialisationsHow the generic polynomial module gr_poly organises multiplication, division, Newton iteration, GCDs, evaluation, composition, power series and factorisation over any ring through overridable ring methods, and how nmod_poly, fmpz_poly, fmpz_mod_poly, fq_poly and arb_poly specialise or reuse these algorithms.

OverviewMultiplying polynomials over Z/nZHow nmod_poly multiplies: classical products built on modular dot products, Kronecker substitution (KS, KS2, KS4), and the small-prime FFT of fft_small, with the length and modulus-size cutoffs that choose between them for full, low, middle and high products.

OverviewMultiplying polynomials over ZHow fmpz_poly multiplies, depending on the length and the coefficient size - word-size accumulation, classical and packed-limb products, Karatsuba with Toom-Cook interpolation in the polynomial variable, Kronecker substitution, the multimodular small-prime FFT, Schönhage-Strassen convolutions and classical multiplication in transform space - with the exactness lemmas and the dispatcher that chooses among them.

AlgorithmKronecker substitutionMultiplies polynomials over \mathbb{Z}/n\mathbb{Z} by packing their coefficients into large integers, multiplying the integers and unpacking; Harvey's KS2 and KS4 variants evaluate at ±2^b and ±2^(-b) to split the integer product into two or four smaller ones.

AlgorithmNewton iteration for power series and divisionInverse, quotient, square root, reciprocal square root, exponential and logarithm of power series by Newton iteration with middle products and the Karp–Markstein trick, and polynomial division with remainder via reversed polynomials, as implemented for nmod_poly.

AlgorithmMiddle products and the transposition principleThe middle product, a window of coefficients of a product, is the transpose of polynomial multiplication and costs no more than an ordinary product of the corresponding size; FLINT computes it with dot products, a cyclic convolution whose wrap-around misses the window, or transposed FFTs, and uses it in Newton iteration and geometric evaluation.

OverviewPolynomial GCDs and resultantsThe Euclidean algorithm, the half-gcd algorithm and the subresultant pseudo-remainder sequence as implemented generically in gr_poly, how the generic code chooses between them from the properties of the coefficient ring, how resultants are derived from the same sequences, and the specialised algorithms of nmod_poly, fmpz_mod_poly, fq_poly and fmpz_poly.

AlgorithmGCDs of polynomials over ZThe three GCD algorithms of fmpz_poly - the subresultant pseudo-remainder sequence, the heuristic GCD through one integer GCD, and the multimodular algorithm with adaptive termination and certification by multimodular division - with the proofs that make their results correct, and the multimodular extended GCD.

AlgorithmResultants and discriminants over ZResultants of integer polynomials by the subresultant pseudo-remainder sequence and by the multimodular algorithm with Hadamard's bound, discriminants as resultants with the derivative, and resultants with a known divisor, as implemented in fmpz_poly.

AlgorithmHalf-GCDThe half-gcd algorithm computes the quotients of the first half of the Euclidean remainder sequence from the top halves of the inputs, recursively, giving GCDs, extended GCDs and resultants in O(M(n) \log n) operations; with a correctness proof and FLINT's cutoffs for nmod_poly.

AlgorithmMultipoint evaluation and interpolationEvaluation of a polynomial at many points and interpolation through many points in O(M(n) \log n) operations with the subproduct tree and the remainder tree, and in O(M(n)) for points in geometric progression with Bluestein's chirp transform and the method of Bostan and Schost.

AlgorithmComposition and modular compositionComputing f(g), f(g) \bmod x^n and f(g) \bmod h by Horner's rule, divide and conquer, Taylor shifts, the baby-step giant-step method of Brent and Kung, and the algorithm of Kinoshita and Li, with the choices made by nmod_poly.

AlgorithmHensel liftingLifting a factorisation modulo a prime p into coprime monic factors to a factorisation modulo p^N, for two factors with the Bézout cofactors and for many factors along a factor tree, with quadratic convergence; the correctness proof and the fused tree nodes used by fmpz_poly.

AlgorithmFactoring polynomials over the integersThe Zassenhaus algorithm (factor modulo a prime, Hensel lift, recombine subsets of the modular factors) and van Hoeij's knapsack method with CLD data and gradual feeding to LLL, as implemented in fmpz_poly_factor, with the reductions that come first (content, powers of x, deflation with Capelli certificates, squarefree factorisation), the choice of the prime and the bounds that make the result provable.

AlgorithmSquarefree factorisationYun's algorithm in characteristic zero and the gcd iteration with p-th roots over finite fields, which split a polynomial into squarefree, pairwise coprime factors with distinct multiplicities using only gcds and exact divisions.

AlgorithmFactoring polynomials over finite fieldsSquarefree, distinct-degree and equal-degree factorisation over \mathbb{F}_q; the Cantor–Zassenhaus, Berlekamp and Kaltofen–Shoup algorithms, the baby-step giant-step distinct-degree factorisation with modular composition, the trace and minimal-polynomial splittings, and how the generic implementation in gr_poly chooses between them.

AlgorithmIrreducibility testing over finite fieldsRabin's test, Ben-Or's test and the distinct-degree test for irreducibility over \mathbb{F}_q, their costs on irreducible and on random inputs, how FLINT combines them, and the construction of irreducible polynomials.

AlgorithmRoots of polynomials over finite fieldsRoots in \mathbb{F}_q by squarefree factorisation, the split \gcd(f, x^{(q-1)/2} \pm 1) and random shifts, with powers of x + c computed through Taylor shifts; roots modulo prime powers by Hensel lifting of all roots, and modulo composite n by the Chinese remainder theorem.

AlgorithmCounting and isolating real roots over ZRoot bounds, Descartes' rule of signs and the Vincent-Collins-Akritas bisection algorithm, Sturm sequences computed as subresultant or primitive remainder sequences, and sign-change isolation for real-rooted polynomials, as used by fmpz_poly to count and isolate the real roots of squarefree integer polynomials exactly.

In this section#