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

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(mp_limb_t *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(mp_limb_t *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(mp_limb_t *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(mp_ptr *rop, mp_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(mp_limb_t *rop, const mp_limb_t *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 mp_limb_t *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 mp_limb_t *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(mp_limb_t *rop, const mp_limb_t *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.