# fq_nmod.h – finite fields (word-size characteristic)

We represent an element of the finite field \(\mathbf{F}_{p^n} \cong \mathbf{F}_p[X]/(f(X))\), where \(f(X) \in \mathbf{F}_p[X]\) is a monic, irreducible polynomial of degree \(n\), as a polynomial in \(\mathbf{F}_p[X]\) of degree less than \(n\). The underlying data structure is an `nmod_poly_t`.

The default choice for \(f(X)\) is the Conway polynomial for the pair \((p,n)\), enabled by Frank Lübeck’s data base of Conway polynomials using the `_nmod_poly_conway()` function. If a Conway polynomial is not available, then a random irreducible polynomial will be chosen for \(f(X)\). Additionally, the user is able to supply their own \(f(X)\).

## Types, macros and constants

type fq_nmod_ctx_struct

type fq_nmod_ctx_t

type fq_nmod_struct

type fq_nmod_t

## Context Management

void fq_nmod_ctx_init_ui(fq_nmod_ctx_t ctx, ulong p, slong d, const char *var)

  Initialises the context for prime \(p\) and extension degree \(d\), with name `var` for the generator. By default, it will try use a Conway polynomial; if one is not available, a minimal weight irreducible polynomial will be used.

  Assumes that \(p\) is a prime.

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

void fq_nmod_ctx_init_minimal_weight_ui(fq_nmod_ctx_t ctx, ulong p, slong d, const char *var)

  Initialises the context for prime \(p\) and extension degree \(d\), with name `var` for the generator, choosing a modulus polynomial with minimal number of nonzero terms for efficient arithmetic.

  Assumes that \(p\) is a prime.

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

int _fq_nmod_ctx_init_conway_ui(fq_nmod_ctx_t ctx, ulong p, slong d, const char *var)

  Attempts to initialise the context for prime \(p\) and extension degree \(d\), with name `var` for the generator using a Conway polynomial for the modulus.

  Returns \(1\) if the Conway polynomial is in the database for the given size and the initialization is successful; otherwise, returns \(0\).

  Assumes that \(p\) is a prime.

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

void fq_nmod_ctx_init_conway_ui(fq_nmod_ctx_t ctx, ulong p, slong d, const char *var)

  Initialises the context for prime \(p\) and extension degree \(d\), with name `var` for the generator using a Conway polynomial for the modulus.

  Assumes that \(p\) is a prime.

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

void fq_nmod_ctx_init_modulus(fq_nmod_ctx_t ctx, const nmod_poly_t modulus, const char *var)

  Initialises the context for given `modulus` with name `var` for the generator.

  Assumes that `modulus` is an irreducible polynomial over \(\mathbf{F}_{p}\).

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

void fq_nmod_ctx_init_randtest(fq_nmod_ctx_t ctx, flint_rand_t state, int type)

  Initialises `ctx` to a random finite field, where the prime and degree is set according to `type`. To see what prime and degrees may be output, see `type` in `_nmod_poly_conway_rand()`.

void fq_nmod_ctx_init_randtest_reducible(fq_nmod_ctx_t ctx, flint_rand_t state, int type)

  Initializes `ctx` to a random extension of a word-sized prime field, where the prime and degree is set according to `type`. If `type` is \(0\) the prime and degree may be large, else if `type` is \(1\) the degree is small but the prime may be large, else if `type` is \(2\) the prime is small but the degree may be large, else if `type` is \(3\) both prime and degree are small.

  The modulus may or may not be irreducible.

void fq_nmod_ctx_clear(fq_nmod_ctx_t ctx)

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

const nmod_poly_struct *fq_nmod_ctx_modulus(const fq_nmod_ctx_t ctx)

  Returns a pointer to the modulus in the context.

slong fq_nmod_ctx_degree(const fq_nmod_ctx_t ctx)

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

ulong fq_nmod_ctx_prime(const fq_nmod_ctx_t ctx)

  Returns the prime \(p\) of the context.

void fq_nmod_ctx_order(fmpz_t f, const fq_nmod_ctx_t ctx)

  Sets \(f\) to be the size of the finite field.

int fq_nmod_ctx_fprint(FILE *file, const fq_nmod_ctx_t ctx)

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

void fq_nmod_ctx_print(const fq_nmod_ctx_t ctx)

  Prints the context information to `stdout`.

## Memory management

void fq_nmod_init(fq_nmod_t rop, const fq_nmod_ctx_t ctx)

  Initialises the element `rop`, setting its value to \(0\). Currently, the behaviour is identical to `fq_nmod_init2`, as it also ensures `rop` has enough space for it to be an element of `ctx`, this may change in the future.

void fq_nmod_init2(fq_nmod_t rop, const fq_nmod_ctx_t ctx)

  Initialises `rop` with at least enough space for it to be an element of `ctx` and sets it to \(0\).

void fq_nmod_clear(fq_nmod_t rop, const fq_nmod_ctx_t ctx)

  Clears the element `rop`.

void _fq_nmod_sparse_reduce(ulong *R, slong lenR, const fq_nmod_ctx_t ctx)

  Reduces `(R, lenR)` modulo the polynomial \(f\) given by the modulus of `ctx`.

void _fq_nmod_dense_reduce(ulong *R, slong lenR, const fq_nmod_ctx_t ctx)

  Reduces `(R, lenR)` modulo the polynomial \(f\) given by the modulus of `ctx` using Newton division.

void _fq_nmod_reduce(ulong *r, slong lenR, const fq_nmod_ctx_t ctx)

  Reduces `(R, lenR)` modulo the polynomial \(f\) given by the modulus of `ctx`. Does either sparse or dense reduction based on `ctx->sparse_modulus`.

void fq_nmod_reduce(fq_nmod_t rop, const fq_nmod_ctx_t ctx)

  Reduces the polynomial `rop` as an element of \(\mathbf{F}_p[X] / (f(X))\).

## Basic arithmetic

void fq_nmod_add(fq_nmod_t rop, const fq_nmod_t op1, const fq_nmod_t op2, const fq_nmod_ctx_t ctx)

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

void fq_nmod_sub(fq_nmod_t rop, const fq_nmod_t op1, const fq_nmod_t op2, const fq_nmod_ctx_t ctx)

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

void fq_nmod_sub_one(fq_nmod_t rop, const fq_nmod_t op1, const fq_nmod_ctx_t ctx)

  Sets `rop` to the difference of `op1` and \(1\).

void fq_nmod_neg(fq_nmod_t rop, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

void fq_nmod_mul(fq_nmod_t rop, const fq_nmod_t op1, const fq_nmod_t op2, const fq_nmod_ctx_t ctx)

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

void fq_nmod_mul_fmpz(fq_nmod_t rop, const fq_nmod_t op, const fmpz_t x, const fq_nmod_ctx_t ctx)

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

void fq_nmod_mul_si(fq_nmod_t rop, const fq_nmod_t op, slong x, const fq_nmod_ctx_t ctx)

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

void fq_nmod_mul_ui(fq_nmod_t rop, const fq_nmod_t op, ulong x, const fq_nmod_ctx_t ctx)

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

void fq_nmod_sqr(fq_nmod_t rop, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

void _fq_nmod_inv(nn_ptr *rop, nn_srcptr *op, slong len, const fq_nmod_ctx_t ctx)

  Sets `(rop, d)` to the inverse of the non-zero element `(op, len)`.

void fq_nmod_inv(fq_nmod_t rop, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

void fq_nmod_gcdinv(fq_nmod_t f, fq_nmod_t inv, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

  Sets `inv` to be the inverse of `op` modulo the modulus of `ctx`. If `op` is not invertible, then `f` is set to a factor of the modulus; otherwise, it is set to one.

void _fq_nmod_pow(ulong *rop, const ulong *op, slong len, const fmpz_t e, const fq_nmod_ctx_t ctx)

  Sets `(rop, 2*d-1)` to `(op,len)` raised to the power \(e\), reduced modulo \(f(X)\), the modulus of `ctx`.

  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 reduced modulo \(f(X)\), which is a polynomial of degree \(d\).

  Does not support aliasing.

void fq_nmod_pow(fq_nmod_t rop, const fq_nmod_t op, const fmpz_t e, const fq_nmod_ctx_t ctx)

  Sets `rop` to `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\).

void fq_nmod_pow_ui(fq_nmod_t rop, const fq_nmod_t op, const ulong e, const fq_nmod_ctx_t ctx)

  Sets `rop` to `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

int fq_nmod_sqrt(fq_nmod_t rop, const fq_nmod_t op1, const fq_nmod_ctx_t ctx)

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

void fq_nmod_pth_root(fq_nmod_t rop, const fq_nmod_t op1, const fq_nmod_ctx_t ctx)

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

int fq_nmod_is_square(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

## Output

int fq_nmod_fprint_pretty(FILE *file, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

  In case of success, returns a positive value. In case of failure, returns a non-positive value.

void fq_nmod_print_pretty(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

  In case of success, returns a positive value. In case of failure, returns a non-positive value.

int fq_nmod_fprint(FILE *file, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

  For further details on the representation used, see `nmod_poly_fprint()`.

void fq_nmod_print(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

  For further details on the representation used, see `nmod_poly_print()`.

char *fq_nmod_get_str(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

char *fq_nmod_get_str_pretty(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

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

## Randomisation

void fq_nmod_randtest(fq_nmod_t rop, flint_rand_t state, const fq_nmod_ctx_t ctx)

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

void fq_nmod_randtest_not_zero(fq_nmod_t rop, flint_rand_t state, const fq_nmod_ctx_t ctx)

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

void fq_nmod_randtest_dense(fq_nmod_t rop, flint_rand_t state, const fq_nmod_ctx_t ctx)

  Generates a random element of \(\mathbf{F}_q\) which has an underlying polynomial with dense coefficients.

void fq_nmod_rand(fq_nmod_t rop, flint_rand_t state, const fq_nmod_ctx_t ctx)

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

void fq_nmod_rand_not_zero(fq_nmod_t rop, flint_rand_t state, const fq_nmod_ctx_t ctx)

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

## Assignments and conversions

void fq_nmod_set(fq_nmod_t rop, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

  Sets `rop` to `op`.

void fq_nmod_set_si(fq_nmod_t rop, const slong x, const fq_nmod_ctx_t ctx)

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

void fq_nmod_set_ui(fq_nmod_t rop, const ulong x, const fq_nmod_ctx_t ctx)

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

void fq_nmod_set_fmpz(fq_nmod_t rop, const fmpz_t x, const fq_nmod_ctx_t ctx)

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

void fq_nmod_swap(fq_nmod_t op1, fq_nmod_t op2, const fq_nmod_ctx_t ctx)

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

void fq_nmod_zero(fq_nmod_t rop, const fq_nmod_ctx_t ctx)

  Sets `rop` to zero.

void fq_nmod_one(fq_nmod_t rop, const fq_nmod_ctx_t ctx)

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

void fq_nmod_gen(fq_nmod_t rop, const fq_nmod_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.

int fq_nmod_get_fmpz(fmpz_t rop, const fq_nmod_t op, const fq_nmod_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.

void fq_nmod_get_nmod_poly(nmod_poly_t a, const fq_nmod_t b, const fq_nmod_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`.

void fq_nmod_set_nmod_poly(fq_nmod_t a, const nmod_poly_t b, const fq_nmod_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`.

void fq_nmod_get_nmod_mat(nmod_mat_t col, const fq_nmod_t a, const fq_nmod_ctx_t ctx)

  Convert `a` to a column vector of length `degree(ctx)`.

void fq_nmod_set_nmod_mat(fq_nmod_t a, const nmod_mat_t col, const fq_nmod_ctx_t ctx)

  Convert a column vector `col` of length `degree(ctx)` to an element of `ctx`.

## Comparison

int fq_nmod_is_zero(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

  Returns whether `op` is equal to zero.

int fq_nmod_is_one(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

  Returns whether `op` is equal to one.

int fq_nmod_equal(const fq_nmod_t op1, const fq_nmod_t op2, const fq_nmod_ctx_t ctx)

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

int fq_nmod_is_invertible(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

  Returns whether `op` is an invertible element.

int fq_nmod_is_invertible_f(fq_nmod_t f, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

  Returns whether `op` is an invertible element. If it is not, then `f` is set to a factor of the modulus.

int fq_nmod_cmp(const fq_nmod_t a, const fq_nmod_t b, const fq_nmod_ctx_t ctx)

  Return `1` (resp. `-1`, or `0`) if `a` is after (resp. before, same as) `b` in some arbitrary but fixed total ordering of the elements.

## Special functions

void _fq_nmod_trace(fmpz_t rop, const ulong *op, slong len, const fq_nmod_ctx_t ctx)

  Sets `rop` to the trace of the non-zero element `(op, len)` in \(\mathbf{F}_{q}\).

void fq_nmod_trace(fmpz_t rop, const fq_nmod_t op, const fq_nmod_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\).

void _fq_nmod_norm(fmpz_t rop, const ulong *op, slong len, const fq_nmod_ctx_t ctx)

  Sets `rop` to the norm of the non-zero element `(op, len)` in \(\mathbf{F}_{q}\).

void fq_nmod_norm(fmpz_t rop, const fq_nmod_t op, const fq_nmod_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.

void _fq_nmod_frobenius(ulong *rop, const ulong *op, slong len, slong e, const fq_nmod_ctx_t ctx)

  Sets `(rop, 2d-1)` to the image of `(op, len)` under the Frobenius operator raised to the e-th power, assuming that neither `op` nor `e` are zero.

void fq_nmod_frobenius(fq_nmod_t rop, const fq_nmod_t op, slong e, const fq_nmod_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\).

int fq_nmod_multiplicative_order(fmpz *ord, const fq_nmod_t op, const fq_nmod_ctx_t ctx)

  Computes the order of `op` as an element of the multiplicative group of `ctx`.

  Returns 0 if `op` is 0, otherwise it returns 1 if `op` is a generator of the multiplicative group, and -1 if it is not.

  This function can also be used to check primitivity of a generator of a finite field whose defining polynomial is not primitive.

int fq_nmod_is_primitive(const fq_nmod_t op, const fq_nmod_ctx_t ctx)

  Returns whether `op` is primitive, i.e., whether it is a generator of the multiplicative group of `ctx`.

## Bit packing

void fq_nmod_bit_pack(fmpz_t f, const fq_nmod_t op, flint_bitcnt_t bit_size, const fq_nmod_ctx_t ctx)

  Packs `op` into bitfields of size `bit_size`, writing the result to `f`.

void fq_nmod_bit_unpack(fq_nmod_t rop, const fmpz_t f, flint_bitcnt_t bit_size, const fq_nmod_ctx_t ctx)

  Unpacks into `rop` the element with coefficients packed into fields of size `bit_size` as represented by the integer `f`.