.. _fq_default:

**fq_default.h** -- unified finite fields
===============================================================================

Types, macros and constants
-------------------------------------------------------------------------------

.. type:: fq_default_ctx_t

.. type:: fq_default_t

Context Management
--------------------------------------------------------------------------------


.. function:: void fq_default_ctx_init_type(fq_default_ctx_t ctx, const fmpz_t p, slong d, const char * var, int type)
              void fq_default_ctx_init(fq_default_ctx_t ctx, const fmpz_t p, slong d, const char * var)

    Initialises the context ``ctx`` for prime `p` and extension degree `d`, with
    string ``var`` of length at least one for the generator display name.  By
    default, it will try use a Conway polynomial; if one is not available, a
    random irreducible polynomial will be used.

    For ``fq_default_ctx_init``, it will choose the best representation for
    performance.

    For ``fq_default_ctx_init_type``, a separate argument ``type`` is required
    which sets which representation to use. These values can be: ``0`` (which
    then will act just like ``fq_default_ctx_init``), ``FQ_DEFAULT_FQ_ZECH``,
    ``FQ_DEFAULT_FQ_NMOD``, ``FQ_DEFAULT_FQ``, ``FQ_DEFAULT_NMOD`` and
    ``FQ_DEFAULT_FMPZ_MOD``.

.. function:: void fq_default_ctx_init_modulus_nmod_type(fq_default_ctx_t ctx, const nmod_poly_t modulus, const char * var, int type)
              void fq_default_ctx_init_modulus_nmod(fq_default_ctx_t ctx, const nmod_poly_t modulus, const char * var)
              void fq_default_ctx_init_modulus_type(fq_default_ctx_t ctx, const fmpz_mod_poly_t modulus, fmpz_mod_ctx_t mod_ctx, const char * var, int type)
              void fq_default_ctx_init_modulus(fq_default_ctx_t ctx, const fmpz_mod_poly_t modulus, fmpz_mod_ctx_t mod_ctx, const char * var)

    Initialises the finite field context ``ctx`` defined by the given polynomial
    ``modulus``. For the ``fmpz_mod_poly`` type, the context structure
    ``mod_ctx`` for the polynomial must also be given. Sets the printing of
    variable of the field to the string ``var``, which is assumed to be length
    of at least one.

    The context ``ctx`` will after the call represent the finite field in one of
    the five different formats: ``fq_zech``, ``fq_nmod``, ``nmod``, ``fmpz_mod``
    and ``fq``.

    The characteristic of the field will be the modulus of the polynomial and
    its degree will equal to the degree of the polynomial. Furthermore, it
    assumes that the characteristic is prime and that the polynomial
    irreducible. Furthermore, in order for the field to be representable as the
    Zech logarithm we assume that polynomial is primitive; if it is not, another
    representation will be chosen.

    For ``fq_default_ctx_init_modulus_nmod`` or ``fq_default_ctx_init_modulus``,
    it chooses the best representation for performance.

    For ``fq_default_ctx_init_modulus_nmod_type`` or
    ``fq_default_ctx_init_modulus_type``, it expects ``type`` to be one of the
    following choices: ``FQ_DEFAULT_FQ_ZECH``, ``FQ_DEFAULT_FQ_NMOD``,
    ``FQ_DEFAULT_FQ``, ``FQ_DEFAULT_NMOD`` or ``FQ_DEFAULT_FMPZ_MOD``. To be
    clear: if the Zech logarithm is chosen but the polynomial is not primitive,
    another representation will be chosen.

.. function:: void fq_default_ctx_clear(fq_default_ctx_t ctx)

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

.. function:: int fq_default_ctx_type(const fq_default_ctx_t ctx)

    Returns `1` if the context contains an ``fq_zech`` context, `2` if it
    contains an ``fq_mod`` context and `3` if it contains an ``fq`` context.

.. function:: void * fq_default_ctx_inner(const fq_default_ctx_t ctx)

    Returns a pointer to the internal context object of type
    ``fq_ctx_t``, ``fq_zech_ctx_t``, ``fmpz_mod_ctx_t``, etc.

.. function:: slong fq_default_ctx_degree(const fq_default_ctx_t ctx)

    Returns the degree of the field extension
    `[\mathbf{F}_{q} : \mathbf{F}_{p}]`, which
    is equal to `\log_{p} q`.

.. function:: void fq_default_ctx_prime(fmpz_t prime, const fq_default_ctx_t ctx)

    Sets `prime` to the prime `p` in the context.

.. function:: void fq_default_ctx_order(fmpz_t f, const fq_default_ctx_t ctx)

     Sets `f` to be the size of the finite field.

.. function:: void fq_default_ctx_modulus(fmpz_mod_poly_t p, const fq_default_ctx_t ctx)

    Sets `p` to the defining polynomial of the finite field..

.. function:: int fq_default_ctx_fprint(FILE * file, const fq_default_ctx_t ctx)

    Prints the context information to ``file``. Returns 1 for a
    success and a negative number for an error.

.. function:: void fq_default_ctx_print(const fq_default_ctx_t ctx)

    Prints the context information to ``stdout``.

.. function:: void fq_default_ctx_init_randtest(fq_default_ctx_t ctx, flint_rand_t state)

    Initializes ``ctx`` to a random finite field using one of the five internal representations.
    Assumes that ``fq_default_ctx_init`` has not been called on ``ctx`` already.

.. function:: void fq_default_get_coeff_fmpz(fmpz_t c, fq_default_t op, slong n, const fq_default_ctx_t ctx)

    Set `c` to the degree `n` coefficient of the polynomial representation of
    the finite field element ``op``.


Memory management
--------------------------------------------------------------------------------


.. function:: void fq_default_init(fq_default_t rop, const fq_default_ctx_t ctx)

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

.. function:: void fq_default_init2(fq_default_t rop, const fq_default_ctx_t ctx)

    Initialises ``poly`` with at least enough space for it to be an element
    of ``ctx`` and sets it to `0`.

.. function:: void fq_default_clear(fq_default_t rop, const fq_default_ctx_t ctx)

    Clears the element ``rop``.


Predicates
--------------------------------------------------------------------------------


.. function:: int fq_default_is_invertible(const fq_default_t op, const fq_default_ctx_t ctx)

    Return ``1`` if ``op`` is an invertible element.


Basic arithmetic
--------------------------------------------------------------------------------


.. function:: void fq_default_add(fq_default_t rop, const fq_default_t op1, const fq_default_t op2, const fq_default_ctx_t ctx)

    Sets ``rop`` to the sum of ``op1`` and ``op2``.

.. function:: void fq_default_sub(fq_default_t rop, const fq_default_t op1, const fq_default_t op2, const fq_default_ctx_t ctx)

    Sets ``rop`` to the difference of ``op1`` and ``op2``.

.. function:: void fq_default_sub_one(fq_default_t rop, const fq_default_t op1, const fq_default_ctx_t ctx)

    Sets ``rop`` to the difference of ``op1`` and `1`.

.. function:: void fq_default_neg(fq_default_t rop, const fq_default_t op, const fq_default_ctx_t ctx)

    Sets ``rop`` to the negative of ``op``.

.. function:: void fq_default_mul(fq_default_t rop, const fq_default_t op1, const fq_default_t op2, const fq_default_ctx_t ctx)

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

.. function:: void fq_default_mul_fmpz(fq_default_t rop, const fq_default_t op, const fmpz_t x, const fq_default_ctx_t ctx)

    Sets ``rop`` to the product of ``op`` and `x`,
    reducing the output in the given context.

.. function:: void fq_default_mul_si(fq_default_t rop, const fq_default_t op, slong x, const fq_default_ctx_t ctx)

    Sets ``rop`` to the product of ``op`` and `x`,
    reducing the output in the given context.

.. function:: void fq_default_mul_ui(fq_default_t rop, const fq_default_t op, ulong x, const fq_default_ctx_t ctx)

    Sets ``rop`` to the product of ``op`` and `x`,
    reducing the output in the given context.

.. function:: void fq_default_sqr(fq_default_t rop, const fq_default_t op, const fq_default_ctx_t ctx)

    Sets ``rop`` to the square of ``op``,
    reducing the output in the given context.

.. function:: void fq_default_div(fq_default_t rop, fq_default_t op1, fq_default_t op2, const fq_default_ctx_t ctx)

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

.. function:: void fq_default_inv(fq_default_t rop, const fq_default_t op, const fq_default_ctx_t ctx)

    Sets ``rop`` to the inverse of the non-zero element ``op``.

.. function:: void fq_default_pow(fq_default_t rop, const fq_default_t op, const fmpz_t e, const fq_default_ctx_t ctx)

    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 `1`
    whenever `e = 0`.

.. function:: void fq_default_pow_ui(fq_default_t rop, const fq_default_t op, const ulong e, const fq_default_ctx_t ctx)

    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 `1`
    whenever `e = 0`.



Roots
--------------------------------------------------------------------------------


.. function:: int fq_default_sqrt(fq_default_t rop, const fq_default_t op1, const fq_default_ctx_t ctx)

    Sets ``rop`` to the square root of ``op1`` if it is a square, and return
    `1`, otherwise return `0`.

.. function:: void fq_default_pth_root(fq_default_t rop, const fq_default_t op1, const fq_default_ctx_t ctx)

    Sets ``rop`` to a `p^{th}` root root of ``op1``.  Currently,
    this computes the root by raising ``op1`` to `p^{d-1}` where
    `d` is the degree of the extension.

.. function:: int fq_default_is_square(const fq_default_t op, const fq_default_ctx_t ctx)

    Return ``1`` if ``op`` is a square.

Output
--------------------------------------------------------------------------------


.. function:: int fq_default_fprint_pretty(FILE * file, const fq_default_t op, const fq_default_ctx_t ctx)

    Prints a pretty representation of ``op`` to ``file``.

    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.

.. function:: void fq_default_print_pretty(const fq_default_t op, const fq_default_ctx_t ctx)

    Prints a pretty representation of ``op`` to ``stdout``.

    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.

.. function:: int fq_default_fprint(FILE * file, const fq_default_t op, const fq_default_ctx_t ctx)

    Prints a representation of ``op`` to ``file``.

.. function:: void fq_default_print(const fq_default_t op, const fq_default_ctx_t ctx)

    Prints a representation of ``op`` to ``stdout``.

.. function:: char * fq_default_get_str(const fq_default_t op, const fq_default_ctx_t ctx)

    Returns the plain FLINT string representation of the element
    ``op``.

.. function:: char * fq_default_get_str_pretty(const fq_default_t op, const fq_default_ctx_t ctx)

    Returns a pretty representation of the element ``op`` using the
    null-terminated string ``x`` as the variable name.


Randomisation
--------------------------------------------------------------------------------


.. function:: void fq_default_randtest(fq_default_t rop, flint_rand_t state, const fq_default_ctx_t ctx)

    Generates a random element of `\mathbf{F}_q`.

.. function:: void fq_default_randtest_not_zero(fq_default_t rop, flint_rand_t state, const fq_default_ctx_t ctx)

    Generates a random non-zero element of `\mathbf{F}_q`.

.. function:: void fq_default_rand(fq_default_t rop, flint_rand_t state, const fq_default_ctx_t ctx)

    Generates a high quality random element of `\mathbf{F}_q`.

.. function:: void fq_default_rand_not_zero(fq_default_t rop, flint_rand_t state, const fq_default_ctx_t ctx)

    Generates a high quality non-zero random element of `\mathbf{F}_q`.


Assignments and conversions
--------------------------------------------------------------------------------


.. function:: void fq_default_set(fq_default_t rop, const fq_default_t op, const fq_default_ctx_t ctx)

    Sets ``rop`` to ``op``.

.. function:: void fq_default_set_si(fq_default_t rop, const slong x, const fq_default_ctx_t ctx)

    Sets ``rop`` to ``x``, considered as an element of
    `\mathbf{F}_p`.

.. function:: void fq_default_set_ui(fq_default_t rop, const ulong x, const fq_default_ctx_t ctx)

    Sets ``rop`` to ``x``, considered as an element of
    `\mathbf{F}_p`.

.. function:: void fq_default_set_fmpz(fq_default_t rop, const fmpz_t x, const fq_default_ctx_t ctx)

    Sets ``rop`` to ``x``, considered as an element of
    `\mathbf{F}_p`.

.. function:: void fq_default_swap(fq_default_t op1, fq_default_t op2, const fq_default_ctx_t ctx)

    Swaps the two elements ``op1`` and ``op2``.

.. function:: void fq_default_zero(fq_default_t rop, const fq_default_ctx_t ctx)

    Sets ``rop`` to zero.

.. function:: void fq_default_one(fq_default_t rop, const fq_default_ctx_t ctx)

    Sets ``rop`` to one, reduced in the given context.

.. function:: void fq_default_gen(fq_default_t rop, const fq_default_ctx_t ctx)

    Sets ``rop`` to a generator for the finite field.
    There is no guarantee this is a multiplicative generator of
    the finite field.

.. function:: int fq_default_get_fmpz(fmpz_t rop, const fq_default_t op, const fq_default_ctx_t ctx)

    If ``op`` has a lift to the integers, return `1` and set ``rop`` to the lift in `[0,p)`.
    Otherwise, return `0` and leave `rop` undefined.

.. function:: void fq_default_get_nmod_poly(nmod_poly_t poly, const fq_default_t op, const fq_default_ctx_t ctx)

    Sets ``poly`` to the polynomial representation of ``op``. Assumes the
    characteristic of the field and the modulus of the polynomial are the same.
    No checking of this occurs.

.. function:: void fq_default_set_nmod_poly(fq_default_t op, const nmod_poly_t poly, const fq_default_ctx_t ctx)

    Sets ``op`` to the finite field element represented by the polynomial
    ``poly``. Assumes the characteristic of the field and the modulus of the
    polynomial are the same. No checking of this occurs.

.. function:: void fq_default_get_fmpz_mod_poly(fmpz_mod_poly_t poly, const fq_default_t op,  const fq_default_ctx_t ctx)

    Sets ``poly`` to the polynomial representation of ``op``. Assumes the
    characteristic of the field and the modulus of the polynomial are the same.
    No checking of this occurs.

.. function:: void fq_default_set_fmpz_mod_poly(fq_default_t op, const fmpz_mod_poly_t poly, const fq_default_ctx_t ctx)

    Sets ``op`` to the finite field element represented by the polynomial
    ``poly``. Assumes the characteristic of the field and the modulus of the
    polynomial are the same. No checking of this occurs.

.. function:: void fq_default_get_fmpz_poly(fmpz_poly_t a, const fq_default_t b, const fq_default_ctx_t ctx)

    Set ``a`` to a representative of ``b`` in ``ctx``.
    The representatives are taken in `(\mathbb{Z}/p\mathbb{Z})[x]/h(x)` where
    `h(x)` is the defining polynomial in ``ctx``.

.. function:: void fq_default_set_fmpz_poly(fq_default_t a, const fmpz_poly_t b, const fq_default_ctx_t ctx)

    Set ``a`` to the element in ``ctx`` with representative ``b``.
    The representatives are taken in `(\mathbb{Z}/p\mathbb{Z})[x]/h(x)` where
    `h(x)` is the defining polynomial in ``ctx``.


Comparison
--------------------------------------------------------------------------------


.. function:: int fq_default_is_zero(const fq_default_t op, const fq_default_ctx_t ctx)

    Returns whether ``op`` is equal to zero.

.. function:: int fq_default_is_one(const fq_default_t op, const fq_default_ctx_t ctx)

    Returns whether ``op`` is equal to one.

.. function:: int fq_default_equal(const fq_default_t op1, const fq_default_t op2, const fq_default_ctx_t ctx)

    Returns whether ``op1`` and ``op2`` are equal.


Special functions
--------------------------------------------------------------------------------


.. function:: void fq_default_trace(fmpz_t rop, const fq_default_t op, const fq_default_ctx_t ctx)

    Sets ``rop`` to the trace of ``op``.

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

.. function:: void fq_default_norm(fmpz_t rop, const fq_default_t op, const fq_default_ctx_t ctx)

    Computes the norm of ``op``.

    For an element `a \in \mathbf{F}_q`, multiplication by `a` defines
    a `\mathbf{F}_p`-linear map on `\mathbf{F}_q`.  We define the norm
    of `a` as the determinant of this map.  Equivalently, if `\Sigma` generates
    `\operatorname{Gal}(\mathbf{F}_q / \mathbf{F}_p)` then the trace of `a` is equal to
    `\prod_{i=0}^{d-1} \Sigma^i (a)`, where
    `d = \text{dim}_{\mathbf{F}_p}(\mathbf{F}_q)`.

    Algorithm selection is automatic depending on the input.

.. function:: void fq_default_frobenius(fq_default_t rop, const fq_default_t op, slong e, const fq_default_ctx_t ctx)

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

    Recall that `\mathbf{F}_q / \mathbf{F}_p` is Galois with Galois group
    `\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`.