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 code{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 code{nf} whose coefficients have up to the given number of bits.
-
void nf_elem_canonicalise(nf_elem_t a, 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 code{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 code{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 code{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 int 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 int 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 code{pol}.
-
void nf_elem_get_fmpq_poly(fmpq_poly_t pol, const nf_elem_t a, const nf_t nf)¶
Set code{pol} to a polynomial corresponding to \(a\), reduced modulo the defining polynomial of code{nf}.
-
void nf_elem_get_nmod_poly_den(nmod_poly_t pol, const nf_elem_t a, const nf_t nf, int den);¶
Set code{pol} to the reduction of the polynomial corresponding to the numerator of \(a\). If code{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 code{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);¶
Set code{pol} to the reduction of the polynomial corresponding to the numerator of \(a\). If code{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);¶
Set code{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 code{nf_elem_t b} to the given integer \(d\). Assumes \(d > 0\).
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 code{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 code{nf}. This function assumes \(a\) and \(b\) emph{are} canonicalised.
I/O¶
Arithmetic¶
-
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 code{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 code{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 code{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 code{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 code{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 code{_nf_elem_mul}, but reduction modulo the defining polynomial of the number field is only carried out if code{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 code{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 code{nf_elem_mul}, but reduction modulo the defining polynomial of the number field is only carried out if code{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 code{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 code{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 code{res} to \(a^e\) using left-to-right binary exponentiation as described in~citep[p.~461]{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 code{res} = code{a^e} using the binary exponentiation algorithm. If \(e\) is zero, returns one, so that in particular code{0^0 = 1}.
-
void _nf_elem_norm(fmpz_t rnum, fmpz_t rden, const nf_elem_t a, const nf_t nf)¶
Set code{{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 code{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, fmpz_t div, slong nbits)¶
Set code{res} to the absolute norm of the given number field element \(a\), divided by code{div} . Assumes the result to be an integer and having at most code{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 code{{rnum, rden}} to the absolute norm of the given number field element \(a\), divided by code{div} . Assumes the result to be an integer and having at most code{nbits} bits.
Representation matrix¶
-
void nf_elem_rep_mat(fmpq_mat_t res, const nf_elem_t a, const nf_t nf)¶
Set code{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)¶
If code{den == 0}, return an element \(z\) with denominator \(1\), such that the coefficients of \(z - da\) are divisble by code{mod}, where \(d\) is the denominator of \(a\). The coefficients of \(z\) are reduced modulo code{mod}.
If code{den == 1}, return an element \(z\), such that \(z - a\) has denominator \(1\) and the coefficients of \(z - a\) are divisble by code{mod}. The coefficients of \(z\) are reduced modulo code{mod * 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)¶
If code{den == 0}, return an element \(z\) with denominator \(1\), such that the coefficients of \(z - da\) are divisble by code{mod}, where \(d\) is the denominator of \(a\). The coefficients of \(z\) are reduced modulo code{mod}.
If code{den == 1}, return an element \(z\), such that \(z - a\) has denominator \(1\) and the coefficients of \(z - a\) are divisble by code{mod}. The coefficients of \(z\) are reduced modulo code{mod * 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 code{mod}. The coefficients of \(z\) are reduced modulo code{mod * 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 code{mod}. The coefficients of \(z\) are reduced modulo code{mod * d}, where \(d\) is the denominator of \(b\).
Reduction takes place with respect to the symmetric residue system.