padic_poly.h

Initialise poly to zero, with precision PADIC_DEFAULT_PREC (that is, 20) and no allocated coefficients, respectively with precision prec and space for alloc coefficients.

Clears poly.

Reallocates poly to have space for exactly alloc coefficients. If the length is larger, the polynomial is first truncated and canonicalised with respect to $p$. With alloc $= 0$ the polynomial is cleared and reinitialised, which also resets its precision to PADIC_DEFAULT_PREC.

Ensures that poly has space for at least len coefficients, at least doubling the allocation when it grows. The value is not changed.

Sets the length to len, first zeroing (and freeing) the coefficients beyond len. The result may not be normalised or canonical.

Decreases the length until the leading coefficient is nonzero.

Bring a normalised polynomial into canonical form by dividing $f$ by the largest power of $p$ dividing all its coefficients and adding the exponent to $v$; set $v = 0$ for the zero polynomial. No reduction is done.

Reduces the canonical poly modulo $p^N$: reduces the coefficients modulo $p^{N - v}$ and normalises, or sets poly to zero if $v \ge N$.

Truncates poly to length at most $n$ and brings it into canonical form. A reduced input gives a reduced output.

Return the degree ($-1$ for zero) and the length of poly.

Returns the valuation $v$, which for a canonical polynomial is the minimum valuation of its coefficients (0 for the zero polynomial). The name is also defined as a macro, so padic_poly_val(poly) can be assigned to.

Sets $f$ to a random reduced polynomial of length at most len, with valuation drawn as for padic_randtest. With len $= 0$, $f$ is not changed.

Sets $f$ to a random nonzero reduced polynomial of length at most len. Throws if len is zero.

Sets $f$ to a random reduced polynomial of length at most len with valuation val, or to zero if val $\ge N$. With len $= 0$, $f$ is not changed.

Sets poly1 to poly2.

Sets poly to the constant polynomial $x$.

Set poly to the constant polynomial $x$.

Set rop to the integer or rational polynomial op. For a rational polynomial the power of $p$ in the common denominator becomes a negative valuation and the rest of the denominator is inverted modulo $p^{N - v}$.

If $v \ge 0$, sets rop to the integer polynomial $p^v f$ and returns

1. Otherwise returns 0 and leaves rop unchanged.

Sets rop to the rational polynomial $p^v f$.

Sets poly to zero.

Sets poly to 1, or to zero if its precision is not positive.

Swaps poly1 and poly2, including their precisions, in constant time.

Sets $c$ to the coefficient of $x^n$, which is zero for $n$ beyond the length, reduced to the precision of $c$ (which is not changed).

Sets the coefficient of $x^n$ to $c$, reduced to the precision of poly. If $c$ has smaller valuation than poly, all coefficients are rescaled, so the cost can be linear in the length. The result is normalised: setting the leading coefficient to zero (or to an element of valuation at least the precision of poly) reduces the length.

Returns whether the stored values are equal, that is, whether the valuations, lengths and coefficients agree. The precisions are not compared.

Return whether poly is zero, respectively the constant 1.

Set (rop, *rval) of length $\max(len_1, len_2)$ to the sum, respectively difference, of the two polynomials, reduced modulo $p^N$ but not normalised. The input precisions $N_1, N_2$ are ignored. Allow rop to be equal to op1 or op2, provided it has space for $\max(len_1, len_2)$ coefficients.

Set $f$ to $g + h$, respectively $g - h$.

Sets $f$ to $-g$.

Sets (rop, *rval, len) to (op, val, len) times $c$, reduced modulo $p^N$. If $c = 0$ or the valuation of the product is at least $N$, the array is zeroed and *rval set to 0. Requires a nonzero polynomial for the result to be canonical.

Sets rop to $c \cdot op$.

Sets (rop, *rval, len1 + len2 - 1) to the product, reduced modulo $p^N$. Requires $len_1 \ge len_2 \ge 1$ and $val_1 + val_2 < N$. Does not allow aliasing.

Sets res to the product of poly1 and poly2.

Sets (rop, *rval, e(len - 1) + 1) to (op, val, len) raised to the power $e$, reduced modulo $p^N$. Requires $e \ge 2$, $len \ge 1$ and $e \cdot val < N$. Does not allow aliasing.

Sets rop to $op^e$, with $op^0 = 1$. The power is computed in $(\mathbb{Z}/p^{N - ev}\mathbb{Z})[x]$ by _fmpz_mod_poly_pow.

Sets $g$ to the power series inverse of $f$ modulo $x^n$, $n \ge 1$, reduced to the precision of $g$. The constant coefficient of $f$ must have the minimal valuation of all coefficients, that is, the constant coefficient of the stored integer polynomial must be a $p$-adic unit; otherwise, and if it is zero, the function throws. If $-v \ge N$ the result is zero.

Sets (rop, *rval, len - 1) to the derivative of (op, val, len), reduced modulo $p^N$ and canonicalised. Allows aliasing.

Sets rop to the derivative of op.

Sets rop to $x^n \cdot op$, $n \ge 0$. Throws if the precision of rop is smaller than that of op. No reduction is done for $n > 0$.

Sets rop to the quotient of op by $x^n$, $n \ge 0$, discarding the coefficients of $x^0, \ldots, x^{n-1}$, and canonicalises the result. For $n > 0$ no reduction is done, so the result is reduced only if the precision of rop is at least that of op.

Set $y = p^v u$ to the value of poly at $a = p^b a'$, reduced modulo $p^N$ (the precision of $y$). padic_poly_evaluate_padic allows $y$ to be the same object as $a$.

Sets (rop, *rval, (len1 - 1)(len2 - 1) + 1) to the composition $f(g(x))$ of $f$ = op1 and $g$ = op2, reduced modulo $p^N$ and canonicalised. Requires $len_1 \ge 1$. Does not allow aliasing.

Sets rop to $op_1(op_2(x))$. The composition is computed in $(\mathbb{Z}/p^M\mathbb{Z})[x]$ by _fmpz_mod_poly_compose, after scaling the coefficients so that they are integral, as for evaluation.

Sets (rop, *rval, (len - 1)k + 1) to $f(x^k)$ for $f$ = (op, val, len), $k \ge 1$, $len \ge 1$. Only the length-one case is reduced modulo $p^N$. Allows aliasing.

Sets rop to $op(x^k)$, $k \ge 1$. The coefficients are moved, not reduced, so the result is reduced only if the precision of rop is at least that of op.

Print the polynomial as its length, two spaces and the coefficients separated by spaces, each in the printing mode of the context (all three modes are supported); the zero polynomial prints as 0. Return 1.

Print the polynomial as a sum of terms in the variable var, highest degree first, each nonconstant coefficient in parentheses. The underscore versions take len, val in the opposite order to _padic_poly_fprint. Return 1.

Prints the raw fields alloc, length, val, N and all allocated coefficients. Returns 1.

Return whether the polynomial is in canonical form.

Return whether the polynomial is reduced modulo $p^N$: canonical, with $v < N$ (or zero) and all coefficients in $[0, p^{N - v})$.

Returns the minimum $p$-adic valuation of the nonzero entries of (vec, len), or 0 if all entries are zero or len is zero.