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.