fq_nmod_mpoly.h

Initialises ctx for polynomials in nvars variables with the ordering ord (ORD_LEX, ORD_DEGLEX or ORD_DEGREVLEX) and coefficients in the field of fqctx. The context makes its own copy of the field, so fqctx may be cleared afterwards.

Initialises ctx with coefficients in \mathbb{F}_{p^{\mathit{deg}}}, defined by the modulus chosen by fq_nmod_ctx_init_ui (a Conway polynomial if the database has one, otherwise an irreducible polynomial of minimal weight); the generator is printed as #.

Initialises ctx with a random number of variables in [0, max_nvars], a random ordering, and a random field of characteristic a prime of at most p_bits bits and degree at most deg_bound. Used for testing.

Return the number of variables and the ordering.

Replaces the field of ctx by \mathbb{F}_{p^{\mathit{deg}}} with the same characteristic, as in fq_nmod_mpoly_ctx_init_deg. Polynomials of the context become invalid. Used by the algorithms that try extension fields of increasing degree.

Frees the memory used by ctx.

Initialise A as the zero polynomial, allocating nothing, space for alloc terms, or space for alloc terms with bits bits per exponent field.

Frees the memory used by A.

Ensure space for length terms, change the allocation to alloc terms (not less than the length), and ensure space with exponent fields of at least (fit_bits, repacking) or exactly (reset_bits, discarding the exponent data) bits bits.

Keeps only the newlen leading terms of A if it is longer.

Repack the exponents of B into A (resp. of A in place) with Abits bits per field; return 0 if some exponent does not fit, setting A to zero.

Return a string representing A (freed by the caller with flint_free), or print it to file or stdout.

Parses str with integers, the variables in x, +, -, *, exact / and ^ followed by an integer exponent. The generator of the field is not available as a symbol unless it is included in x. Returns 0 on success, and -1 (setting A to zero) on failure.

Set A to the variable of index var; return whether A is that variable, or, for var < 0, any variable.

Assignment, swap and equality test.

Return whether A is constant, and set c to the constant A (throwing if it is not constant).

Set A to the constant c, given as an fq_nmod_t, in n_fq format (d words), or as an integer reduced modulo p.

Sets A to the constant \theta, the generator of \mathbb{F}_q over \mathbb{F}_p (as returned by fq_nmod_gen).

Set A to 0 or 1.

Return whether A equals the constant c, zero or one.

Returns a pointer to the coefficient (d words) of A, which must be a nonzero constant.

Set degs to the degrees of A in all variables, and test whether they fit an slong.

The degree of A in the variable of index var.

The total degree of A, and whether it fits an slong.

Sets used[i] to a nonzero value if the variable of index i appears in A, and to zero otherwise.

Get or set the coefficient of the monomial M (throws if M is not a monomial).

Get or set the coefficient of the monomial with exponent vector exp. Setting a coefficient to zero removes the term. Each call costs time linear in the length of A.

Sets C to the coefficient of \prod_i x_{v_i}^{e_i} in A viewed as a polynomial in the distinct variables x_{v_i}, v_i = vars[i], e_i = exps[i], with coefficients in the other variables.

Returns whether A is nonzero with leading coefficient 1.

Test whether A involves only the variable of index var; convert such a polynomial to an fq_nmod_poly (returning 0 if it involves another variable); and set A to the univariate polynomial B in that variable.

Returns 1, -1 or 0 according as A is greater than, less than or equal to B in a total order on polynomials that agrees with the monomial ordering on monomials.

Return whether A is canonical, or throw if it is not.

Return the number of terms, or change it to new_length, deleting terms at the end or appending zero terms.

Get or set the coefficient of the term of index i.

Test whether the exponents of the term of index i fit a ulong or slong, and get its exponent vector or the exponent of one variable; the ulong and slong versions throw if a value does not fit.

Set the exponent vector of the term of index i.

Set M to the term of index i, or to its monomial with coefficient 1.

Append a term with coefficient c and exponent vector exp (pointers to fmpz, an array of fmpz, or ulong) in constant amortised time.

Sort the terms into the order of the context, and combine adjacent equal monomials and remove zero coefficients.

Sets A to B with its terms in reverse order.

Set A to a random polynomial with at most length terms and exponents below exp_bound, below exp_bounds[i] for variable i, or of at most exp_bits bits.

Set A to B + c or B - c.

Set A to B + C or B - C.

Sets A to -B.

Set A to c B.

Sets A to B + e C.

Sets A to B divided by its leading coefficient; throws if B is zero.

Sets A to the derivative of B with respect to the variable of index var.

Sets ev to the value of A at the point vals[0], vals[1], ... (one per variable).

Sets A to B with the variable of index var replaced by val.

Sets A to B evaluated at the univariate polynomials C[i]. Returns 1 for success and 0 if the result would be too large.

Set A to B evaluated at the polynomials C[i] of the context ctxAC, one per variable of ctxB; A must not alias B or any C[i]. Return 1 for success and 0 if the computation would be too large. The main function uses a matrix transformation of the exponents when every C[i] is zero or a monomial with coefficient 1, and otherwise a Horner scheme or a geobucket sum.

Sets A to B with the variable of index i of ctxB replaced by the variable of index c[i] of ctxAC, or by zero if c[i] is negative.

Set A to B C by Johnson's heap algorithm [Joh1974].

Set A to B^k. fq_nmod_mpoly_pow_fmpz throws if k < 0 and returns 0 if k does not fit an slong and B has more than one term; otherwise both return 1.

Sets A to B^k by repeated multiplication.

If B divides A, sets Q to A/B and returns 1; otherwise sets Q to zero and returns 0. Throws FLINT_DIVZERO if B is zero.

Sets Q to A/B, assuming that the division is exact.

Set Q and R to the quotient and remainder of A divided by B, with no term of R divisible by the leading monomial of B.

Divides A by the len polynomials B[i]: A = R + \sum_i Q_i B_i with no term of R divisible by any leading monomial of a B_i.

The heap implementations [MonPea2011] behind the division functions.

If A is a square, set Q to a square root and return 1; otherwise return 0. In characteristic 2 the square root exists exactly when all exponents are even, and it is obtained by halving the exponents and taking the square roots c^{2^{d-1}} of the coefficients.

If Q^2 + AQ = B has a solution, sets Q to one and returns 1; otherwise returns 0. In characteristic 2 the equation is solved term by term (Quadratics).

Sets M to the GCD of the terms of A: zero, or the monomial with coefficient 1 whose exponents are the minima over the terms of A.

Sets g to the GCD of the coefficients of A viewed as a polynomial in the variables vars[i], and returns 1 for success.

Set G to the monic GCD of A and B (zero if both are zero), and fq_nmod_mpoly_gcd_cofactors also \bar{A} = A/G and \bar{B} = B/G. The algorithm is chosen as for nmod_mpoly_gcd; when \mathbb{F}_q is too small, Brown's and Zippel's algorithms continue with images over \mathbb{F}_q[x]/(h) \cong \mathbb{F}_{q^n} for irreducible h in one of the variables.

Set G to the monic GCD by one algorithm: Brown's dense interpolation, Hensel lifting, Zippel's sparse interpolation, or sparse interpolation with two main variables. Return 0 if the algorithm cannot be applied.

As nmod_mpoly_deflation, nmod_mpoly_deflate and nmod_mpoly_inflate: the shifts and strides of the exponents of each variable, and the substitutions e \mapsto (e - \mathit{shift})/\mathit{stride} and e \mapsto \mathit{shift} + \mathit{stride} \cdot e.

Set R to the resultant of A and B, or the discriminant of A, with respect to the variable of index var, by the subresultant algorithm of Ducos [Duc2000]. Return 1 for success.

Memory management, printing and consistency check.

Convert B to a polynomial in the variable of index var, and back.

Access the terms: whether the degree fits an slong, the number of terms, the exponent and the coefficient of the term of index i, and setting the coefficient of x^e.

A GCD up to factors free of the main variable, the resultant and the discriminant with respect to the main variable, by subresultants. Return 1 for success.

Ensure room for length coefficients of d words and exponent vectors of N words in the given arrays, and set the length field.

Returns a pointer to the leading coefficient (d words) of the nonzero A.

Radix sort of the terms left to right - 1 (with d words per coefficient), appending a term with undefined coefficient, and setting a coefficient given an array of fmpz exponents.

Kernels on term arrays: merge-addition, heap multiplication and exact division (returning 0 if not exact), evaluation at a point, and substitution of monomials by a matrix acting on exponent vectors.

Conversions to and from univariate representations with given exponent bits, shifts and strides.

Sets up the generic ring interface R used by the parser and the subresultant code.

Throws if some term of r is divisible by the leading monomial of g.

Step alpha through the elements of \mathbb{F}_q in the lexicographic order of their coordinates: fq_nmod_next returns 0 when it wraps around to zero, fq_nmod_next_not_zero skips zero.

As the nmod_mpoly_geobucket functions: set swaps p into the geobucket, add and sub add or subtract p, empty returns the sum in p.

Initialise the m embeddings of the field of smallctx into the field of bigctx (whose degree must be a multiple of m), and clear one.

Map a polynomial in x over \mathbb{F}_q to its residue in the large field (reduction modulo h), and an element of the large field to its representative of degree less than n in x, for the fq_nmod and n_fq representations.

Map an element of \mathbb{F}_q into the large field.

Start iterating over embeddings: init sets ectx to a context over an extension of degree n \ge 2 (with n m \log_2 p about 20) and returns the first embedding; next returns the next one, moving to the next degree (and changing ectx) after all m embeddings of a degree have been used; clear frees the chooser and ectx.

Operations on fq_nmod_mpolyu_t, as the nmod_mpolyu functions: memory management, access to the coefficient of x^{\mathit{pow}} (inserted if absent), the leading coefficient of the leading coefficient, shifts of the main exponent, scaling, the GCD of the coefficients, multiplication and exact division by a polynomial in the other variables, exact division with nmainvars main variables, and copying the monomial structure.

Conversions between the representations, with a permutation perm of the variables, deflation by shift and stride, and the inverse operations with Abits-bit exponents.

For A viewed as a polynomial in its first num_vars variables: the leading coefficient, and the GCD of the coefficients (returning 1 for success).

Operations on fq_nmod_mpolyn_t: memory management, the leading coefficient (an element, or the univariate polynomial), the degree in the last variable, the test for a nonzero constant, scaling, multiplication and exact division by a univariate polynomial in the last variable, and the GCD g of the univariate coefficients.

The same operations for fq_nmod_mpolyun_t.

Computes the GCD G and, if Abar and Bbar are not NULL, the cofactors of the nonzero A and B with the algorithms in the bit mask algo (the MPOLY_GCD_USE_ constants). Returns 1 for success.

Brown's algorithm with evaluation points in \mathbb{F}_q, or with reduction of the variable var modulo irreducible polynomials of increasing degree over \mathbb{F}_q (images over \mathbb{F}_{q^n}). Return 1 for success, also setting the cofactors.

Zippel's sparse interpolation on fq_nmod_mpolyu_t: gcdp with points in \mathbb{F}_q (the univar versions for the base case of one main variable, with or without cofactors), gcds solving for the coefficients of the assumed form f, and gcdm trying gcdp first and then images over extensions \mathbb{F}_{q^n} chosen by an embedding chooser.

Sparse interpolation with two main variables given degree bounds and the leading coefficient of the GCD, over \mathbb{F}_q or over extensions; and the GCD by Hensel lifting over \mathbb{F}_q.

Sparse interpolation helpers, as for nmod_mpoly: monomial evaluations at powers of the evaluation points, the next bivariate image from the current and incremental monomial values, and collection and solution of the Vandermonde systems.

Interpolation steps of Brown's and Zippel's algorithms with points \alpha \in \mathbb{F}_q: evaluation of the last variable (reduce), first image (lift) and Chinese remaindering with a new image (crt, returning whether the interpolant changed and updating lastdeg).

The same steps for images over an extension \mathbb{F}_{q^n} (context ectx) obtained with the embedding emb: reduction modulo the irreducible polynomial h in the last variable, lifting of an image, and Chinese remaindering in \mathbb{F}_q[x] with the product modulus of the polynomials used so far.

The lgprime interpolation steps of the nmod_mpoly GCD algorithms (declared here because they use fq_nmod_mpoly): a polynomial over \mathbb{F}_p is reduced modulo an irreducible polynomial m in its last variable, giving a polynomial over \mathbb{F}_p[x]/(m) \cong \mathbb{F}_{p^{\deg m}} in the context ectx (or ffctx), and images are combined by Chinese remaindering in \mathbb{F}_p[x].