# nf_elem.h – number field elements¶

Authors:

• William Hart

## Initialisation¶

type nf_elem_struct
type nf_elem_t

Represents a number field element.

void nf_elem_init(nf_elem_t a, const nf_t nf)

Initialise a number field element to belong to the given number field nf. The element is set to zero.

void nf_elem_clear(nf_elem_t a, const nf_t nf)

Clear resources allocated by the given number field element in the given number field.

void nf_elem_randtest(nf_elem_t a, flint_rand_t state, mp_bitcnt_t bits, const nf_t nf)

Generate a random number field element $$a$$ in the number field nf whose coefficients have up to the given number of bits.

void nf_elem_canonicalise(nf_elem_t a, const nf_t nf)

Canonicalise a number field element, i.e. reduce numerator and denominator to lowest terms. If the numerator is $$0$$, set the denominator to $$1$$.

void _nf_elem_reduce(nf_elem_t a, const nf_t nf)

Reduce a number field element modulo the defining polynomial. This is used with functions such as nf_elem_mul_red which allow reduction to be delayed. Does not canonicalise.

void nf_elem_reduce(nf_elem_t a, const nf_t nf)

Reduce a number field element modulo the defining polynomial. This is used with functions such as nf_elem_mul_red which allow reduction to be delayed.

int _nf_elem_invertible_check(nf_elem_t a, const nf_t nf)

Whilst the defining polynomial for a number field should by definition be irreducible, it is not enforced. Thus in test code, it is convenient to be able to check that a given number field element is invertible modulo the defining polynomial of the number field. This function does precisely this.

If $$a$$ is invertible modulo the defining polynomial of nf the value $$1$$ is returned, otherwise $$0$$ is returned.

The function is only intended to be used in test code.

## Conversion¶

void nf_elem_set_fmpz_mat_row(nf_elem_t b, const fmpz_mat_t M, const slong i, fmpz_t den, const nf_t nf)

Set $$b$$ to the element specified by row $$i$$ of the matrix $$M$$ and with the given denominator $$d$$. Column $$0$$ of the matrix corresponds to the constant coefficient of the number field element.

void nf_elem_get_fmpz_mat_row(fmpz_mat_t M, const slong i, fmpz_t den, const nf_elem_t b, const nf_t nf)

Set the row $$i$$ of the matrix $$M$$ to the coefficients of the numerator of the element $$b$$ and $$d$$ to the denominator of $$b$$. Column $$0$$ of the matrix corresponds to the constant coefficient of the number field element.

void nf_elem_set_fmpq_poly(nf_elem_t a, const fmpq_poly_t pol, const nf_t nf)

Set $$a$$ to the element corresponding to the polynomial pol.

void nf_elem_get_fmpq_poly(fmpq_poly_t pol, const nf_elem_t a, const nf_t nf)

Set pol to a polynomial corresponding to $$a$$, reduced modulo the defining polynomial of nf.

void nf_elem_get_nmod_poly_den(nmod_poly_t pol, const nf_elem_t a, const nf_t nf, int den)

Set pol to the reduction of the polynomial corresponding to the numerator of $$a$$. If den == 1, the result is multiplied by the inverse of the denominator of $$a$$. In this case it is assumed that the reduction of the denominator of $$a$$ is invertible.

void nf_elem_get_nmod_poly(nmod_poly_t pol, const nf_elem_t a, const nf_t nf)

Set pol to the reduction of the polynomial corresponding to the numerator of $$a$$. The result is multiplied by the inverse of the denominator of $$a$$. It is assumed that the reduction of the denominator of $$a$$ is invertible.

void nf_elem_get_fmpz_mod_poly_den(fmpz_mod_poly_t pol, const nf_elem_t a, const nf_t nf, int den, const fmpz_mod_ctx_t ctx)

Set pol to the reduction of the polynomial corresponding to the numerator of $$a$$. If den == 1, the result is multiplied by the inverse of the denominator of $$a$$. In this case it is assumed that the reduction of the denominator of $$a$$ is invertible.

void nf_elem_get_fmpz_mod_poly(fmpz_mod_poly_t pol, const nf_elem_t a, const nf_t nf, const fmpz_mod_ctx_t ctx)

Set pol to the reduction of the polynomial corresponding to the numerator of $$a$$. The result is multiplied by the inverse of the denominator of $$a$$. It is assumed that the reduction of the denominator of $$a$$ is invertible.

## Basic manipulation¶

void nf_elem_set_den(nf_elem_t b, fmpz_t d, const nf_t nf)

Set the denominator of the nf_elem_t b to the given integer $$d$$. Assumes $$d > 0$$.

void nf_elem_get_den(fmpz_t d, const nf_elem_t b, const nf_t nf)

Set $$d$$ to the denominator of the nf_elem_t b.

void _nf_elem_set_coeff_num_fmpz(nf_elem_t a, slong i, const fmpz_t d, const nf_t nf)

Set the $$i$$-th coefficient of the denominator of $$a$$ to the given integer $$d$$.

## Comparison¶

int _nf_elem_equal(const nf_elem_t a, const nf_elem_t b, const nf_t nf)

Return $$1$$ if the given number field elements are equal in the given number field nf. This function does emph{not} assume $$a$$ and $$b$$ are canonicalised.

int nf_elem_equal(const nf_elem_t a, const nf_elem_t b, const nf_t nf)

Return $$1$$ if the given number field elements are equal in the given number field nf. This function assumes $$a$$ and $$b$$ emph{are} canonicalised.

int nf_elem_is_zero(const nf_elem_t a, const nf_t nf)

Return $$1$$ if the given number field element is equal to zero, otherwise return $$0$$.

int nf_elem_is_one(const nf_elem_t a, const nf_t nf)

Return $$1$$ if the given number field element is equal to one, otherwise return $$0$$.

## I/O¶

void nf_elem_print_pretty(const nf_elem_t a, const nf_t nf, const char *var)

Print the given number field element to stdout using the null-terminated string var not equal to "\0" as the name of the primitive element.

## Arithmetic¶

void nf_elem_zero(nf_elem_t a, const nf_t nf)

Set the given number field element to zero.

void nf_elem_one(nf_elem_t a, const nf_t nf)

Set the given number field element to one.

void nf_elem_set(nf_elem_t a, const nf_elem_t b, const nf_t nf)

Set the number field element $$a$$ to equal the number field element $$b$$, i.e. set $$a = b$$.

void nf_elem_neg(nf_elem_t a, const nf_elem_t b, const nf_t nf)

Set the number field element $$a$$ to minus the number field element $$b$$, i.e. set $$a = -b$$.

void nf_elem_swap(nf_elem_t a, nf_elem_t b, const nf_t nf)

Efficiently swap the two number field elements $$a$$ and $$b$$.

void nf_elem_mul_gen(nf_elem_t a, const nf_elem_t b, const nf_t nf)

Multiply the element $$b$$ with the generator of the number field.

void _nf_elem_add(nf_elem_t r, const nf_elem_t a, const nf_elem_t b, const nf_t nf)

Add two elements of a number field nf, i.e. set $$r = a + b$$. Canonicalisation is not performed.

void nf_elem_add(nf_elem_t r, const nf_elem_t a, const nf_elem_t b, const nf_t nf)

Add two elements of a number field nf, i.e. set $$r = a + b$$.

void _nf_elem_sub(nf_elem_t r, const nf_elem_t a, const nf_elem_t b, const nf_t nf)

Subtract two elements of a number field nf, i.e. set $$r = a - b$$. Canonicalisation is not performed.

void nf_elem_sub(nf_elem_t r, const nf_elem_t a, const nf_elem_t b, const nf_t nf)

Subtract two elements of a number field nf, i.e. set $$r = a - b$$.

void _nf_elem_mul(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf)

Multiply two elements of a number field nf, i.e. set $$r = a * b$$. Does not canonicalise. Aliasing of inputs with output is not supported.

void _nf_elem_mul_red(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf, int red)

As per _nf_elem_mul, but reduction modulo the defining polynomial of the number field is only carried out if red == 1. Assumes both inputs are reduced.

void nf_elem_mul(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf)

Multiply two elements of a number field nf, i.e. set $$r = a * b$$.

void nf_elem_mul_red(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf, int red)

As per nf_elem_mul, but reduction modulo the defining polynomial of the number field is only carried out if red == 1. Assumes both inputs are reduced.

void _nf_elem_inv(nf_elem_t r, const nf_elem_t a, const nf_t nf)

Invert an element of a number field nf, i.e. set $$r = a^{-1}$$. Aliasing of the input with the output is not supported.

void nf_elem_inv(nf_elem_t r, const nf_elem_t a, const nf_t nf)

Invert an element of a number field nf, i.e. set $$r = a^{-1}$$.

void _nf_elem_div(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf)

Set $$a$$ to $$b/c$$ in the given number field. Aliasing of $$a$$ and $$b$$ is not permitted.

void nf_elem_div(nf_elem_t a, const nf_elem_t b, const nf_elem_t c, const nf_t nf)

Set $$a$$ to $$b/c$$ in the given number field.

void _nf_elem_pow(nf_elem_t res, const nf_elem_t a, ulong e, const nf_t nf)

Set res to $$a^e$$ using left-to-right binary exponentiation as described on p. 461 of [Knu1997].

Assumes that $$a \neq 0$$ and $$e > 1$$. Does not support aliasing.

void nf_elem_pow(nf_elem_t res, const nf_elem_t a, ulong e, const nf_t nf)

Set res = a^e using the binary exponentiation algorithm. If $$e$$ is zero, returns one, so that in particular 0^0 = 1.

void _nf_elem_norm(fmpz_t rnum, fmpz_t rden, const nf_elem_t a, const nf_t nf)

Set rnum, rden to the absolute norm of the given number field element $$a$$.

void nf_elem_norm(fmpq_t res, const nf_elem_t a, const nf_t nf)

Set res to the absolute norm of the given number field element $$a$$.

void nf_elem_norm_div(fmpq_t res, const nf_elem_t a, const nf_t nf, const fmpz_t div, slong nbits)

Set res to the absolute norm of the given number field element $$a$$, divided by div . Assumes the result to be an integer and having at most nbits bits.

void _nf_elem_norm_div(fmpz_t rnum, fmpz_t rden, const nf_elem_t a, const nf_t nf, const fmpz_t divisor, slong nbits)

Set rnum, rden to the absolute norm of the given number field element $$a$$, divided by div . Assumes the result to be an integer and having at most nbits bits.

void _nf_elem_trace(fmpz_t rnum, fmpz_t rden, const nf_elem_t a, const nf_t nf)

Set rnum, rden to the absolute trace of the given number field element $$a$$.

void nf_elem_trace(fmpq_t res, const nf_elem_t a, const nf_t nf)

Set res to the absolute trace of the given number field element $$a$$.

## Representation matrix¶

void nf_elem_rep_mat(fmpq_mat_t res, const nf_elem_t a, const nf_t nf)

Set res to the matrix representing the multiplication with $$a$$ with respect to the basis $$1, a, \dotsc, a^{d - 1}$$, where $$a$$ is the generator of the number field of $$d$$ is its degree.

void nf_elem_rep_mat_fmpz_mat_den(fmpz_mat_t res, fmpz_t den, const nf_elem_t a, const nf_t nf)

Return a tuple $$M, d$$ such that $$M/d$$ is the matrix representing the multiplication with $$a$$ with respect to the basis $$1, a, \dotsc, a^{d - 1}$$, where $$a$$ is the generator of the number field of $$d$$ is its degree. The integral matrix $$M$$ is primitive.

## Modular reduction¶

void nf_elem_mod_fmpz_den(nf_elem_t z, const nf_elem_t a, const fmpz_t mod, const nf_t nf, int den)

If den == 0, return an element $$z$$ with denominator $$1$$, such that the coefficients of $$z - da$$ are divisble by mod, where $$d$$ is the denominator of $$a$$. The coefficients of $$z$$ are reduced modulo mod.

If den == 1, return an element $$z$$, such that $$z - a$$ has denominator $$1$$ and the coefficients of $$z - a$$ are divisible by mod. The coefficients of $$z$$ are reduced modulo $$\mathtt{mod} \cdot d$$, where $$d$$ is the denominator of $$a$$.

Reduction takes place with respect to the positive residue system.

void nf_elem_smod_fmpz_den(nf_elem_t z, const nf_elem_t a, const fmpz_t mod, const nf_t nf, int den)

If den == 0, return an element $$z$$ with denominator $$1$$, such that the coefficients of $$z - da$$ are divisble by mod, where $$d$$ is the denominator of $$a$$. The coefficients of $$z$$ are reduced modulo mod.

If den == 1, return an element $$z$$, such that $$z - a$$ has denominator $$1$$ and the coefficients of $$z - a$$ are divisible by mod. The coefficients of $$z$$ are reduced modulo $$\mathtt{mod} \cdot d$$, where $$d$$ is the denominator of $$a$$.

Reduction takes place with respect to the symmetric residue system.

void nf_elem_mod_fmpz(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf)

Return an element $$z$$ such that $$z - a$$ has denominator $$1$$ and the coefficients of $$z - a$$ are divisible by mod. The coefficients of $$z$$ are reduced modulo $$\mathtt{mod} \cdot d$$, where $$d$$ is the denominator of $$b$$.

Reduction takes place with respect to the positive residue system.

void nf_elem_smod_fmpz(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf)

Return an element $$z$$ such that $$z - a$$ has denominator $$1$$ and the coefficients of $$z - a$$ are divisible by mod. The coefficients of $$z$$ are reduced modulo $$\mathtt{mod} \cdot d$$, where $$d$$ is the denominator of $$b$$.

Reduction takes place with respect to the symmetric residue system.

void nf_elem_coprime_den(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf)

Return an element $$z$$ such that the denominator of $$z - a$$ is coprime to mod.

Reduction takes place with respect to the positive residue system.

void nf_elem_coprime_den_signed(nf_elem_t res, const nf_elem_t a, const fmpz_t mod, const nf_t nf)

Return an element $$z$$ such that the denominator of $$z - a$$ is coprime to mod.

Reduction takes place with respect to the symmetric residue system.