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.