/*=============================================================================

    This file is part of Antic.

    Antic is free software: you can redistribute it and/or modify it under
    the terms of the GNU Lesser General Public License (LGPL) as published
    by the Free Software Foundation; either version 2.1 of the License, or
    (at your option) any later version. See <http://www.gnu.org/licenses/>.

=============================================================================*/
/******************************************************************************

    Copyright (C) 2013 William Hart

******************************************************************************/

*******************************************************************************

    Initialisation

*******************************************************************************

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$.

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

    Set $d$ to the denominator of the \code{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 \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.

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 \code{stdout} using the
    null-terminated string \code{var} not equal to \code{"\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 \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.

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

    Set \code{{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 \code{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 \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.

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
    \code{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
    \code{mod}.

    Reduction takes place with respect to the symmetric residue system.