n_poly.h

Initialise A as the zero polynomial (with space for alloc coefficients for n_poly_init2), respectively free it.

Ensure that A has space for at least len coefficients. The allocation grows to \max(\mathit{len}, \tfrac32 \mathit{alloc} + 1) and never shrinks.

Swaps A and B efficiently.

Returns whether A is normalised (its length is nonnegative and its leading coefficient nonzero). It does not check that the coefficients are reduced; see n_poly_mod_is_canonical.

Normalise A by decreasing the length past zero leading coefficients, respectively truncate poly to length len and normalise.

Return the degree (-1 for zero) and the leading coefficient (the polynomial must be nonzero).

Set the polynomial to 0, 1, the constant c (which must be reduced), or a copy of B.

Return whether the polynomial is 0, 1, or equal to the other one.

Get or set the coefficient of x^j (or x^e). n_poly_set_coeff normalises the result; n_poly_set_coeff_nonzero requires c \ne 0. The value is not reduced.

Multiply by x^k, respectively divide by x^k discarding the low coefficients.

Sets output to the reversal of input viewed as a polynomial of length m, normalised.

Prints A to standard output with variable name x.

Copy the coefficients between an n_poly_t and an nmod_poly_t (whose modulus is left unchanged).

Make a a shallow view of b, sharing its coefficient array, so that functions of the other type can read it without copying (nmod_poly_mock also sets the modulus of the view). The view must not be cleared or used to modify the length or allocation.

Returns whether A is normalised with all coefficients reduced modulo mod.

Sets the coefficient of x^j to c reduced modulo mod.

Sets A to B divided by its leading coefficient; B must be nonzero with invertible leading coefficient.

Replaces g(x) by g(x + c), in place.

Negation, addition and subtraction, and addition of the constant c (reduced first).

Multiplication by a scalar c, which must be reduced for the underscore versions; these do not normalise (so c should be nonzero). n_poly_mod_scalar_mul_ui reduces c and normalises.

Sets A = B + d_0 C.

Sets A = B + C \cdot (d_1 x + d_0). A must be distinct from B and C.

Multiplies A by x^k + c, in place. Used to build products of linear factors.

Sets A to \prod_{i<n} (x - r_i).

Returns the value of A at c.

Return the value of P at \alpha, where alphapow holds the powers 1, \alpha, \alpha^2, \ldots (at least two of them); missing powers are appended to alphapow, so that one table serves many evaluations at the same point. _n_poly_eval_pow takes the dot product parameters for the length of P.

Sets *vp and *vm to the values of P at \alpha and -\alpha, using and extending the table alphapow as above. This is the evaluation step of the symmetric two-point interpolation (2sm) used by Brown's GCD algorithm.

One step of the evaluation of a sparse polynomial at consecutive powers of a point: with c_i = Acur[i] and Ainc holding the pairs (a_i, m_i), returns \sum_i c_i a_i and replaces each c_i by c_i m_i. Ainc must have twice the length of Acur.

Sets Q to the quotient of A by x - c and returns the remainder A(c).

Multiplication (_nmod_poly_mul), and multiplication truncated to length n.

Euclidean division by a nonzero B with invertible leading coefficient: quotient, remainder, both, or the quotient of an exact division.

Sets res to \mathit{poly}^e.

Divides f by the highest power of p that divides it and returns the exponent. p must be nonconstant.

Set the output to B C \bmod M. The _preinv version takes Minv, the inverse of the reversal of M (see nmod_poly_mulmod_preinv), requires B, C reduced modulo M, and raises an exception otherwise.

Set G to the monic greatest common divisor of A and B, and for n_poly_mod_xgcd the cofactors with SA + TB = G (see nmod_poly_xgcd). The modulus must be prime.

If B is invertible modulo P, sets A to the inverse and returns 1; otherwise returns 0.

Power series inverse of Q modulo x^n, and quotient A/B modulo x^{\mathit{order}}; the constant term of the divisor must be invertible.

Returns the nmod_t of the prime field of ctx.

Return whether the element is 0, 1, or in the prime field (all coefficients except the constant one zero).

Set the element to 0, 1, the prime field element b, the generator t of the field, or a copy of b; or swap two elements.

Return whether two elements are equal (the second compares with an fq_nmod_t).

Returns whether all d words are reduced modulo p.

Sets a to a random nonzero element.

Convert the element to a string (to be freed with flint_free), or print it, as a polynomial in the generator.

Convert between an element and an n_poly_t (the polynomial of degree less than d; _n_fq_set_n_poly reduces a polynomial of any length modulo the defining polynomial) or an fq_nmod_t.

Negation, addition and subtraction, including with a signed integer or an fq_nmod_t.

Multiplies an element by the prime field element c (which need not be reduced).

Unreduced multiplication: _n_fq_mul2 sets the 2d - 1 coefficients of the product of two elements as polynomials in t, _n_fq_madd2 adds it to a; _n_fq_reduce reduces a polynomial of length blen modulo the defining polynomial to an element, and _n_fq_reduce2 does so for length 2d - 1. Delaying the reduction makes sums of products cheaper.

Multiplication a = bc and multiply-add a = b + c e (n_fq_addmul: a = b + c d). The underscore versions need scratch space of N_FQ_MUL_ITCH times d words.

Returns the number of words (1, 2 or 3) needed to accumulate a sum of len products of elements without reduction, or 0 if 3 words do not suffice or d > 30.

Lazy dot products with 1, 2 or 3 words per coefficient, as chosen by _n_fq_dot_lazy_size: mul2 sets and madd2 adds the unreduced product of two elements in a (6d words), and reduce2 reduces the accumulated coefficients modulo p, leaving 2d - 1 coefficients to be reduced with _n_fq_reduce2.

Inversion of a nonzero element.

Powering by binary exponentiation.

Initialises A with space for alloc coefficients in \mathbb{F}_q.

Returns whether A is normalised with canonical coefficients.

Normalises A, whose coefficients have d words.

Set the polynomial to 1, a copy of B, or the constant c.

Return whether the polynomial is 1, or equal to the other one.

Get or set the coefficient of x^e (respectively x^j), as an n_fq element or an fq_nmod_t.

Convert to and from an fq_nmod_poly_t.

Sets A to a random polynomial of length at most len.

Prints A with variable name x.

Multiply by x^n, divide by x^n discarding low terms, or truncate to length len.

Negation, addition, subtraction, and addition of an integer constant.

Multiplication by a scalar (a prime field element c or an n_fq element), and A = B + C d.

Multiplies A by x^k - c, in place.

Sets A to the nonzero B divided by its leading coefficient.

Set e to the value of A at c.

Sets ev to the value of A at \alpha, given the table alphapow of powers 1, \alpha, \ldots (as an n_fq_poly), which is extended as needed.

Multiplication (truncated to length order for n_fq_poly_mullow). If one factor has fewer than 4 terms the product is computed classically with delayed reduction; otherwise by Kronecker substitution: each coefficient is placed in a slot of 2d - 1 words, the packed polynomials are multiplied with _nmod_poly_mul, and the slots are reduced modulo the defining polynomial. The trailing-underscore versions take a stack of temporaries; _n_fq_poly_mul_ works on arrays of Blen and Clen coefficients and writes \mathit{Blen} + \mathit{Clen} - 1.

Sets A to B^e.

Divides f by the highest power of g that divides it and returns the exponent.

Euclidean division by a nonzero B: quotient and remainder, or the remainder only. The basecase functions work on arrays, with invB the inverse of the leading coefficient of B, AA the dividend and A receiving the remainder; n_fq_poly_divrem_ uses the classical algorithm for divisors of length below N_FQ_POLY_DIVREM_DIVCONQUER_CUTOFF (20) and divide and conquer otherwise.

Monic greatest common divisor by the Euclidean algorithm, and for n_fq_poly_xgcd cofactors S, T with SB + TC = G.

Sets A = BC \bmod M.

Sets A to the inverse of the power series B modulo x^{\mathit{order}}; the constant term must be nonzero.

Sets M to \prod_i (x - H_i) for the length elements of H.

Memory management: initialise as zero, free, ensure space for len coefficients A_i (all initialised), and swap.

Removes zero leading coefficients A_i.

Set to 0, 1 or a copy of B (_n_bpoly_set requires A and B to be distinct).

Return whether the polynomial is zero, or equal to the other one.

Get or set the coefficient of x^{e_0} y^{e_1}; the _nonzero version requires c \ne 0.

Return the degree in x, the degree in y (the maximum over the A_i), and the pair (degree in x, degree in y of the leading coefficient A_{\mathrm{lead}}) packed into a word with x in the upper half.

Set A to the univariate polynomial B in x, respectively in y.

Prints A with the variable names xvar and yvar.

Returns whether A is normalised with every A_i canonical modulo mod.

Multiplies A by the nonzero scalar c.

Sets A to \partial B/\partial x; A and B must be distinct.

Treat A as a polynomial in x over \mathbb{F}_p[y]: set g to the content \gcd_i A_i, or divide each A_i exactly by, or multiply it by, the polynomial b(y).

Sets g to the content of A in \mathbb{F}_p[y] and divides it out, then scales so that the leading coefficient of A (in x, then y) is 1, multiplying g by the old leading coefficient.

Replace x by x + c in A (in place), respectively set A to B with y replaced by y + c.

Addition, subtraction and multiplication.

If B divides A, sets Q = A/B and returns 1, otherwise returns 0.

Multiplication, and division with remainder in x, with all coefficients A_i(y) truncated modulo y^{\mathit{order}} (arithmetic in (\mathbb{F}_p[y]/(y^{\mathit{order}}))[x], used in Hensel lifting). The leading coefficient of B must be invertible.

Helpers for interpolation in y at pairs of points \pm\alpha: reduce evaluates A at y = \alpha and y = -\alpha (giving Ap, Am); lift sets T to the bivariate polynomial of degree at most 1 in y with these images; crt updates the interpolant F modulo modulus with new images (using T as scratch), returns whether F changed and sets *deg1 to its degree in y.

Brown's dense modular GCD algorithm [Bro1971] for bivariate polynomials over a word-size prime field: evaluates y at pairs of points \pm \alpha, computes univariate GCDs and interpolates. Sets G = \gcd(A, B), \bar A = A/G, \bar B = B/G and returns 1, or returns 0 if it ran out of evaluation points (the prime is too small). A and B are clobbered. Sp provides the temporaries. See Multivariate polynomials: representations and algorithms.

Returns whether A is normalised with canonical coefficients.

Set to 1, copy, or compare.

Get or set the coefficient of x^{e_0} y^{e_1}.

Set A to a univariate polynomial in x (gen0) or in y (gen1).

Sets A to \partial B/\partial x.

Multiplies A by the scalar c.

Replace x by x + \alpha in A (in place), or set A to B with y replaced by y + c.

Brown's GCD algorithm over \mathbb{F}_q, with the same conventions as n_bpoly_mod_gcd_brown_smprime.

Prints A with the given variable names.

Memory management for n_tpoly_t.

Memory management for n_polyu_t.

Sets the three degrees of the nonzero terms of A, whose exponents pack three variables; -1 each for the zero polynomial.

Prints A with the three variable names.

Memory management for n_polyun_t; all alloc coefficient polynomials are initialised.

Returns whether the terms are in strictly decreasing order of exponents with nonzero normalised coefficients reduced modulo n.

Copy, set to 1, or compare.

Returns the exponent of the leading term and the degree of its coefficient, packed into a word as for n_bpoly_bidegree.

Print A, whose exponents pack 1, 2 or 3 variables, with the given variable names.

Brown's GCD algorithm for polynomials stored as n_polyun with one packed variable, with the same conventions as n_bpoly_mod_gcd_brown_smprime.

For each term of H, set the corresponding term of M (with the same exponent) to the product \prod_j (x - h_j) over the coefficients h_j of that term's coefficient polynomial, and return the largest length of these products. Used to build the master polynomials of Zippel's interpolation.

Initialise the cache tables for the base b.

Return (or set r to) a b^e, respectively a b^{-e}, using and extending the cache.

Initialise and free E.

Prepares E for polynomials of degree at most deg modulo the odd prime p of ctx. Returns 0 if this is not possible (p is 2 or not larger than deg, or not enough points exist), 1 otherwise.

Returns the number of evaluation points (4d + 1 or 2d + 1).

Convert from coefficients a to values v, and back. The n_fq_poly versions transform polynomials over \mathbb{F}_q coefficientwise.

Pointwise arithmetic on vectors of len values, where a zero vector may be stored with length 0: a = 0, a \mathrel{+}= b, a = bc, a \mathrel{+}= bc, and a = bc + de (fmma).

One evaluation step: return (or set res to) \sum_i c_i \mathit{cur}_i and multiply each cur[i] by inc[i]. The fq version works with \mathbb{F}_q elements throughout, the fqp version with cur and inc in the prime field and coeffs in \mathbb{F}_q.

Solve for the mlength coefficients given the monomial values, the elength \ge mlength evaluations and the master polynomial, and check the extra evaluations. Return 1 on success, 0 if the extra evaluations are inconsistent, and -1 if the monomial values are not distinct.

The stack of n_poly_struct.

Take an n_poly from the stack and return its coefficient array with space for len words, respectively give it back.

The stack of n_bpoly_struct.

The stack of n_polyun_struct.