nmod_poly.h

Initialise poly as the zero polynomial modulo n \ge 1, without allocating coefficients. nmod_poly_init_preinv takes the precomputed inverse ninv = n_preinvert_limb(n) instead of computing it.

Initialises poly as the zero polynomial with the modulus mod, which must have been set up with nmod_init. This is the cheapest way to create polynomials with the modulus of an existing one, nmod_poly_init_mod(a, b->mod).

Like nmod_poly_init and nmod_poly_init_preinv, but allocate space for alloc coefficients.

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 coefficients are freed and poly becomes zero.

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

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

Replaces the modulus of poly by mod without changing the coefficients, which must be reduced modulo the new modulus.

Sets the length field of poly to len without zeroing or normalising anything. poly must have space for len coefficients.

Decreases the length of poly until the leading coefficient is nonzero or the length is zero. This is the usual last step after writing coefficients with an underscore function.

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

Returns the modulus n of poly.

Returns the number of bits of the largest coefficient of poly, or 0 for the zero polynomial.

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

Return the number of nonzero coefficients.

Returns whether poly is the zero polynomial.

Return whether poly is the constant 1, respectively the generator x. For n = 1 both return 1, since every polynomial is zero modulo 1.

Returns whether poly is a nonzero constant, which for prime n is the same as being a unit. For composite n the result does not tell whether the constant is invertible. For n = 1 it returns 1.

Returns whether poly is nonzero with leading coefficient 1.

Sets a to a copy of b.

Swaps poly1 and poly2 in constant time by swapping the structures, including the moduli.

Set res to 0 and to 1. Modulo n = 1, nmod_poly_one sets res to the zero polynomial.

Set res to poly truncated to length len, that is, poly modulo x^{\mathit{len}}, and truncate poly in place. The result is normalised. Nothing happens if len is at least the length.

Set output to the reversal x^{m-1} f(1/x) of the input f viewed as a polynomial of length m \ge 0: coefficient i of the output is coefficient m - 1 - i of the input, taken as 0 beyond its length. Input coefficients from index m on are ignored.

Returns the coefficient of x^j, or 0 if j is at least the length. Requires j \ge 0.

Sets the coefficient of x^j to c \bmod n, for any c. The polynomial grows, with zero coefficients in between, or shrinks if the leading coefficient is set to zero.

Returns whether a and b are equal. The moduli are not compared.

Return whether poly is the constant cst. nmod_poly_equal_nmod requires cst to be reduced; nmod_poly_equal_ui reduces it first.

Returns whether poly1 and poly2 agree modulo x^n. A negative n is treated as 0.

Set poly to a random polynomial of length at most len, respectively a random monic polynomial of length exactly \mathit{len} \ge 1.

Sets poly to a random irreducible polynomial of length at most len. Since nmod_poly_is_irreducible regards nonzero constants as irreducible, the result can be a constant, and it need not be monic.

Set poly to a random test polynomial of length at most len, a nonzero one (requires \mathit{len} \ge 1 and n \ge 2), and a monic one of length exactly \mathit{len} \ge 1.

Set poly to a random irreducible polynomial of length at most len (which may be a constant), and to a random monic irreducible polynomial of length exactly \mathit{len} \ge 2.

Sets poly to a random monic irreducible polynomial of length \mathit{len} \ge 2 whose root generates the multiplicative group of the field \mathbb{F}_n[x]/(\mathit{poly}). Primitivity is tested with fq_nmod_is_primitive.

Set poly to a random monic polynomial of length len with at most three nonzero terms x^{\mathit{len}-1} + a x^k + b, 0 < k < \mathit{len} - 1 (requires \mathit{len} \ge 3), respectively at most five nonzero terms x^{\mathit{len}-1} + a_3 x^3 + a_2 x^2 + a_1 x + a_0 (requires \mathit{len} \ge 5).

Try up to max_attempts random trinomials, respectively pentomials, as above and return 1 as soon as one is irreducible, or 0 if none is. For max_attempts = 0 they try until they succeed, which does not terminate if there is no irreducible polynomial of that shape.

Sets poly to a sparse monic irreducible polynomial of length len: it tries 2 \mathit{len} trinomials, then 2 \mathit{len} pentomials, then random polynomials with a growing number of terms.

Return poly as a string in the plain format and in the pretty format with variable name x. The zero polynomial is "0 n" and "0". Free the string with flint_free.

Reads poly from a string in the plain format and returns 1, or returns 0 if the string is not in this format. The modulus in the string is ignored and the coefficients are not reduced: they must be smaller than the modulus of poly.

Write the polynomial to stdout or to f, in the plain or the pretty format. Return a positive value on success and a non-positive value on failure.

Read a polynomial in the plain format from stdin or from f. Unlike nmod_poly_set_str, they reinitialise poly with the modulus that was read. Return 1 on success and 0 if the input is not in the plain format. The coefficients are not reduced.

Set res to poly times x^k, for k \ge 0. The underscore version writes \mathit{len} + k coefficients and allows res == poly.

Set res to poly divided by x^k, discarding the remainder, for k \ge 0. In the underscore version len is the length of the output: it sets res[i] = poly[i + k] for 0 \le i < \mathit{len}, so poly must have at least \mathit{len} + k coefficients. It allows res == poly.

Set res to the sum and the difference of (poly1, len1) and (poly2, len2), writing \max(\mathit{len1}, \mathit{len2}) coefficients, which may include leading zeros. Any lengths, including 0, are allowed, and res may be poly1 or poly2.

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

Set res to the sum and the difference modulo x^n. A negative n is treated as 0.

Set res to \mathit{poly} + c and \mathit{poly} - c, for any c.

Sets res to c \cdot \mathit{poly}, for reduced c. The result is normalised, which matters for composite n.

Sets res to \mathit{res} + c \cdot \mathit{poly}, for reduced c.

Set output to input divided by its leading coefficient, which must be invertible modulo n (otherwise FLINT_IMPINV is thrown). nmod_poly_make_monic throws FLINT_DIVZERO for the zero polynomial; the underscore version requires \mathit{len} \ge 1 and allows output == input.

Set res to the product \mathit{poly1} \cdot \mathit{poly2}. The underscore version requires \mathit{len1} \ge \mathit{len2} \ge 1, writes \mathit{len1} + \mathit{len2} - 1 coefficients and does not allow res to overlap the inputs; poly1 == poly2 (squaring) is allowed and faster.

Set res to the product truncated to length trunc, that is, \mathit{poly1} \cdot \mathit{poly2} \bmod x^{\mathit{trunc}}. The underscore version requires \mathit{len1} \ge \mathit{len2} \ge 1 and 1 \le \mathit{trunc} \le \mathit{len1} + \mathit{len2} - 1, writes trunc coefficients and does not allow aliasing. Inputs longer than trunc are allowed.

Set the coefficients of res from index n on to those of the product. The coefficients below n are either zero or the coefficients of the product. The underscore version requires \mathit{len1} \ge \mathit{len2} \ge 1, writes \mathit{len1} + \mathit{len2} - 1 coefficients and does not allow aliasing.

Set res to the coefficients \mathit{nlo}, \ldots, \mathit{nhi} - 1 of the product, that is, \lfloor \mathit{poly1} \cdot \mathit{poly2} / x^{\mathit{nlo}} \rfloor \bmod x^{\mathit{nhi} - \mathit{nlo}}. The underscore version requires \mathit{len1}, \mathit{len2} \ge 1 in either order and 0 \le \mathit{nlo} < \mathit{nhi} \le \mathit{len1} + \mathit{len2} - 1, writes \mathit{nhi} - \mathit{nlo} coefficients and does not allow aliasing. The non-underscore version accepts any 0 \le \mathit{nlo} \le \mathit{nhi}.

Set res to the product by the classical algorithm, with O(\mathit{len1} \cdot \mathit{len2}) operations. The underscore version requires \mathit{len1} \ge \mathit{len2} \ge 1 and does not allow aliasing.

Set res to the product modulo x^{\mathit{trunc}} by the classical algorithm. The underscore version requires \mathit{len1} \ge \mathit{len2} \ge 1 and 1 \le \mathit{trunc} \le \mathit{len1} + \mathit{len2} - 1, and does not allow aliasing.

Set the coefficients of res from index start on to those of the product, by the classical algorithm, and the coefficients below start to zero. The underscore version requires \mathit{len1} \ge \mathit{len2} \ge 1, writes \mathit{len1} + \mathit{len2} - 1 coefficients and does not allow aliasing.

Set res to the coefficients \mathit{nlo}, \ldots, \mathit{nhi} - 1 of the product by the classical algorithm, with the same conventions as _nmod_poly_mulmid and nmod_poly_mulmid.

Set res to the product by Kronecker substitution. The underscore version requires \mathit{len1}, \mathit{len2} \ge 1 in either order.

Set res to the product modulo x^n by Kronecker substitution. The underscore version requires \mathit{len1}, \mathit{len2} \ge 1 and 1 \le n \le \mathit{len1} + \mathit{len2} - 1. It multiplies the operands truncated to length n in full and unpacks the low n coefficients.

Set res to the coefficients \mathit{nlo}, \ldots, \mathit{nhi} - 1 of the product by Kronecker substitution, with the same conventions as _nmod_poly_mulmid and nmod_poly_mulmid, except that the output may alias the inputs.

Set res to the product by Kronecker substitution at 2^b and -2^b [Har2009a]. The underscore version requires \mathit{n1} \ge \mathit{n2} \ge 1.

Set res to the product by Kronecker substitution at \pm 2^b and at the reciprocal points \pm 2^{-b} [Har2009a]. The underscore version requires \mathit{n1} \ge \mathit{n2} \ge 1.

Write the coefficients \mathit{znlo}, \ldots, \mathit{zn} - 1 (respectively 0, \ldots, \mathit{zn} - 1) of the product of (a, an) and (b, bn) to z, using fft_small. Require \mathit{an}, \mathit{bn} \ge 1, in either order, and 0 \le \mathit{znlo} < \mathit{zn} \le \mathit{an} + \mathit{bn} - 1; the output must not overlap the inputs.

Return whether fft_small is expected to be the fastest algorithm for a product of lengths len1 and len2 truncated to length n (a full product if n = \mathit{len1} + \mathit{len2} - 1), respectively for m coefficients of a middle product whose shorter operand, after trimming, has length len2.

Internal helper of _nmod_poly_mulmid_fft_small for n \le 23: if the coefficients are small enough, writes the coefficients \mathit{znlo}, \ldots, \mathit{zn} - 1 of the product to z and returns 1; otherwise returns 0 without writing anything. The conditions on the arguments are those of _nmod_poly_mulmid_fft_small.

Set res to \mathit{poly}^e by binary exponentiation; the two pairs of functions are the same. The underscore versions require \mathit{len} \ge 1 and e \ge 1, write (\mathit{len} - 1) e + 1 coefficients and do not allow aliasing. nmod_poly_pow returns 1 for 0^0, but nmod_poly_pow_binexp returns 0.

Set res to \mathit{poly}^e \bmod x^{\mathit{trunc}} by binary exponentiation with truncated products; the two pairs of functions are the same. The underscore versions read exactly trunc coefficients of poly (zero-pad shorter inputs), require \mathit{trunc} \ge 1 and e \ge 1, write trunc coefficients and do not allow aliasing.

Set Q and R to the quotient and remainder of A by B, so that A = BQ + R with \deg R < \deg B. The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1 and writes \mathit{lenA} - \mathit{lenB} + 1 coefficients to Q and \mathit{lenB} - 1 to R. R may be the same array as A; otherwise the outputs must not overlap each other or the inputs.

Set Q to the quotient of A by B without computing the remainder. The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1, writes \mathit{lenA} - \mathit{lenB} + 1 coefficients and does not allow aliasing.

Set R to the remainder of A by B. The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1, writes \mathit{lenB} - 1 coefficients and does not allow aliasing. Quotients of length 2, the typical step of the Euclidean algorithm, use a dedicated routine. nmod_poly_rem throws FLINT_DIVZERO for B = 0 even modulo 1.

Set Q to A / B, assuming that B divides A; otherwise the result is meaningless. The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1, writes \mathit{lenA} - \mathit{lenB} + 1 coefficients and does not allow aliasing.

Set Q to the quotient of A by x - c and return the remainder A(c), by Horner's rule (synthetic division). The value c must be reduced. The underscore version requires \mathit{len} \ge 2 (for smaller lengths it returns 0 and writes nothing), writes \mathit{len} - 1 coefficients and allows Q == A.

If B divides A, set Q = A / B and return 1; otherwise set Q = 0 and return 0. The zero polynomial divides only itself. The underscore versions require \mathit{lenA} \ge \mathit{lenB} \ge 1, write \mathit{lenA} - \mathit{lenB} + 1 coefficients and do not allow aliasing.

Removes the largest power p^k dividing f from f and returns k. Requires \deg p \ge 1: for a nonzero constant p the function does not terminate. For f = 0 it returns 0.

Division with remainder by the schoolbook algorithm, with the same conventions as _nmod_poly_divrem and nmod_poly_divrem.

Set Q to the quotient of A by B, given the power series inverse Binv of the reversal of B (see Computing modulo a fixed polynomial). The quotient is the reversal of \operatorname{rev}(A) \cdot \mathit{Binv} \bmod x^{\mathit{lenQ}}, so Binv must be correct modulo x^{\mathit{lenQ}}, \mathit{lenQ} = \mathit{lenA} - \mathit{lenB} + 1. The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1, does not read B, and does not allow Q to overlap Binv.

Set Q and R to the quotient and remainder of A by B, given Binv as for nmod_poly_div_newton_n_preinv; the remainder is A - BQ computed by a short product. The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1 and does not allow the outputs to overlap the inputs.

Set Qinv to the inverse of the power series Q modulo x^n, that is, Q \cdot \mathit{Qinv} \equiv 1 \pmod{x^n}. The underscore version requires \mathit{Qlen} \ge 1 and n \ge 1, writes n coefficients and does not allow aliasing; Q may be longer than n. The non-underscore version throws FLINT_DIVZERO if Q = 0 or n = 0.

The same, by the O(n \min(n, \mathit{Qlen})) recurrence q_0 = Q_0^{-1}, q_i = -q_0 \sum_{j \ge 1} Q_j q_{i-j}, with each sum computed as a dot product. A binomial Q_0 + c x^k is inverted directly as a geometric series.

The same as _nmod_poly_inv_series and nmod_poly_inv_series, of which they are aliases; they use Newton iteration only when the length makes it faster.

Set Q to A / B \bmod x^n, so that BQ \equiv A \pmod{x^n}. The underscore version requires \mathit{Alen}, \mathit{Blen}, n \ge 1, writes n coefficients and does not allow aliasing. The non-underscore version throws FLINT_DIVZERO if n = 0, B = 0 or B_0 = 0.

The same by the O(n \min(n, \mathit{Blen})) recurrence q_i = B_0^{-1} (A_i - \sum_{j \ge 1} B_j q_{i-j}).

Set res to \mathit{poly1} \cdot \mathit{poly2} \bmod f, computed as a product followed by _nmod_poly_divrem. The underscore version requires \mathit{len1}, \mathit{len2} \ge 1 and \mathit{len1} + \mathit{len2} - 1 \ge \mathit{lenf} (otherwise there is nothing to reduce; use _nmod_poly_mul), writes \mathit{lenf} - 1 coefficients and does not allow res to overlap f. The non-underscore version accepts inputs of any length and throws FLINT_ERROR for f = 0.

Set res to \mathit{poly1} \cdot \mathit{poly2} \bmod f, reducing with _nmod_poly_divrem_newton_n_preinv and the precomputed finv. Both factors must be reduced modulo f: the non-underscore version throws FLINT_ERROR if \mathit{len1} \ge \mathit{lenf} or \mathit{len2} \ge \mathit{lenf}. The underscore version also requires \mathit{len1}, \mathit{len2} \ge 1 and \mathit{len1} + \mathit{len2} - 1 \ge \mathit{lenf}, writes \mathit{lenf} - 1 coefficients and does not allow res to overlap f or finv.

If B is invertible modulo P, set A to its inverse and return 1; otherwise return 0, leaving A undefined. Requires a prime modulus. The non-underscore version reduces B modulo P first, returns 0 for B = 0 and throws FLINT_ERROR if \mathit{lenP} < 2. The underscore version requires 1 \le \mathit{lenB} < \mathit{lenP} (zero padding of B is allowed), writes \mathit{lenP} - 1 coefficients and does not allow aliasing. It calls the extended Euclidean algorithm _nmod_poly_gcdinv.

Set res to \mathit{poly}^e \bmod f by left-to-right binary exponentiation, reducing each product with _nmod_poly_divrem. The non-underscore versions accept any poly (reducing it first) and e \ge 0, and throw FLINT_ERROR for f = 0. The underscore versions require \mathit{lenf} \ge 2, poly reduced and zero-padded to length \mathit{lenf} - 1, and e \ge 1; they write \mathit{lenf} - 1 coefficients and do not allow aliasing.

The same with a precomputed finv, reducing with _nmod_poly_divrem_newton_n_preinv. These are the functions to use for large f or many exponentiations modulo the same f.

Set res to x^e \bmod f, given finv. They use sliding-window exponentiation in which a multiplication by x^w is a shift followed by a reduction, so each window costs one reduction instead of a full multiplication. The underscore versions require \mathit{lenf} \ge 3 and e \ge 1 and write \mathit{lenf} - 1 coefficients; the non-underscore versions accept e \ge 0 and any nonzero f.

Set res[i] to f^i \bmod g for 0 \le i < n, computing f^i as f^{\lfloor i/2 \rfloor} f^{\lceil i/2 \rceil}. The non-underscore version takes an array of n initialised polynomials, reduces f first, and throws FLINT_ERROR for g = 0; for f = 0 or constant g it sets res[0] to 1 and the others to 0. The underscore version requires 1 \le \mathit{flen} < \mathit{glen}, ginv as for _nmod_poly_mulmod_preinv, and n arrays of \mathit{glen} - 1 coefficients, all of which are written.

The same as the naive functions, computed with baby steps and giant steps in parallel: with k = \lfloor \sqrt{n} \rfloor, the powers f^0, \ldots, f^k and f^{2k}, f^{3k}, \ldots are computed first, and then the threads fill in f^{ik + j} = f^{ik} f^j, taking blocks of k powers from a shared counter. _nmod_poly_powers_mod_preinv_threaded and nmod_poly_powers_mod_bsgs take their threads from the global pool (see thread_pool.h), the _pool version uses the num_threads threads given.

Initialise precond for multiplication by a modulo d with the given method. Require a reduced modulo d (\mathit{alen} < \mathit{dlen}) and dinv the power series inverse of the reversal of d, as for nmod_poly_mulmod_preinv; the matrix method only reads dinv[0]. An invalid method throws FLINT_ERROR.

Like the init_method functions, but choose the method expected to be fastest for num multiplications.

Frees the memory used by precond.

Set res to ab \bmod d for the a and d of precond. Require b reduced modulo d. The underscore version requires \mathit{alen}, \mathit{blen} \ge 1, writes \deg d coefficients (zero-padded) and does not allow res to overlap b, a or d. The non-underscore version allows res to be b, but not a.

Set G to a greatest common divisor of A and B. The underscore version requires \mathit{lenA} \ge \mathit{lenB} \ge 1, writes at most \mathit{lenB} coefficients, returns the length of G, does not make G monic and does not allow aliasing.

The GCD by the Euclidean algorithm, with the conventions of _nmod_poly_gcd and nmod_poly_gcd. Each step is a call to _nmod_poly_rem, so the cost is O(\mathit{lenA} \cdot \mathit{lenB}).

The Euclidean algorithm in Montgomery arithmetic (nmod_redc_fast, see nmod.h), after a first remainder in the ordinary representation. Require an odd prime modulus n < 2^{\mathtt{FLINT\_BITS} - 2}, which is not checked.

The GCD by the half-GCD algorithm, with the conventions of _nmod_poly_gcd and nmod_poly_gcd. Its complexity is O(M(n) \log n), where M(n) is the cost of a multiplication of length n.

The half-GCD step. For \deg a > \deg b, compute consecutive remainders A, B of the Euclidean remainder sequence of a, b with \deg A \ge \deg(a)/2 > \deg B and the matrix

the product of the matrices \left(\begin{smallmatrix} q_i & 1 \\ 1 & 0 \end{smallmatrix}\right) for the quotients q_i of these steps. Return \det M = \pm 1.

A reference implementation of nmod_poly_hgcd by repeated division with remainder, for testing. Same contract; no aliasing is allowed.

Return the tuned cutoffs for the bit size of the modulus: the length below which the half-GCD recursion uses Euclidean steps (60 to 244), the length below which the outer loop of the half-GCD GCD switches to the Euclidean algorithm (310 to 1585), and the length of B from which _nmod_poly_gcd (470 to 2199) and _nmod_poly_xgcd (72 to 388) use the half-GCD algorithm.

Compute the GCD G of A and B and cofactors S, T with SA + TB = G. The non-underscore version makes G monic; for B \ne 0 the cofactors satisfy \deg S < \max(\deg B - \deg G, 1) and \deg T < \max(\deg A - \deg G, 1), and for B = 0 it returns S = \operatorname{lc}(A)^{-1}, T = 0. G, S and T must be distinct objects.

The extended GCD by the Euclidean and by the half-GCD algorithm, with the conventions of _nmod_poly_xgcd and nmod_poly_xgcd.

Compute G = \gcd(A, B) and S with G \equiv SA \pmod B and \deg S < \deg B - \deg G, without the cofactor of B. If \gcd(A, B) = 1, then S = A^{-1} \bmod B. The non-underscore version requires \mathit{lenB} \ge 2 (otherwise it throws FLINT_ERROR), reduces A modulo B first, makes G monic and returns G = S = 0 if B divides A. The underscore version requires 1 \le \mathit{lenA} < \mathit{lenB}, writes at most lenA coefficients to G and \mathit{lenB} - 1 to S, returns the length of G and does not make G monic.

Return \operatorname{res}(f, g). The underscore version requires \mathit{len1} \ge \mathit{len2} \ge 1.

The resultant by the Euclidean algorithm, using \operatorname{res}(f, g) = (-1)^{\deg f \deg g} \operatorname{lc}(g)^{\deg f - \deg r} \operatorname{res}(g, r) for r = f \bmod g.

The resultant by the half-GCD algorithm, in O(M(n) \log n) operations.

Return the discriminant of f of degree d,

where the power of \operatorname{lc}(f) is adjusted if \deg f' < d - 1 (when the characteristic divides d). The discriminant is 0 for constants and when f' = 0. The underscore version requires \mathit{len} \ge 2.

Set x_prime to the derivative of x. The underscore version requires \mathit{len} \ge 1, writes \mathit{len} - 1 coefficients and allows x_prime == x.

Set x_int to the integral of x with constant term 0. The integers 1, \ldots, \deg x + 1 must be invertible modulo n, for example n prime and n > \deg x + 1; otherwise FLINT_IMPINV is thrown. Here len is the length of the output: the underscore version reads \mathit{len} - 1 coefficients, writes len coefficients, requires \mathit{len} \ge 1 and allows x_int == x. It needs only one modular inversion.

Return \mathit{poly}(c) for reduced c. Any length, including 0, is allowed.

Return \mathit{poly}(c) by Horner's rule, and by rectangular splitting: with m = \min(\lfloor\sqrt{\mathit{len}}\rfloor + 1, 1024), the powers c, \ldots, c^m are computed once, each block of m coefficients is evaluated by a dot product (see Computing dot products), and the blocks are combined by Horner's rule in c^m. The dot products accumulate without intermediate reductions, which makes rectangular splitting faster than Horner's rule for long polynomials although it does the same number of multiplications.

Evaluate poly at c modulo modn by Horner's rule with Shoup multiplication, given c_precomp = n_mulmod_precomp_shoup(c, modn). Require c < \mathit{modn} < 2^{\mathtt{FLINT\_BITS} - 1}.

Set dest to the matrix \mathit{poly}(c), for a square matrix c with the modulus of poly; dest must have the same dimensions and may be c. The Horner version uses \deg(\mathit{poly}) matrix multiplications, the Paterson–Stockmeyer version [PS1973] about 2\sqrt{\deg} matrix multiplications and O(\deg) scalar multiply-adds. nmod_poly_evaluate_mat uses Horner's rule if \mathit{len} < 5 or \mathit{len} \cdot r < 425 for an r \times r matrix, and Paterson–Stockmeyer otherwise.

Sets dest to \mathit{mat} + cI for a square matrix mat and reduced c, the step of Horner's rule above. dest may be mat.

Set ys[i] to \mathit{poly}(\mathit{xs}[i]) for 0 \le i < \mathit{olen}, for reduced points. Polynomials of length less than 32 are evaluated point by point with _nmod_poly_evaluate_nmod, longer ones with a subproduct tree.

The same, evaluating at each point with _nmod_poly_evaluate_nmod.

The same with a temporary subproduct tree.

Evaluates (poly, ilen) at the olen points of the subproduct tree tree, built with _nmod_poly_tree_build. The polynomial may be longer or shorter than the number of points; it is first reduced modulo the products at the highest useful level of the tree, and the remainders are then reduced down the tree.

Allocate and free a subproduct tree for len points. For len = 0, _nmod_poly_tree_alloc returns NULL.

Builds the subproduct tree of the monic linear factors x - r_i, 0 \le i < \mathit{len}, in the space allocated by _nmod_poly_tree_alloc.

Sets w[i] to the barycentric weight 1 / \prod_{j \ne i} (x_i - x_j) = 1 / P'(x_i), where P = \prod_j (x - x_j) for the points of tree.

Sets (poly, len) to the polynomial of length at most len taking the values ys at the points of tree, given the weights from _nmod_poly_interpolation_weights, by combining the scaled values y_i w_i up the tree (fast Lagrange interpolation). Writes len coefficients.

Set poly to the unique polynomial of length at most len with \mathit{poly}(x_i) = y_i for 0 \le i < \mathit{len}. The points must be distinct and all values reduced. Uses the Newton form for \mathit{len} < 6, the barycentric form for \mathit{len} < 16 and fast interpolation otherwise. The underscore version requires \mathit{len} \ge 1, writes len coefficients and does not allow poly to overlap xs or ys.

The same by fast Lagrange interpolation with a temporary subproduct tree, in O(M(\mathit{len}) \log \mathit{len}) operations.

The same by divided differences, followed by a conversion from the Newton basis to the monomial basis. It uses O(\mathit{len}^2) multiplications and O(\mathit{len}^2) modular inversions.

The same by the Lagrange formula \sum_i y_i w_i P(x)/(x - x_i), with P = \prod (x - x_i) and w_i as above, in O(\mathit{len}^2) multiplications and len inversions.

Set poly to \prod_{i=0}^{n-1} (x - x_i), for reduced x_i. The underscore version writes n + 1 coefficients and does not allow aliasing. Uses the quadratic algorithm for n < 20 and balanced products above.

Initialise G for the points 1, r^2, \ldots, r^{2(\mathit{len}-1)}. len must be at least the number of points and at least the length of the polynomials used. nmod_geometric_progression_init prepares evaluation, interpolation and extrapolation; the second function only the functionalities selected by the bits of function: bit 0 evaluation, bit 1 interpolation, bit 2 extrapolation, and bit 3 stored transforms.

Stores the fft_small transforms described above for the functionalities of G, with a separate bound, at most G->len, for each: evaluation of polynomials of length at most ev_len, interpolation from at most int_len points, and extrapolation from at most ext_len values. A bound 0 removes the stored transforms of the functionality and a negative bound keeps them unchanged. Smaller bounds give shorter transforms for evaluation (\mathit{ev\_len} + \mathit{len} - 1 instead of 2 \mathit{len} - 1) and interpolation (about 2\,\mathit{int\_len}), and may need fewer primes; the extrapolation transforms have length \mathit{len} - 1 whatever ext_len, which only bounds the number of primes. Longer inputs remain possible without the stored transforms. Must not be called while other threads use G.

Frees the memory used by G.

Sets vs[i] to \mathit{poly}(r^{2i}) for 0 \le i < \mathit{olen}, using G prepared for evaluation. Requires \mathit{ilen}, \mathit{olen} \le G->len.

The same with a temporary precomputation for evaluation.

The same by evaluating at each point with _nmod_poly_evaluate_nmod. No condition on r.

Set poly to the polynomial of length at most len taking the values v[i] at r^{2i}, 0 \le i < \mathit{len}, using G prepared for interpolation. Requires 1 \le \mathit{len} \le G->len. The underscore version writes len coefficients and does not allow poly to overlap v.

The same with a temporary precomputation for interpolation.

Given the values ival of a polynomial f of degree less than \mathit{ilen} at ilen consecutive points of the progression, compute its values oval at olen consecutive points starting offset positions later, without computing f. The points must not overlap: \mathit{offset} \ge \mathit{ilen} (forward) or \mathit{offset} + \mathit{olen} \le 0 (backward).

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

The composition by Horner's rule, with the conventions of _nmod_poly_compose.

Set g(x) = f(x + c), for reduced c; the underscore version works in place on (poly, len). Uses Horner's rule for \mathit{len} < 100 or \mathit{len} > n, and for c = \pm 1 and \mathit{len} < 1000, and the convolution method otherwise, which requires (\mathit{len} - 1)! to be invertible modulo n (for prime n, guaranteed by \mathit{len} \le n); otherwise FLINT_IMPINV is thrown.

The Taylor shift by Horner's rule, with O(\mathit{len}^2) additions and multiplications. Works for every modulus.

The Taylor shift as one product of length len, using \sum_k f_k (x + c)^k = \sum_j \frac{x^j}{j!} \sum_k k!\, f_k \frac{c^{k-j}}{(k-j)!} [ASU1975] [GG1997], in O(M(\mathit{len})) operations. Requires (\mathit{len} - 1)! to be invertible modulo n.

Set res to f(g) \bmod h. The non-underscore version accepts any f and g and throws FLINT_DIVZERO for h = 0. The underscore version requires \mathit{lenh} \ge 2, \mathit{lenf} \ge 1 and g reduced and zero-padded to length \mathit{lenh} - 1, writes \mathit{lenh} - 1 coefficients and does not allow aliasing. It uses Horner's rule if \mathit{lenh} < 8 or \mathit{lenf} \ge \mathit{lenh}, and the Brent–Kung algorithm otherwise.

Modular composition by Horner's rule, with \mathit{lenf} - 1 multiplications modulo h, and the conventions of _nmod_poly_compose_mod.

Modular composition by the Brent–Kung algorithm, with the conventions of _nmod_poly_compose_mod. Requires \mathit{lenf} < \mathit{lenh} (\deg f < \deg h); the non-underscore version throws FLINT_ERROR otherwise.

Set res to \mathit{poly1}(\mathit{poly2}) \bmod \mathit{poly3} by the Brent–Kung algorithm, given the inverse poly3inv of the reversal of poly3 as for nmod_poly_mulmod_preinv. Requires \mathit{len1} < \mathit{len3}; the underscore version also requires poly2 reduced and zero-padded to length \mathit{len3} - 1.

Set the rows of the m \times n matrix A to \mathit{poly1}^i \bmod \mathit{poly2} for 0 \le i < m, where n = \deg \mathit{poly2} and m = \lfloor \sqrt{n} \rfloor + 1, given the inverse poly2inv of the reversal of poly2. A must be initialised with these dimensions (the non-underscore version throws FLINT_ERROR otherwise). The underscore version requires poly1 reduced and zero-padded to length n.

Set res to \mathit{poly1}(g) \bmod \mathit{poly3}, where A is the matrix computed by nmod_poly_precompute_matrix for g and poly3. Requires \mathit{len1} < \mathit{len3}. This is the function to use for many compositions with the same g and modulus, as in the computation of Frobenius powers in polynomial factorisation [GatSho1992] [KalSho1998].

Initialises A as an m \times n matrix, n = \deg f, m = \lfloor \sqrt n \rfloor + 1, and sets row 0 to 1 and row i to row i of B reduced modulo f for 1 \le i < m. A must not be initialised before the call; B needs at least m rows and at least \deg f + 1 columns.

Sets (res, n) to \sum_{i} A_i h^i \bmod \mathit{poly3}, where A_i is row i of the d \times n matrix A, h has length n and \mathit{len3} = n + 1. This is the last step of the Brent–Kung algorithm, with h = g^m; it uses Horner's rule for d \le 10 and rectangular splitting otherwise.

Set res to \mathit{poly1}(\mathit{poly2}) \bmod x^n, where poly2 must have constant term 0 (the non-underscore version throws FLINT_ERROR otherwise). The underscore version requires 0 < \mathit{len1}, \mathit{len2} \le n, writes n coefficients and does not allow aliasing.

Set Qinv to the compositional inverse of the power series Q modulo x^n, so that Q(\mathit{Qinv}(x)) = \mathit{Qinv}(Q(x)) = x \bmod x^n. Requires Q_0 = 0 and Q_1 invertible; the non-underscore version throws FLINT_ERROR otherwise. The underscore version writes n coefficients and does not allow aliasing.

Set g to \sqrt{h} and 1/\sqrt{h} modulo x^n. The constant term of h must be a nonzero square modulo a prime n \ne 2 (it is usually 1), and its square root is chosen by nmod_sqrt; otherwise an exception is thrown. The underscore versions require \mathit{hlen}, n \ge 1, write n coefficients and do not allow aliasing.

If a is the square of a polynomial, set b to a square root and return 1; otherwise return 0 (and set b = 0). Requires a prime modulus. The underscore version requires \mathit{len} \ge 1, writes \mathit{len} / 2 + 1 coefficients and does not allow aliasing.

Set res to \sum_{k=0}^{n-1} p_k x^k. The non-underscore version accepts any nonzero poly with invertible leading coefficient (throwing FLINT_ERROR for zero) and handles factors x^k. The underscore version requires poly monic and writes n coefficients. Uses Newton's identities for 10 n < \mathit{len} + 75 and the series formula otherwise.

The power sums by Newton's identities, in O(n \cdot \mathit{len}) operations, and by the series formula with one power series division, in O(M(n)) operations. The underscore versions require poly monic.

Set res to the monic polynomial of degree d = Q_0 whose power sum series is Q (modulo x^{\mathit{len}}, the higher power sums being determined by d of them). Requires 1, \ldots, d invertible modulo n. For Q = 0 the result is 1. The underscore version writes d + 1 coefficients. Uses Newton's identities if n \le 12 or d \le 10 and the exponential formula \tilde f = \exp(\int (d - Q)/x) otherwise.

The same by Newton's identities, in O(d^2) operations, and by the exponential formula, in O(M(d)) operations.

Set f = \exp(h) \bmod x^n.

Sets f = \exp(h) and g = \exp(-h) = 1/f modulo x^n, currently by _nmod_poly_exp_series followed by _nmod_poly_inv_series. Requires \mathit{hlen} \le n and does not allow aliasing.