fq_nmod_poly.h

Initialise poly as the zero polynomial. fq_nmod_poly_init2 allocates space for alloc coefficients.

Changes the allocation of poly to alloc coefficients, truncating and normalising the polynomial if it is longer. For alloc = 0 the coefficients are freed.

Ensures that poly has space for at least len coefficients, growing the allocation to at least twice its old size if it must grow. The polynomial is not changed.

Frees the memory used by poly.

Sets the length of poly to len, setting the coefficients from index len up to the old length to zero. Does not normalise. poly must have space for len coefficients.

Decrease the length of poly, respectively the variable *length of the array (poly, *length), until the leading coefficient is nonzero or the length is zero.

Truncates poly to length at most len (that is, reduces it modulo x^{\mathit{len}}) and normalises it.

Sets poly1 to poly2 truncated to length len. poly2 is not modified unless it is the same object as poly1.

Return the length, respectively the degree, of poly; the zero polynomial has length 0 and degree -1.

Returns a pointer to the leading coefficient of poly, or NULL for the zero polynomial.

Return the number of nonzero coefficients.

Returns whether the two polynomials are equal.

Returns whether the two polynomials are equal modulo x^n.

Returns whether poly is the constant polynomial c.

Return whether the polynomial is 0, 1, respectively x.

Returns whether op is a unit of \mathbb{F}_q[x], that is, a nonzero constant.

Copy op into rop.

Sets poly to the constant polynomial c.

Set rop to the polynomial op over \mathbb{F}_p, with coefficients mapped to \mathbb{F}_p \subseteq \mathbb{F}_q. The modulus of op must be p; it is not checked.

Swaps op1 and op2 efficiently.

Set the len coefficients of rop, respectively the polynomial poly, to zero.

Set the polynomial to 1, respectively to x.

Set rop to op divided by its leading coefficient. The zero polynomial is mapped to zero; the underscore version requires a nonzero leading coefficient op[length - 1] and allows aliasing.

Set res to the reversal x^{n-1} f(1/x) of the polynomial f = poly truncated to length n, considered as a polynomial of length n. The underscore version requires \mathit{len} \le n, writes n coefficients and allows res to be poly.

Returns the largest k such that input is a polynomial in x^k. For a polynomial of length at most 1 the result is its length.

fq_nmod_poly_deflate sets result to g with g(x^k) = f for the polynomial f = input and k = deflation, which must divide the exponents of all nonzero terms of f; it throws FLINT_DIVZERO for k = 0. fq_nmod_poly_inflate sets result to f(x^k) for k = inflation.

Sets x to the coefficient of x^n in poly, which is zero for n at least the length.

Set the coefficient of x^n, n \ge 0, to the element x, respectively to the image of the integer x in \mathbb{F}_p, extending and normalising the polynomial as needed.

Set f to a random polynomial of length at most len, with coefficients from fq_nmod_randtest; the second version returns a nonzero polynomial and requires len > 0 (it throws otherwise).

Sets f to a random monic polynomial of length len \ge 1.

Sets f to a random monic irreducible polynomial of length len \ge 2. Random monic polynomials are tested by computing \gcd(f, x^{q^i} - x) for i \le (\mathit{len} - 1)/2 until one is irreducible, which takes about len attempts on average.

Set (res, max(len1, len2)) to the sum, respectively the difference, of the two arrays. Aliasing of res with the inputs is allowed.

Set rop to \mathit{op1} + \mathit{op2}, respectively \mathit{op1} - \mathit{op2}.

Sets rop to \mathit{op1} + c, where c is mapped to \mathbb{F}_p.

Set rop to the sum, respectively the difference, of the two polynomials truncated to length n.

Set rop to -\mathit{op}.

Set rop to x \cdot \mathit{op}.

Set rop to \mathit{op} / x. Throws FLINT_ERROR if x is zero.

Add x \cdot \mathit{op} to rop, respectively subtract it. The underscore versions work on the first len coefficients of both arrays.

Set rop to \mathit{op1} \cdot \mathit{op2}, choosing the algorithm. The underscore version writes len1 + len2 - 1 coefficients, requires len1, len2 \ge 1 and does not allow aliasing.

Set rop to the product, computed by the classical algorithm with one dot product (reduced once) per coefficient (a wrapper of _gr_poly_mullow_classical). The underscore version requires len1, len2 \ge 1 and does not allow aliasing.

Set rop to the product, computed by Kronecker substitution: every coefficient is packed into one integer, the integer polynomials are multiplied with _fmpz_poly_mul, and the coefficients are unpacked and reduced. The underscore version allows zero padding of the inputs (it writes len1 + len2 - 1 coefficients) and aliasing.

Set rop to the product, computed by substituting y = x^{2d-1} for the generator of \mathbb{F}_q, which gives one product in (\mathbb{Z}/p\mathbb{Z})[x] of length about (2d - 1)\,\mathit{len} computed with _nmod_poly_mul, and reducing each block of 2d - 1 coefficients modulo the defining polynomial. The underscore version requires len1, len2 \ge 1 and writes len1 + len2 - 1 coefficients.

Set rop to the product truncated to length n, that is, the low n coefficients of \mathit{op1} \cdot \mathit{op2}. The underscore version requires 0 < n \le \mathit{len1} + \mathit{len2} - 1 and len1, len2 \ge 1, writes n coefficients and does not allow aliasing. The classical algorithm is used for n below FQ_NMOD_MULLOW_CLASSICAL_CUTOFF (6) or short inputs, and Kronecker substitution otherwise.

Truncated products with a fixed algorithm: classical, Kronecker substitution, or the substitution y = x^{2d-1}. The underscore versions require 0 < n \le \mathit{len1} + \mathit{len2} - 1 and write n coefficients; _fq_nmod_poly_mullow_KS allows zero padding and zero inputs.

Compute the coefficients of index at least n (start) of the product. fq_nmod_poly_mulhigh sets rop to a polynomial of length len1 + len2 - 1 whose coefficients from start on are those of the product and whose lower coefficients are zero; it uses the classical algorithm. _fq_nmod_poly_mulhigh requires len1 \ge len2 \ge 1 and space for len1 + len2 - 1 coefficients in res; its coefficients below n are arbitrary (it computes the full product by Kronecker substitution for inputs of length at least 6).

As the previous functions, with the classical algorithm, which computes only the coefficients from start on and sets the lower ones to zero. The underscore version requires len1 \ge len2 \ge 1 and does not allow aliasing.

Set res to \mathit{poly1} \cdot \mathit{poly2} \bmod f. The underscore version requires \mathit{len1} + \mathit{len2} > \mathit{lenf} (the product must need reduction), writes \mathit{lenf} - 1 coefficients and needs space for len1 + len2 - 1 coefficients in res, which must not be aliased with f. fq_nmod_poly_mulmod throws FLINT_DIVZERO if f = 0.

As fq_nmod_poly_mulmod, with the precomputed inverse finv of the reversal of f modulo x^{\deg f + 1} (fq_nmod_poly_reverse followed by fq_nmod_poly_inv_series). The product must satisfy \mathit{len1} + \mathit{len2} - 1 \le 2\,\mathit{lenf} - 2; the inputs need not be reduced. The underscore version does not allow aliasing.

Set rop to \mathit{op}^2, choosing the algorithm as for multiplication. The underscore version writes 2 * len - 1 coefficients, requires len \ge 1 and does not allow aliasing.

Squaring with a fixed algorithm: classical or Kronecker substitution. The underscore versions write 2 * len - 1 coefficients; the classical version does not allow aliasing.

Set rop to \mathit{op}^e, with \mathit{op}^0 = 1. The underscore version requires e > 0, len > 0 and space for e(\mathit{len} - 1) + 1 coefficients, and does not allow aliasing. It uses binary exponentiation (_gr_poly_pow_ui_binexp).

Set res to \mathit{poly}^e \bmod x^{\mathit{trunc}}, by binary exponentiation with truncated multiplications. The underscore versions require the input to be zero-padded to length trunc, trunc > 0, e > 1 and space for trunc coefficients, and do not allow aliasing.

Set res to \mathit{poly}^e \bmod f for e \ge 0, by binary exponentiation. The underscore versions require e > 0, lenf > 1, poly reduced modulo f and zero-padded to length lenf - 1, and space for lenf - 1 coefficients in res.

As the previous functions, with the precomputed inverse finv of the reversal of f, so that every reduction is a Newton division with two multiplications.

As fq_nmod_poly_powmod_fmpz_binexp_preinv, using sliding window exponentiation with windows of k bits; k = 0 chooses k from the size of e.

Set res to x^e \bmod f, using sliding window exponentiation, in which multiplications by x are shifts. The underscore version requires e > 0, lenf > 2 and space for lenf - 1 coefficients. This is the first step of distinct-degree factorisation and irreducibility testing, with e = q.

Set rop to x^n \cdot \mathit{op}. The underscore version writes len + n coefficients and allows aliasing.

Set rop to \lfloor \mathit{op} / x^n \rfloor, dropping the n lowest coefficients; the result is zero if n is at least the length. The underscore version requires len > n, writes len - n coefficients and allows aliasing (the top n coefficients of op are then permuted, not zeroed).

Computes (Q, lenA - lenB + 1) and (R, lenB - 1) with A = BQ + R and \deg R < \deg B, given the inverse invB of the leading coefficient of B. Requires lenA \ge lenB > 0. Allows aliasing of R and A but no other aliasing.

Computes Q and R with A = BQ + R and \deg R < \deg B. B must be nonzero. If \deg A < \deg B, then Q = 0 and R = A.

Compute only the quotient Q of the division of A by B. The underscore version requires lenA \ge lenB > 0 and writes lenA - lenB + 1 coefficients; fq_nmod_poly_div requires B \ne 0.

The same as fq_nmod_poly_div; kept for compatibility with FLINT 2.

Compute only the remainder R of the division of A by B \ne 0. The underscore version writes lenB - 1 coefficients and also accepts lenA < lenB; invB is not used.

As fq_nmod_poly_divrem, for a possibly reducible defining polynomial: if the leading coefficient of B is invertible, sets f = 1 and computes Q and R; otherwise sets f to a nontrivial factor of the defining polynomial (see fq_nmod_gcdinv) and leaves Q and R unchanged. B must be nonzero.

Compute the quotient Q of A by B with two multiplications, given the inverse Binv of the reversal of B modulo x^{\mathit{lenB}}: the reversed quotient is the product of the reversal of A and Binv modulo x^{\mathit{lenA} - \mathit{lenB} + 1}. Requires \mathit{lenA} \le 2\,\mathit{lenB} - 1; the underscore version writes lenA - lenB + 1 coefficients and does not read B. The non-underscore version throws FLINT_DIVZERO for B = 0.

As the previous functions, also computing the remainder R = A - BQ, with one more multiplication. Requires \mathit{lenA} \le 2\,\mathit{lenB} - 1.

Return 1 and set Q = A / B if B divides A, and return 0 otherwise (then Q is undefined). The underscore version requires lenA \ge lenB > 0, space for lenA - lenB + 1 coefficients in Q and no aliasing. fq_nmod_poly_divides throws FLINT_DIVZERO if B = 0. The test performs a full division with remainder.

Removes the highest power of g that divides f from f and returns its exponent. g must have degree at least 1.

Set (Qinv, n) to the inverse of the power series (Q, n) modulo x^n, given the inverse cinv of the constant term. Requires n > 0 and no aliasing. The basecase algorithm is used for small n and Newton iteration (_gr_poly_inv_series_newton) otherwise; the two functions are the same.

Set Qinv to the inverse of the power series Q modulo x^n. The constant term of Q must be nonzero (otherwise FLINT_ERROR is thrown) and n \ge 1.

Set Q to A / B \bmod x^n for power series with B(0) \ne 0. The underscore version requires 0 < \mathit{Alen}, \mathit{Blen} \le n, writes n coefficients and does not allow aliasing. fq_nmod_poly_div_series throws FLINT_DIVZERO if B is zero modulo x^n and FLINT_ERROR if its constant term is zero.

Set g to \sqrt{h}, respectively 1/\sqrt{h}, modulo x^n, for a power series h with constant term 1 (the square root with constant term 1), by Newton iteration. The underscore versions require n > 0 and h zero-padded to length n, and do not allow aliasing. All four throw FLINT_ERROR in characteristic 2 for n > 1; the others throw if the constant term of h is not 1.

If the polynomial is the square of a polynomial, set the output to a square root and return 1; otherwise return 0. The underscore version writes len / 2 + 1 coefficients.

Set rop to the formal derivative of op. The underscore version writes len - 1 coefficients and allows aliasing.

Sets G to a GCD of (A, lenA) and (B, lenB) and returns its length. Requires lenA \ge lenB > 0 and space for lenB coefficients in G. The GCD is not made monic. This is a wrapper of _gr_poly_gcd_euclidean and _gr_poly_gcd_hgcd.

Sets rop to the monic GCD of op1 and op2. The GCD of two zero polynomials is zero.

GCD by the Euclidean algorithm for a possibly reducible defining polynomial: either set f = 1 and G to the GCD (monic in the non-underscore version) and return its length, or set f to a nontrivial factor of the defining polynomial when a leading coefficient is not invertible, leaving G undefined. The underscore version requires lenA \ge lenB > 0 and space for lenB coefficients.

Computes a GCD G of A and B and cofactors S, T (the argument named fq_nmod) with SA + TB = G, and returns the length of G. Requires lenA \ge lenB \ge 1 and (\mathit{lenA}, \mathit{lenB}) \ne (1, 1), space for lenB coefficients in G, lenB - 1 in S and lenA - 1 in T, and no aliasing. G is not made monic. This is a wrapper of _gr_poly_xgcd_euclidean and _gr_poly_xgcd_hgcd.

Computes the monic GCD G of A and B and cofactors S, T (the argument named fq_nmod) with SA + TB = G, where \deg S < \deg B - \deg G and \deg T < \deg A - \deg G when both are nonzero. The GCD of two zero polynomials is zero, with zero cofactors. G, S and T must be distinct objects.

Extended Euclidean algorithm for a possibly reducible defining polynomial: either set f = 1 and compute G, S, T as fq_nmod_poly_xgcd (the underscore version as _fq_nmod_poly_xgcd), or set f to a nontrivial factor of the defining polynomial, leaving the outputs undefined.

Set the result to f(a), by Horner's rule. Any length is allowed.

Set ys[i] to f(x_i) for the n points xs, using _vec_iter for polynomials of length below 32 and _vec_fast otherwise.

Evaluate at the n points one by one with Horner's rule, at the cost of O(n \cdot \mathit{len}) operations.

Evaluate at the n points by building the subproduct tree of the points and reducing the polynomial down the tree (Multipoint evaluation and interpolation), at the cost of O(M(n) \log n) operations plus one initial division.

Evaluates (poly, plen) at the len points whose subproduct tree tree was built by _fq_nmod_poly_tree_build, writing the values to vs.

Allocate, respectively free, a subproduct tree for len points, with \lceil \log_2 \mathit{len} \rceil + 1 levels of initialised polynomials.

Fills the subproduct tree for the len points roots: level 0 holds the linear factors x - a_i, and each higher level the products of pairs of the level below.

Set rop to the composition g(h(x)) of g = op1 and h = op2. The underscore version requires nonzero inputs, space for (\mathit{len1} - 1)(\mathit{len2} - 1) + 1 coefficients and no aliasing.

Set res to f(g) \bmod h for f = poly1, g = poly2 and h = poly3 \ne 0, choosing between Horner's rule and the Brent–Kung algorithm. The underscore version requires g reduced modulo h and zero-padded to length lenh - 1, writes lenh - 1 coefficients and does not allow aliasing.

As fq_nmod_poly_compose_mod, given the inverse of the reversal of h.

Modular composition by Horner's rule, with \deg f multiplications modulo h. Requirements as for fq_nmod_poly_compose_mod; the _preinv versions also require \mathit{lenf} < \mathit{lenh} and the inverse of the reversal of h.

Modular composition f(g) \bmod h by the Brent–Kung algorithm: the powers g^i \bmod h for i < m = \lceil \sqrt{\mathit{lenf}} \rceil are computed, f is split into m blocks, the block compositions are obtained by one m \times m by m \times \deg h matrix product, and the results are combined by Horner's rule in g^m. Requires \deg f < \deg h and g reduced modulo h; the _preinv versions also require the inverse of the reversal of h. No aliasing in the underscore versions.

Set the rows of the matrix A to the coefficients of the powers g^i \bmod h, 0 \le i < m, for g = poly1 and h = poly2, as needed by fq_nmod_poly_compose_mod_brent_kung_precomp_preinv. A must have exactly m = \lfloor \sqrt{\deg h} \rfloor + 1 rows and \deg h columns (otherwise fq_nmod_poly_precompute_matrix throws FLINT_ERROR), and poly2inv must be the inverse of the reversal of h. In the underscore version g must be reduced and zero-padded to length len2 - 1.

Set res to f(g) \bmod h for f = poly1 with \deg f < \deg h, using the matrix A of powers of g computed by fq_nmod_poly_precompute_matrix. This amortises the precomputation over many compositions with the same g, as in the iterated Frobenius computations of factorisation.

Sets the rows of A to the rows of B, considered as polynomials, reduced modulo f; A must have \deg f columns. Used for the precomputation of the Brent–Kung matrix.

Sets p to the characteristic polynomial \det(xI - M) of the square matrix M; throws FLINT_ERROR if M is not square. This is a wrapper of gr_mat_charpoly, which uses the Berkowitz algorithm for n \le 12 and Danilevsky's algorithm otherwise (for fq_zech, from n = 5); see Characteristic and minimal polynomials.

Sets p to the minimal polynomial of the square matrix X, the monic polynomial of least degree with p(X) = 0; throws FLINT_ERROR if X is not square. This is a wrapper of gr_mat_minpoly_field.

Print the polynomial to file, respectively stdout: the length, two spaces, and the coefficients in the format of fq_nmod_fprint separated by single spaces. Return a positive value on success and a non-positive value on failure.

Print the polynomial in the variable x, with coefficients other than 1 in parentheses in the format of fq_nmod_fprint_pretty, for example x^2+(a+1)*x+(a). Return a positive value on success.

Return the plain, respectively pretty, representation as a newly allocated string, which the caller must free with flint_free.