Data structures¶

We represent an element of the extension $$\mathbf{Q}_q \cong \mathbf{Q}_p[X] / (f(X))$$ as a polynomial in $$\mathbf{Q}_p[X]$$ of degree less than $$\deg(f)$$. As such, qadic_struct and qadic_t are typedef’ed as padic_poly_struct and padic_poly_t.

Context¶

We represent an unramified extension of $$\mathbf{Q}_p$$ via $$\mathbf{Q}_q \cong \mathbf{Q}_p[X] / (f(X))$$, where $$f \in \mathbf{Q}_p[X]$$ is a monic, irreducible polynomial which we assume to actually be in $$\mathbf{Z}[X]$$. The first field in the context structure is a $$p$$-adic context struct pctx, which contains data about the prime $$p$$, precomputed powers, the printing mode etc. The polynomial $$f$$ is represented as a sparse polynomial using two arrays $$j$$ and $$a$$ of length len, where $$f(X) = \sum_{i} a_{i} X^{j_{i}}$$. We also assume that the array $$j$$ is sorted in ascending order. We choose this data structure to improve reduction modulo $$f(X)$$ in $$\mathbf{Q}_p[X]$$, assuming a sparse polynomial $$f(X)$$ is chosen. The field var contains the name of a generator of the extension, which is used when printing the elements.

void qadic_ctx_init(qadic_ctx_t ctx, const fmpz_t p, slong d, slong min, slong max, const char *var, enum padic_print_mode mode)

Initialises the context ctx with prime $$p$$, extension degree $$d$$, variable name var and printing mode mode. The defining polynomial is chosen as a Conway polynomial if possible and otherwise as a random sparse polynomial.

Stores powers of $$p$$ with exponents between min (inclusive) and max exclusive. Assumes that min is at most max.

Assumes that $$p$$ is a prime.

Assumes that the string var is a null-terminated string of length at least one.

This function also carries out some relevant precomputation for arithmetic in $$\mathbf{Q}_p / (p^N)$$ such as powers of $$p$$ close to $$p^N$$.

void qadic_ctx_init_conway(qadic_ctx_t ctx, const fmpz_t p, slong d, slong min, slong max, const char *var, enum padic_print_mode mode)

Initialises the context ctx with prime $$p$$, extension degree $$d$$, variable name var and printing mode mode. The defining polynomial is chosen as a Conway polynomial, hence has restrictions on the prime and the degree.

Stores powers of $$p$$ with exponents between min (inclusive) and max exclusive. Assumes that min is at most max.

Assumes that $$p$$ is a prime.

Assumes that the string var is a null-terminated string of length at least one.

This function also carries out some relevant precomputation for arithmetic in $$\mathbf{Q}_p / (p^N)$$ such as powers of $$p$$ close to $$p^N$$.

Clears all memory that has been allocated as part of the context.

Returns the extension degree.

Prints the data from the given context.

Memory management¶

Initialises the element rop, setting its value to $$0$$.

Initialises the element rop with the given output precision, setting the value to $$0$$.

Clears the element rop.

void _fmpz_poly_reduce(fmpz *R, slong lenR, const fmpz *a, const slong *j, slong len)

Reduces a polynomial (R, lenR) modulo a sparse monic polynomial $$f(X) = \sum_{i} a_{i} X^{j_{i}}$$ of degree at least $$2$$.

Assumes that the array $$j$$ of positive length len is sorted in ascending order.

void _fmpz_mod_poly_reduce(fmpz *R, slong lenR, const fmpz *a, const slong *j, slong len, const fmpz_t p)

Reduces a polynomial (R, lenR) modulo a sparse monic polynomial $$f(X) = \sum_{i} a_{i} X^{j_{i}}$$ of degree at least $$2$$ in $$\mathbf{Z}/(p)$$, where $$p$$ is typically a prime power.

Assumes that the array $$j$$ of positive length len is sorted in ascending order.

Reduces rop modulo $$f(X)$$ and $$p^N$$.

Properties¶

Returns the valuation of op.

Returns the precision of op.

Randomisation¶

Generates a random element of $$\mathbf{Q}_q$$.

Generates a random non-zero element of $$\mathbf{Q}_q$$.

Generates a random element of $$\mathbf{Q}_q$$ with prescribed valuation val.

Note that if $$v \geq N$$ then the element is necessarily zero.

Generates a random element of $$\mathbf{Q}_q$$ with non-negative valuation.

Assignments and conversions¶

Sets rop to op.

Sets rop to zero.

Sets rop to one, reduced in the given context.

Note that if the precision $$N$$ is non-positive then rop is actually set to zero.

Sets rop to the generator $$X$$ for the extension when $$N > 0$$, and zero otherwise. If the extension degree is one, raises an abort signal.

Sets rop to the integer op, reduced in the context.

If the element op lies in $$\mathbf{Q}_p$$, sets rop to its value and returns $$1$$; otherwise, returns $$0$$.

Comparison¶

Returns whether op is equal to zero.

Returns whether op is equal to one in the given context.

Returns whether op1 and op2 are equal.

Basic arithmetic¶

Sets rop to the sum of op1 and op2.

Assumes that both op1 and op2 are reduced in the given context and ensures that rop is, too.

Sets rop to the difference of op1 and op2.

Assumes that both op1 and op2 are reduced in the given context and ensures that rop is, too.

Sets rop to the negative of op.

Assumes that op is reduced in the given context and ensures that rop is, too.

Sets rop to the product of op1 and op2, reducing the output in the given context.

void _qadic_inv(fmpz *rop, const fmpz *op, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N)

Sets (rop, d) to the inverse of (op, len) modulo $$f(X)$$ given by (a,j,lena) and $$p^N$$.

Assumes that (op,len) has valuation $$0$$, that is, that it represents a $$p$$-adic unit.

Assumes that len is at most $$d$$.

Does not support aliasing.

Sets rop to the inverse of op, reduced in the given context.

void _qadic_pow(fmpz *rop, const fmpz *op, slong len, const fmpz_t e, const fmpz *a, const slong *j, slong lena, const fmpz_t p)

Sets (rop, 2*d-1) to (op,len) raised to the power $$e$$, reduced modulo $$f(X)$$ given by (a, j, lena) and $$p$$, which is expected to be a prime power.

Assumes that $$e \geq 0$$ and that len is positive and at most $$d$$.

Although we require that rop provides space for $$2d - 1$$ coefficients, the output will be reduces modulo $$f(X)$$, which is a polynomial of degree $$d$$.

Does not support aliasing.

Sets rop the op raised to the power $$e$$.

Currently assumes that $$e \geq 0$$.

Note that for any input op, rop is set to one in the given context whenever $$e = 0$$.

Special functions¶

void _qadic_exp_rectangular(fmpz *rop, const fmpz *op, slong v, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N, const fmpz_t pN)

Sets (rop, 2*d - 1) to the exponential of (op, v, len) reduced modulo $$p^N$$, assuming that the series converges.

Assumes that (op, v, len) is non-zero.

Does not support aliasing.

Returns whether the exponential series converges at op and sets rop to its value reduced modulo in the given context.

void _qadic_exp_balanced(fmpz *rop, const fmpz *x, slong v, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N, const fmpz_t pN)

Sets (rop, d) to the exponential of (op, v, len) reduced modulo $$p^N$$, assuming that the series converges.

Assumes that len is in $$[1,d)$$ but supports zero padding, including the special case when (op, len) is zero.

Supports aliasing between rop and op.

Returns whether the exponential series converges at op and sets rop to its value reduced modulo in the given context.

void _qadic_exp(fmpz *rop, const fmpz *op, slong v, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N)

Sets (rop, 2*d - 1) to the exponential of (op, v, len) reduced modulo $$p^N$$, assuming that the series converges.

Assumes that (op, v, len) is non-zero.

Does not support aliasing.

Returns whether the exponential series converges at op and sets rop to its value reduced modulo in the given context.

The exponential series converges if the valuation of op is at least $$2$$ or $$1$$ when $$p$$ is even or odd, respectively.

void _qadic_log_rectangular(fmpz *z, const fmpz *y, slong v, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N, const fmpz_t pN)

Computes

$z = - \sum_{i = 1}^{\infty} \frac{y^i}{i} \pmod{p^N}.$

Note that this can be used to compute the $$p$$-adic logarithm via the equation

$\begin{split}\log(x) & = \sum_{i=1}^{\infty} (-1)^{i-1} \frac{(x-1)^i}{i} \\ & = - \sum_{i=1}^{\infty} \frac{(1-x)^i}{i}.\end{split}$

Assumes that $$y = 1 - x$$ is non-zero and that $$v = \operatorname{ord}_p(y)$$ is at least $$1$$ when $$p$$ is odd and at least $$2$$ when $$p = 2$$ so that the series converges.

Assumes that $$y$$ is reduced modulo $$p^N$$.

Assumes that $$v < N$$, and in particular $$N \geq 2$$.

Supports aliasing between $$y$$ and $$z$$.

Returns whether the $$p$$-adic logarithm function converges at op, and if so sets rop to its value.

void _qadic_log_balanced(fmpz *z, const fmpz *y, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N, const fmpz_t pN)

Computes $$(z, d)$$ as

$z = - \sum_{i = 1}^{\infty} \frac{y^i}{i} \pmod{p^N}.$

Assumes that $$v = \operatorname{ord}_p(y)$$ is at least $$1$$ when $$p$$ is odd and at least $$2$$ when $$p = 2$$ so that the series converges.

Supports aliasing between $$z$$ and $$y$$.

Returns whether the $$p$$-adic logarithm function converges at op, and if so sets rop to its value.

void _qadic_log(fmpz *z, const fmpz *y, slong v, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N, const fmpz_t pN)

Computes $$(z, d)$$ as

$z = - \sum_{i = 1}^{\infty} \frac{y^i}{i} \pmod{p^N}.$

Note that this can be used to compute the $$p$$-adic logarithm via the equation

$\begin{split}\log(x) & = \sum_{i=1}^{\infty} (-1)^{i-1} \frac{(x-1)^i}{i} \\ & = - \sum_{i=1}^{\infty} \frac{(1-x)^i}{i}.\end{split}$

Assumes that $$y = 1 - x$$ is non-zero and that $$v = \operatorname{ord}_p(y)$$ is at least $$1$$ when $$p$$ is odd and at least $$2$$ when $$p = 2$$ so that the series converges.

Assumes that $$(y, d)$$ is reduced modulo $$p^N$$.

Assumes that $$v < N$$, and hence in particular $$N \geq 2$$.

Supports aliasing between $$z$$ and $$y$$.

Returns whether the $$p$$-adic logarithm function converges at op, and if so sets rop to its value.

The $$p$$-adic logarithm function is defined by the usual series

$\log_p(x) = \sum_{i=1}^{\infty} (-1)^{i-1} \frac{(x-1)^i}{i}$

but this only converges when $$\operatorname{ord}_p(x)$$ is at least $$2$$ or $$1$$ when $$p = 2$$ or $$p > 2$$, respectively.

void _qadic_frobenius_a(fmpz *rop, slong e, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N)

Computes $$\sigma^e(X) \bmod{p^N}$$ where $$X$$ is such that $$\mathbf{Q}_q \cong \mathbf{Q}_p[X]/(f(X))$$.

Assumes that the precision $$N$$ is at least $$2$$ and that the extension is non-trivial, i.e.$$d \geq 2$$.

Assumes that $$0 < e < d$$.

Sets (rop, 2*d-1), although the actual length of the output will be at most $$d$$.

void _qadic_frobenius(fmpz *rop, const fmpz *op, slong len, slong e, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N)

Sets (rop, 2*d-1) to $$\Sigma$$ evaluated at (op, len).

Assumes that len is positive but at most $$d$$.

Assumes that $$0 < e < d$$.

Does not support aliasing.

Evaluates the homomorphism $$\Sigma^e$$ at op.

Recall that $$\mathbf{Q}_q / \mathbf{Q}_p$$ is Galois with Galois group $$\langle \Sigma \rangle \cong \langle \sigma \rangle$$, which is also isomorphic to $$\mathbf{Z}/d\mathbf{Z}$$, where $$\sigma \in \operatorname{Gal}(\mathbf{F}_q/\mathbf{F}_p)$$ is the Frobenius element $$\sigma \colon x \mapsto x^p$$ and $$\Sigma$$ is its lift to $$\operatorname{Gal}(\mathbf{Q}_q/\mathbf{Q}_p)$$.

This functionality is implemented as GaloisImage() in Magma.

void _qadic_teichmuller(fmpz *rop, const fmpz *op, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N)

Sets (rop, d) to the Teichm”uller lift of (op, len) modulo $$p^N$$.

Does not support aliasing.

Sets rop to the Teichm”uller lift of op to the precision given in the context.

For a unit op, this is the unique $$(q-1)$$ modulo $$p$$.

Sets rop to zero if op is zero in the given context.

Raises an exception if the valuation of op is negative.

void _qadic_trace(fmpz_t rop, const fmpz *op, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t pN)

Sets rop to the trace of op.

For an element $$a \in \mathbf{Q}_q$$, multiplication by $$a$$ defines a $$\mathbf{Q}_p$$-linear map on $$\mathbf{Q}_q$$. We define the trace of $$a$$ as the trace of this map. Equivalently, if $$\Sigma$$ generates $$\operatorname{Gal}(\mathbf{Q}_q / \mathbf{Q}_p)$$ then the trace of $$a$$ is equal to $$\sum_{i=0}^{d-1} \Sigma^i (a)$$.

void _qadic_norm(fmpz_t rop, const fmpz *op, slong len, const fmpz *a, const slong *j, slong lena, const fmpz_t p, slong N)

Sets rop to the norm of the element (op,len) in $$\mathbf{Z}_q$$ to precision $$N$$, where len is at least one.

The result will be reduced modulo $$p^N$$.

Note that whenever (op,len) is a unit, so is its norm. Thus, the output rop of this function will typically not have to be canonicalised or reduced by the caller.

Computes the norm of op to the given precision.

Algorithm selection is automatic depending on the input.

Whenever op has valuation greater than $$(p-1)^{-1}$$, this routine computes its norm rop via

$\operatorname{Norm} (x) = \exp \Bigl( \bigl( \operatorname{Trace} \log (x) \bigr) \Bigr).$

In the special case that op lies in $$\mathbf{Q}_p$$, returns its norm as $$\operatorname{Norm}(x) = x^d$$, where $$d$$ is the extension degree.

Otherwise, raises an abort signal.

The complexity of this implementation is quasi-linear in $$d$$ and $$N$$, and polynomial in $$\log p$$.

Sets rop to the norm of op, using the formula

$\operatorname{Norm}(x) = \ell(f)^{-\deg(a)} \operatorname{Res}(f(X), a(X)),$

where $$\mathbf{Q}_q \cong \mathbf{Q}_p[X] / (f(X))$$, $$\ell(f)$$ is the leading coefficient of $$f(X)$$, and $$a(X) \in mathbf{Q}_p[X]$$ denotes the same polynomial as $$x$$.

The complexity of the current implementation is given by $$\mathcal{O}(d^4 M(N \log p))$$, where $$M(n)$$ denotes the complexity of multiplying to $$n$$-bit integers.

Output¶

In the current implementation, always returns $$1$$. The return code is part of the function’s signature to allow for a later implementation to return the number of characters printed or a non-positive error code.
In the current implementation, always returns $$1$$. The return code is part of the function’s signature to allow for a later implementation to return the number of characters printed or a non-positive error code.