qadic.h

Initialises ctx for the extension of degree $d \ge 1$ of $\mathbf{Q}_p$, with powers $p^e$ for $\mathtt{min} \le e < \mathtt{max}$ precomputed, generator name var and printing mode mode. The defining polynomial is the Conway polynomial for $(p, d)$ if the database contains it, otherwise for word-size $p$ the polynomial of nmod_poly_minimal_irreducible (a binomial, trinomial, tetranomial or pentanomial), and otherwise a random sparse irreducible polynomial. The prime $p$ is not checked.

Like qadic_ctx_init but always uses the Conway polynomial, and throws if $p > 109987$ or the database has no Conway polynomial for $(p, d)$.

Initialises ctx with the Conway polynomial for $(p, d)$ and returns 1, or returns 0 without initialising ctx if the database does not contain it.

Initialise ctx with the given defining polynomial, which must be monic and irreducible over $\mathbf{F}_p$ (not checked). Its coefficients, taken in $[0, p)$, define $f$; only the nonzero ones are stored.

Clears ctx.

Returns the degree $d$ of the extension.

Prints $p$, $d$ and $f$ to stdout.

Initialise rop to zero with precision PADIC_DEFAULT_PREC, respectively prec.

Clears rop.

Reduces (R, lenR) in place modulo the sparse monic polynomial $f = \sum_k a_k X^{j_k}$ of degree $d = j_{\mathtt{len} - 1}$, setting the coefficients of degree at least $d$ to zero. The array $j$ must be increasing; (R, lenR) may have leading zeros.

Like _fmpz_poly_reduce, followed by reduction of the remaining coefficients modulo $p$ (typically a prime power) into $[0, p)$.

Reduces rop modulo $f$ and $p^{N - v}$ and canonicalises it, or sets it to zero if $v \ge N$.

Return the valuation $v$ and the precision $N$ of op.

Set rop to a random reduced element, respectively a random nonzero one, with valuation drawn as for padic_randtest.

Sets rop to a random reduced element of valuation $v$, which is zero if $v \ge N$.

Sets rop to a random reduced element of $\mathbf{Z}_q$, with valuation in $[0, N)$, or to zero if $N \le 0$.

Sets rop to op, reduced to the precision of rop.

Set rop to 0, respectively 1 (or 0 if the precision is not positive).

Sets rop to the generator $X$, or to zero if its precision is not positive. For $d = 1$ it sets rop to the root $-a_0$ of $f$, reduced modulo $p^N$.

Sets rop to the integer op, reduced.

Sets rop to the image of the integer polynomial op in $\mathbf{Q}_q$, reduced modulo $f$ and $p^N$.

If op lies in $\mathbf{Q}_p$, that is, has length at most 1, sets rop to its value and returns 1; otherwise returns 0. The value is canonicalised but not reduced to the precision of rop.

Return whether op is 0, respectively 1.

Returns whether the stored values are equal; the precisions are not compared.

Set rop to $op_1 + op_2$, $op_1 - op_2$ and $-op$, reduced. These are the corresponding padic_poly functions.

Sets rop to $op_1 \, op_2$, reduced: the integer polynomials are multiplied in $\mathbb{Z}[X]$ and the product is reduced modulo $f$ and $p^{N - v_1 - v_2}$ (Multiplication and reduction).

Sets (rop, d) to the inverse of the unit (op, len) modulo $f$ and $p^N$, for $1 \le len \le d$ and $N \ge 1$, by Newton iteration from the inverse modulo $p$. Does not allow aliasing.

Sets rop to $1/op$, reduced, or to zero if $N + v \le 0$. Throws if op is zero.

Sets (rop, 2d - 1) to (op, len) raised to the power $e \ge 0$, reduced modulo $f$ and the integer $p$ (typically a prime power); only the first $d$ coefficients can be nonzero. Requires $1 \le len \le d$. Does not allow aliasing.

Sets rop to $op^e$, reduced, with $op^0 = 1$. Throws if $e < 0$. Assumes that $e \cdot v$ fits in a slong.

Returns whether op is a square in $\mathbf{Q}_q$, and if so sets rop to a square root, reduced. If the valuation of the root is at least the precision of rop, rop is set to zero and squareness is decided from the residue of the unit (modulo $p$, or modulo 8 for $p = 2$); if op has no digits of precision left, 1 is returned.

For $p = 2$, precompute the LUP decomposition of the matrix of the Artin–Schreier map $Y \mapsto Y^2 + Y$ on $\mathbf{F}_q$, compute square roots as qadic_sqrt using it, and free it. The structure is opaque. The first two functions throw if $p \ne 2$.

Set (rop, 2d - 1) to the exponential of the nonzero element (op, v, len) modulo $p^N$, where pN is $p^N$, assuming that the series converges and $v < N$. Do not allow aliasing. _qadic_exp uses rectangular splitting for $N < 8192/b$, where $b$ is the bit length of $p$, and the balanced algorithm otherwise.

Sets (rop, d) to the exponential of (x, v, len) modulo $p^N$ by the balanced (bit-burst) algorithm, assuming convergence and $v < N$. Requires $1 \le len \le d$; the input may be zero. Allows aliasing.

Return whether the exponential series converges at op, that is, whether op is zero or has valuation at least 1 (odd $p$) or 2 ($p = 2$), and if so set rop to $\exp(op)$, reduced.

Set (z, d) to

for a nonzero $y$ reduced modulo $p^N$, of valuation $v$ with $1 \le v < N$. The array $z$ must have space for $2d - 1$ coefficients. _qadic_log_rectangular allows aliasing between $y$ and $z$, _qadic_log_balanced does not. _qadic_log uses rectangular splitting for $N < 1024/b$, where $b$ is the bit length of $p$, and the balanced algorithm otherwise.

If $\operatorname{ord}_p(op - 1) \ge 1$ (for every $p$, including $p = 2$), set rop to $\log(op)$, reduced, and return 1; otherwise, in particular for $op = 0$, return 0.

Sets (rop, 2d - 1) to $\Sigma^e(X)$ modulo $p^N$, where $\Sigma$ is the Frobenius automorphism; only the first $d$ coefficients can be nonzero. Requires $d \ge 2$, $N \ge 2$ and $0 < e < d$.

Sets (rop, 2d - 1) to $\Sigma^e$ applied to (op, len), modulo $p^N$, for $1 \le len \le d$ and $0 < e < d$. Does not allow aliasing.

Sets rop to $\Sigma^e(op)$, reduced, for any integer $e$, which is taken modulo $d$. $\Sigma$ is the automorphism of $\mathbf{Q}_q$ that reduces to $x \mapsto x^p$ on $\mathbf{F}_q$; it generates the Galois group, which is cyclic of order $d$.

Sets (rop, d) to the Teichmüller lift of the unit (op, len) modulo $p^N$, for $N \ge 1$. Allows aliasing.

Sets rop to the Teichmüller lift of op: the unique $(q - 1)$-th root of unity congruent to op modulo $p$, reduced. Sets rop to zero if op is zero or divisible by $p$, or if the precision of rop is not positive. Throws if op has negative valuation.

Set rop to the trace of op over $\mathbf{Q}_p$, reduced modulo pN, respectively to the precision of rop. The trace is computed from the power sums of the roots of $f$ by Newton's identities.

Sets rop to the norm of the unit (op, len), $len \ge 1$, reduced modulo $p^N$; the result is a unit. Chooses between the analytic and the resultant method.

Set rop to the norm of op over $\mathbf{Q}_p$, reduced to the precision of rop. The analytic version computes $\exp(\operatorname{Tr}(\log u))$ for the unit part $u$ and throws unless $u \equiv 1 \pmod p$ ($\bmod 4$ for $p = 2$) or $u \in \mathbf{Q}_p$; the resultant version computes $\operatorname{Res}(f, u)$ as a determinant modulo $p^N$; qadic_norm chooses.

Print op as a polynomial in the generator, in the printing mode of the context: in PADIC_TERSE mode as a polynomial with rational coefficients, in PADIC_SERIES mode as a sum of polynomials with coefficients in $[0, p)$ times powers of $p$ (throws if a coefficient is negative), and in PADIC_VAL_UNIT mode as (g)*p^v. Return 1.

Prints the raw fields of op, as padic_poly_debug. Returns 1.