fmpz_mod_poly.h

Initialise poly as the zero polynomial. fmpz_mod_poly_init allocates nothing, fmpz_mod_poly_init2 allocates space for alloc coefficients.

Frees the memory used by poly, which must be initialised again before it is used.

Changes the allocated space of poly to alloc coefficients. If the length exceeds alloc, the polynomial is truncated to length alloc and normalised. For alloc = 0 the polynomial is cleared and reinitialised.

Ensure that poly has space for at least len coefficients. If it has to grow, it grows to at least twice the old allocation, so that repeated calls cost amortised linear time. The length and coefficients are not changed.

Decreases the length of poly until the leading coefficient is nonzero or the length is zero.

Sets the length of poly to len. If len is smaller than the current length, the discarded coefficients are set to zero (freeing their memory); otherwise the coefficients between the old and the new length must already be valid. The result is not normalised.

Truncates poly to length len (if it is longer) and normalises it.

Sets res to poly truncated to length n, that is, to \mathit{poly} \bmod x^n.

Return the length and the degree of poly. The zero polynomial has length 0 and degree -1.

Returns a pointer to the leading coefficient of poly, or NULL if poly is zero.

Return whether poly is 0, 1, or the generator x. Modulo n = 1 every polynomial is zero; fmpz_mod_poly_is_gen then returns 1, while fmpz_mod_poly_is_one returns 0.

Returns whether f is nonzero with leading coefficient 1.

Returns whether op is a constant that is invertible modulo n (or whether n = 1). For prime n these are exactly the units of (\mathbb{Z}/n\mathbb{Z})[x]; for composite n there are also nonconstant units, such as 1 + 2x modulo 4, which this function does not recognise.

Returns whether A is normalised and has all its coefficients reduced modulo n. Useful for checking the result of low-level manipulations.

Returns the number of nonzero coefficients of A.

Return whether poly1 and poly2 are equal, respectively equal modulo x^n.

Set f to a random polynomial of length at most len with uniformly distributed coefficients; fmpz_mod_poly_rand_monic makes the coefficient of x^{\mathit{len} - 1} equal to 1 (\mathit{len} > 0).

Sets f to a random irreducible polynomial of length at most len with uniformly distributed coefficients, by testing random polynomials with fmpz_mod_poly_is_irreducible. Requires \mathit{len} \ge 1 and a prime modulus.

Set f to a random polynomial of length at most len, nonzero (\mathit{len} \ge 1), or monic of length exactly len. The coefficients are drawn with fmpz_randtest_mod, which favours special values (small values, values close to n), as appropriate for testing.

Set f to a random irreducible polynomial of length at most len (respectively a monic one of length exactly len), for testing. Requires \mathit{len} \ge 1 and a prime modulus.

Sets f to a random monic irreducible polynomial of length len whose roots generate the multiplicative group of \mathbb{F}_{p^{\mathit{len} - 1}} (a primitive polynomial), tested with fq_is_primitive.

Set f to a random monic polynomial of length len of the form x^{d} + a x^k + b with 0 < k < d (trinomial, \mathit{len} \ge 3), or x^{d} + a_3 x^3 + a_2 x^2 + a_1 x + a_0 (pentanomial, \mathit{len} \ge 5), where d = \mathit{len} - 1 and some of the random coefficients may be zero.

Try up to max_attempts random trinomials or pentanomials of length len (without limit if max_attempts is 0) and return 1 as soon as one is irreducible, with f set to it; return 0 if none was found.

Sets f to a sparse monic irreducible polynomial of length len: an irreducible trinomial if one is found in 2 \mathit{len} attempts, otherwise a pentanomial (likewise), otherwise a random monic irreducible polynomial with few terms.

Sets poly1 to poly2.

Swaps poly1 and poly2 efficiently, by swapping the structures.

Set poly to 0, 1 or the generator x (all three are zero for n = 1).

Sets the coefficients of x^k for i \le k < j to zero, normalising the result if the top coefficients were cleared. Indices outside [0, \mathit{len}) are ignored.

Set res to the reversal x^{n-1} \mathit{poly}(1/x) of poly viewed as a polynomial of length n (truncated or zero-padded). The underscore version writes exactly n coefficients, requires \mathit{len} \le n and allows res and poly to be the same array; the other version normalises the result, which can therefore be shorter than n.

Set the polynomial to the constant x or c, reduced modulo n.

Sets f to the integer polynomial g reduced modulo n.

Sets f to the integer polynomial whose coefficients are the representatives in [0, n) of the coefficients of g.

Copy the coefficients between an fmpz_mod_poly_t and an nmod_poly_t, assuming that both have the same modulus, which is not checked (no context is passed). For fmpz_mod_poly_get_nmod_poly, the modulus of f must already be set.

Set the coefficient of x^n, n \ge 0, to x reduced modulo the modulus, extending or normalising the polynomial as needed.

Sets x to the coefficient of x^n in poly (zero if n is at least the length).

Set the output to the input multiplied by x^n. The underscore version writes len + n coefficients and allows res and poly to be the same array.

Set the output to the input divided by x^n, discarding the low coefficients; the result is zero if n is at least the length. The underscore version writes len - n coefficients, requires \mathit{len} > n and allows res and poly to be the same array.

Sets result to p(x^m) where p is input and m = inflation.

Sets result to p(x^{1/m}) where p is input and m \ge 1 = deflation, which must divide the exponents of all nonzero terms of input (see fmpz_mod_poly_deflation). m = 0 raises an exception.

Returns the largest m such that input is a polynomial in x^m, that is, the gcd of the exponents of its nonzero terms; 0 for the zero polynomial and 1 for a nonzero constant.

Set res to the sum or difference of (poly1, len1) and (poly2, len2), writing \max(\mathit{len1}, \mathit{len2}) coefficients without normalising. res may be one of the inputs.

Set res to \mathit{poly1} + \mathit{poly2}, respectively \mathit{poly1} - \mathit{poly2}.

Set res to the sum or difference of poly1 and poly2 truncated to length n.

Set res to \mathit{poly} + c, \mathit{poly} - c or c - \mathit{poly} for an integer constant c, which is reduced modulo n.

Set res to -\mathit{poly}.

Set res to x \cdot \mathit{poly}, with x reduced modulo n (it need not be reduced on input).

Sets A to A + x B.

Set res to x^{-1} \cdot \mathit{poly}. If x is not invertible modulo n, an exception is raised (FLINT_DIVZERO for x \equiv 0, FLINT_ERROR otherwise).

Set res to the product of poly1 and poly2. The underscore version writes \mathit{len1} + \mathit{len2} - 1 coefficients, requires positive lengths (in either order) and allows zero-padded inputs.

Set res to the product of poly1 and poly2 truncated to length n. The underscore version requires positive lengths and 0 < n \le \mathit{len1} + \mathit{len2} - 1, and does not allow aliasing.

Set res to the coefficients of index \mathit{nlo} \le i < \mathit{nhi} of the product, that is, to ((\mathit{poly1} \cdot \mathit{poly2}) \bmod x^{\mathit{nhi}}) / x^{\mathit{nlo}}. The underscore version requires positive lengths and 0 \le \mathit{nlo} < \mathit{nhi} \le \mathit{len1} + \mathit{len2} - 1, writes \mathit{nhi} - \mathit{nlo} coefficients and does not allow aliasing.

Sets the coefficients of index at least start of res to those of the product of poly1 and poly2. The coefficients of index less than start are arbitrary (they are not set to zero).

Set res to the square of poly; the underscore version writes 2 \mathit{len} - 1 coefficients.

Set res to \mathit{poly1} \cdot \mathit{poly2} \bmod f. The underscore version requires \mathit{len1} + \mathit{len2} - \mathit{lenf} > 0 (so that a reduction takes place), writes \mathit{lenf} - 1 coefficients and does not allow res to alias f. The leading coefficient of f must be invertible (FLINT_IMPINV otherwise).

Like fmpz_mod_poly_mulmod, given finv, the inverse of the reversal of f modulo x^{\mathit{lenf}} (computed with fmpz_mod_poly_reverse and fmpz_mod_poly_inv_series). Both factors must be reduced modulo f (len1, len2 < \mathit{lenf}); otherwise an exception is raised.

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

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

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

Like the previous functions, given finv, the inverse of the reversal of f modulo x^{\mathit{lenf}}, so that each reduction modulo f costs two multiplications.

Set res to x^e \bmod f for e \ge 0 by sliding-window exponentiation, given finv as above. Multiplications by x are shifts, which makes this cheaper than powering a general polynomial. The underscore version requires e > 0 and \mathit{lenf} > 2 and writes \mathit{lenf} - 1 coefficients.

Sets res to (x + a)^e \bmod f for e \ge 0, given finv as above, by binary exponentiation in which the multiplications by x + a are done in linear time. Used in root finding. A negative e raises an exception.

Set the n entries of res to f^0, f^1, \ldots, f^{n-1} \bmod g by repeated multiplication. In the underscore version f must be reduced modulo g (with length \mathit{flen} > 0, possibly zero-padded), each res[i] must have space for \mathit{glen} - 1 coefficients, and ginv is the inverse of the reversal of g. The entries of res must not alias the inputs.

Like the previous functions, computing the powers with a baby-step giant-step scheme in which blocks of consecutive powers are computed in parallel using the threads of the given thread pool (respectively the threads available through flint_get_num_threads).

Compute (and free) the table of x^{p^{2^i}} \bmod f for 2^i \le m, where p is the modulus, given finv, the inverse of the reversal of f. The first entry is computed by exponentiation and each following one by modular composition of the previous one with itself.

Sets res to x^{p^m} \bmod f using the table pow from fmpz_mod_poly_frobenius_powers_2exp_precomp (computed for a bound at least m), by modular compositions of the table entries along the binary expansion of m (see Finite fields and the Frobenius map).

Compute (and free) the table of all x^{p^k} \bmod f for 0 \le k \le m, given finv.

Compute Q and R with A = BQ + R and \deg R < \deg B. The leading coefficient of B must be invertible; invB is its inverse. The underscore version requires \mathit{lenA} \ge \mathit{lenB} > 0, writes \mathit{lenA} - \mathit{lenB} + 1 coefficients of Q and \mathit{lenB} - 1 of R, allows zero-padding of A and no aliasing. A zero B raises FLINT_DIVZERO (except modulo 1).

Set Q to the quotient of the division of A by B, with the same conventions as the division with remainder.

Set R to A \bmod B, with the same conventions as the division with remainder.

Division with remainder, respectively remainder, by the classical algorithm in O(\mathit{lenB} (\mathit{lenA} - \mathit{lenB} + 1)) operations. In the underscore versions R (of length \mathit{lenA} for _fmpz_mod_poly_divrem_basecase, \mathit{lenB} - 1 for _fmpz_mod_poly_rem_basecase) may alias A, but no other aliasing is allowed.

Division with remainder, respectively quotient only, given Binv, the inverse of the reversal of B modulo x^{\mathit{lenB}}: the quotient is a truncated product of the reversed A with Binv, and the remainder costs one more product. Requires \mathit{lenA} \le 2 \mathit{lenB} - 2; the non-underscore versions raise an exception otherwise.

Division with remainder (respectively remainder) for a possibly composite modulus: if the leading coefficient of B is invertible, sets f = 1 and computes the result; otherwise sets f to the nontrivial factor \gcd(\mathrm{lc}(B), n) of n and leaves Q and R unchanged. A zero B raises a division by zero exception.

Divides f by the largest power of p that divides it and returns the exponent. p must have an invertible leading coefficient. An exception is raised if p is zero or constant.

Return 1 and set Q = A/B if B divides A, and otherwise return 0 and set Q to zero. The leading coefficient of B must be invertible. The underscore versions require \mathit{lenA} \ge \mathit{lenB} > 0 and write \mathit{lenA} - \mathit{lenB} + 1 coefficients.

Set Qinv to the inverse of the power series Q modulo x^n, n \ge 1, by Newton iteration (_gr_poly_inv_series). The constant term of Q must be invertible: zero raises FLINT_DIVZERO, a non-invertible nonzero value (composite modulus) another exception. The underscore version writes n coefficients and does not allow aliasing.

Like fmpz_mod_poly_inv_series for a possibly composite modulus: sets f = 1 and Qinv to the inverse, or sets f to a nontrivial factor of n (when the constant term is not invertible) with Qinv undefined.

Set Q to A/B \bmod x^n. The constant term of B must be invertible (an exception is raised otherwise). The underscore version requires \mathit{Alen}, \mathit{Blen} \le n.

Set g to \sqrt{h}, respectively 1/\sqrt{h}, modulo x^n, the series being defined by the binomial expansion of (1 + y)^{\pm 1/2}. The constant term of h must be 1 (an exception is raised otherwise), and 2 must be invertible modulo n. The underscore versions require n > 0 and \mathit{hlen} > 0 and do not allow aliasing.

Sets res to poly divided by its leading coefficient (zero if poly is zero). A non-invertible leading coefficient raises FLINT_IMPINV.

Either sets f = 1 and res to poly made monic, or sets f to a nontrivial factor of n (the gcd of n with the leading coefficient) and leaves res undefined.

Set G to the greatest common divisor of A and B, which is made monic by the non-underscore version (the gcd of two zero polynomials is zero). The underscore version requires \mathit{lenA} \ge \mathit{lenB} > 0 and space for \mathit{lenB} coefficients in G, returns the length of G and does not normalise its leading coefficient. The modulus must be prime.

GCD for a possibly composite modulus by the Euclidean algorithm: either sets f = 1 and computes G as in fmpz_mod_poly_gcd (the underscore versions returning its length), or sets f to a nontrivial factor of n met as a non-invertible leading coefficient of a remainder, with G undefined (the underscore versions then return 0). The _gcd_f names are aliases of the _gcd_euclidean_f functions. The underscore versions require \mathit{lenA} \ge \mathit{lenB} > 0 and do not allow aliasing.

One step of the half-GCD algorithm (_gr_poly_hgcd): for \mathit{lena} > \mathit{lenb} > 0, computes the 2 \times 2 matrix M (the entries M[0], ..., M[3] with lengths lenM[0], ..., lenM[3], each with space for lena coefficients) and the two consecutive remainders A, B of the Euclidean remainder sequence of (a, b) that straddle half the degree of a, such that (A, B)^T = \sigma M^{-1} (a, b)^T, and returns the sign \sigma = \pm 1. A and B need space for lena and lenb coefficients; their lengths are returned in *lenA, *lenB. See Half-GCD.

Compute the GCD G of A and B and cofactors with SA + TB = G. The non-underscore version makes G monic, with \deg S < \deg B and \deg T < \deg A (if A or B is nonzero; if both are zero, all outputs are zero). The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1 with (\mathit{lenA}, \mathit{lenB}) \ne (1, 1), does not make G monic, needs space for \mathit{lenB}, \mathit{lenB} - 1 and \mathit{lenA} - 1 coefficients in G, S, T, returns the length of G, and does not allow aliasing (invB is not used). The modulus must be prime.

Extended GCD for a possibly composite modulus by the Euclidean algorithm: either set f = 1 and compute the outputs as in fmpz_mod_poly_xgcd (with the same conventions for the underscore versions, where invB is the inverse of the leading coefficient of B), or set f to a nontrivial factor of n. The _xgcd_f names are aliases of the _xgcd_euclidean_f functions.

Compute G = \gcd(A, B) and S, both reduced modulo B, with G \equiv SA \pmod B; when G = 1, S is the inverse of A modulo B. Requires \mathit{len}(B) \ge 2 (an exception is raised otherwise); if A \equiv 0 \pmod B, sets G = S = 0. The underscore versions require 0 < \mathit{lenA} < \mathit{lenB}, write lenA coefficients of G and \mathit{lenB} - 1 of S, and return the length of G, which is not made monic. fmpz_mod_poly_gcdinv uses the Euclidean algorithm for \mathit{lenB} < 16 and the extended half-GCD algorithm otherwise. The modulus must be prime.

Versions of the previous functions for a possibly composite modulus: either set f = 1 and compute G and S, or set f to a nontrivial factor of n.

If B is invertible modulo P, set A to the inverse (reduced modulo P) and return 1; otherwise return 0, with A undefined. The modulus must be prime. fmpz_mod_poly_invmod raises an exception if \deg P < 1 and reduces B modulo P first. The underscore version requires 0 < \mathit{lenB} < \mathit{lenP} (allowing zero-padding of B), writes \mathit{lenP} - 1 coefficients and does not allow aliasing.

Versions of the previous functions for a possibly composite modulus: either set f = 1 and behave as fmpz_mod_poly_invmod, or set f to a nontrivial factor of n.

Set res to the resultant of the two polynomials (zero if one of them is zero), computed with _gr_poly_resultant, which uses the Euclidean or the half-GCD algorithm. The underscore version requires \mathit{len1} \ge \mathit{len2} > 0. The modulus should be prime; for a composite modulus the function raises an exception if it meets a non-invertible leading coefficient.

Set d to the discriminant of f, normalised as

with n = \deg f and m = \deg f' (so \operatorname{lc}(f)^{-1} when p \nmid n); then \operatorname{disc}(f) = \operatorname{lc}(f)^{2n-2} \prod_{i < j} (r_i - r_j)^2 over the roots r_i of f. The discriminant of a polynomial of degree less than 1, or with f' = 0, is zero. The underscore version requires \mathit{len} > 1.

Set res to the derivative of poly. The underscore version writes \mathit{len} - 1 coefficients and allows aliasing.

Set res to the value of the polynomial at a (reduced modulo n first if necessary), by Horner's rule. res may alias a in the non-underscore version, but not a coefficient of poly.

Evaluate the polynomial at the n reduced points xs, writing the values to ys. Uses Horner's rule for each point if the length of the polynomial is less than 32, and fast multipoint evaluation otherwise.

Evaluate the polynomial at the n reduced points xs by Horner's rule for each point, in O(n \cdot \mathit{len}) operations.

Evaluate the polynomial at the reduced points by fast multipoint evaluation: the remainders modulo the products in a subproduct tree of the points are computed from the root to the leaves, in O(M(n) \log n) operations (Multipoint evaluation and interpolation). The _precomp version takes the tree built by _fmpz_mod_poly_tree_build for len points.

Allocate, free and fill a subproduct tree for len points: level 0 holds the linear factors x - r_i and each following level the products of pairs from the level below; the root (the product of all factors) is not computed.

Set poly to the monic polynomial (x - x_0)(x - x_1) \cdots (x - x_{n-1}) for reduced x_i, by a quadratic algorithm for n < 20 and by splitting the roots into halves otherwise. The underscore version writes n + 1 coefficients and does not allow aliasing.

If the nonzero polynomial P has \deg P distinct nonzero roots in \mathbb{F}_p, writes them to roots[0], ..., roots[deg(P) - 1] and returns 1; otherwise returns 0. The modulus must be prime.

Splits f of degree at least 2, assumed to have \deg f distinct nonzero roots in \mathbb{F}_p, into two nontrivial factors a and b with \deg a \ge \deg b, as a = \gcd(f, (x + \delta)^{(p-1)/2} - 1) for random \delta (degree 2 is solved directly with a square root). halfp must be (p - 1)/2, and t, t_2 are scratch polynomials.

Set res to the composition \mathit{poly1}(\mathit{poly2}), by _gr_poly_compose. The underscore version requires nonzero inputs, writes (\mathit{len1} - 1)(\mathit{len2} - 1) + 1 coefficients and does not allow aliasing.

Set res to f(g) \bmod h (in the non-underscore version f, g, h are poly1, poly2, poly3), choosing between Horner's rule and the Brent–Kung algorithm according to the lengths.

Set res to f(g) \bmod h by Horner's rule, with \mathit{lenf} - 1 multiplications modulo h.

Set res to f(g) \bmod h by the Brent–Kung baby-step giant-step algorithm [BrentKung1978], with about 2\sqrt{n} multiplications modulo h and one product of a \sqrt{n} \times \sqrt{n} by a \sqrt{n} \times n matrix, n = \deg h. Requires \deg f < \deg h.

Like fmpz_mod_poly_compose_mod_brent_kung, given poly3inv, the inverse of the reversal of h = poly3 modulo x^{\mathit{len3}}.

Set the rows of A to the coefficients of g^i \bmod h for 0 \le i < m, where g = poly1 is reduced modulo h = poly2, poly2inv is the inverse of the reversal of h, and A must have been initialised as an m \times \deg h matrix with m = \lfloor \sqrt{\deg h} \rfloor + 1. This is the precomputation for repeated compositions with the same g and h.

Set res to f(g) \bmod h for f = poly1 with \deg f < \deg h, h = poly3, given the matrix A of powers of g computed by fmpz_mod_poly_precompute_matrix and the inverse poly3inv of the reversal of h. Only the matrix product and the giant steps remain, which makes repeated compositions with the same g, such as the Frobenius iterations in factorisation, cheaper.

Initialises A and sets its rows to the rows of B reduced modulo f: B is a matrix of powers g^i \bmod h as above and f a divisor of h, so that A is the corresponding matrix modulo f, with \lfloor \sqrt{\deg f} \rfloor + 1 rows and \deg f columns.

If the polynomial is a perfect square, set the output to a square root and return 1; otherwise return 0 (and set b to zero). The modulus must be prime. The underscore version writes \mathit{len}/2 + 1 coefficients.

Set poly to a minimal generating polynomial of (seq, len), choosing the Berlekamp–Massey algorithm for \mathit{len} < \max(200, 530 - 22s), s being the number of limbs of the modulus, and the half-GCD algorithm otherwise. The underscore version needs space for \mathit{len} + 1 coefficients, returns the length of poly and does not allow aliasing.

Like fmpz_mod_poly_minpoly, using the Berlekamp–Massey algorithm [Ber1968] [Mas1969], in O(\mathit{len} \cdot d) operations for a minimal polynomial of degree d.

Like fmpz_mod_poly_minpoly, using a half-GCD of x^{\mathit{len}} and the reversed sequence, in O(M(\mathit{len}) \log \mathit{len}) operations regardless of the degree.

Initialise B with an empty stream of points, respectively free it.

Empties the stream of points of B.

Append points (reduced modulo n) to the stream of B: count points from a, count zeros, or a single point. V and R are not updated until the next call to fmpz_mod_berlekamp_massey_reduce.

Brings V and R up to date with the points added so far and returns 1 if V changed, 0 otherwise. For example, after the points 1, 1, 2, 3 the call returns 1 with \deg R < \deg V = 2, since the Fibonacci recurrence has been recognised; after adding 5, 8 another call returns 0.

Return the number of points stored in B and a pointer to them (which may be NULL if there are none).

Return pointers to the polynomials V and R of B, as of the last call to fmpz_mod_berlekamp_massey_reduce.

Prints V and the stored points of B to standard output, for debugging.

Initialise D with the data for radix conversion with respect to R of polynomials of degree at most degF, respectively free it. R must have degree at least 1 and an invertible leading coefficient.

Sets B[0], ..., B[N] to the digits B_i of F with respect to the radix R of D, where N = \lfloor \deg F / \deg R \rfloor and \deg F is at most the bound given to fmpz_mod_poly_radix_init.

Computes the powers R^{2^i} and the inverses of their reversals modulo x^{2^i \deg R} for 0 \le i < k, where invL is the inverse of the leading coefficient of R. Rpow[i] and Rinv[i] need space for 2^i \deg R + 1 and 2^i \deg R coefficients. The data can be used for all F with \mathrm{len}(F) \le 2^k \deg R.

The recursive step of fmpz_mod_poly_radix: F has length 2^{i+1} \deg R (zero-padded), k is the number of digits already accounted for (0 at the top level), every B[j] has space for \deg R coefficients, and W is scratch space of length 2^{i+1} \deg R.

Return a string for poly in the format of fmpz_poly_get_str (the length and the coefficients, without the modulus), respectively the pretty format with variable name x. The string must be freed with flint_free.

Print the polynomial, with its length and modulus, to file or to standard output.

Print the polynomial in the pretty format with variable name x.

Reads a polynomial in the format of fmpz_mod_poly_fprint from file, sets the modulus of ctx to the modulus read (which must be at least 2) and poly to the polynomial, and returns 1 on success and 0 on failure.