fq.h – finite fields¶
Description.
Context Management¶
-
void
fq_ctx_init
(fq_ctx_t ctx, const fmpz_t 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_ctx_init_conway
(fq_ctx_t ctx, const fmpz_t 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_ctx_init_conway
(fq_ctx_t ctx, const fmpz_t 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_ctx_init_modulus
(fq_ctx_t ctx, fmpz_mod_poly_t modulus, const char *var)¶ Initialises the context for given
modulus
with namevar
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.
-
const fmpz_mod_poly_struct*
fq_ctx_modulus
(const fq_ctx_t ctx)¶ Returns a pointer to the modulus in the context.
-
long
fq_ctx_degree
(const fq_ctx_t ctx)¶ Returns the degree of the field extension \([\mathbf{F}_{q} : \mathbf{F}_{p}]\), which is equal to \(\log_{p} q\).
-
int
fq_ctx_fprint
(FILE * file, const fq_ctx_t ctx)¶ Prints the context information to {tt{file}}. Returns 1 for a success and a negative number for an error.
Memory management¶
-
void
fq_init2
(fq_t rop, const fq_ctx_t ctx)¶ Initialises
poly
with at least enough space for it to be an element ofctx
and sets it to~`0`.
-
void
_fq_sparse_reduce
(fmpz *R, slong lenR, const fq_ctx_t ctx)¶ Reduces
(R, lenR)
modulo the polynomial \(f\) given by the modulus ofctx
.
-
void
_fq_dense_reduce
(fmpz *R, slong lenR, const fq_ctx_t ctx)¶ Reduces
(R, lenR)
modulo the polynomial \(f\) given by the modulus ofctx
using Newton division.
Basic arithmetic¶
-
void
fq_add
(fq_t rop, const fq_t op1, const fq_t op2, const fq_ctx_t ctx)¶ Sets
rop
to the sum ofop1
andop2
.
-
void
fq_sub
(fq_t rop, const fq_t op1, const fq_t op2, const fq_ctx_t ctx)¶ Sets
rop
to the difference ofop1
andop2
.
-
void
fq_sub_one
(fq_t rop, const fq_t op1, const fq_ctx_t ctx)¶ Sets
rop
to the difference ofop1
and \(1\).
-
void
fq_mul
(fq_t rop, const fq_t op1, const fq_t op2, const fq_ctx_t ctx)¶ Sets
rop
to the product ofop1
andop2
, reducing the output in the given context.
-
void
fq_mul_fmpz
(fq_t rop, const fq_t op, const fmpz_t x, const fq_ctx_t ctx)¶ Sets
rop
to the product ofop
and \(x\), reducing the output in the given context.
-
void
fq_mul_si
(fq_t rop, const fq_t op, slong x, const fq_ctx_t ctx)¶ Sets
rop
to the product ofop
and \(x\), reducing the output in the given context.
-
void
fq_mul_ui
(fq_t rop, const fq_t op, ulong x, const fq_ctx_t ctx)¶ Sets
rop
to the product ofop
and \(x\), reducing the output in the given context.
-
void
fq_sqr
(fq_t rop, const fq_t op, const fq_ctx_t ctx)¶ Sets
rop
to the square ofop
, reducing the output in the given context.
-
void
fq_div
(fq_t rop, const fq_t op1, const fq_t op2, const fq_ctx_t ctx)¶ Sets
rop
to the quotient ofop1
andop2
, reducing the output in the given context.
-
void
_fq_inv
(fmpz *rop, const fmpz *op, slong len, const fq_ctx_t ctx)¶ Sets
(rop, d)
to the inverse of the non-zero element(op, len)
.
-
void
fq_inv
(fq_t rop, const fq_t op, const fq_ctx_t ctx)¶ Sets
rop
to the inverse of the non-zero elementop
.
-
void
fq_gcdinv
(fq_t f, fq_t inv, const fq_t op, const fq_ctx_t ctx)¶ Sets
inv
to be the inverse ofop
modulo the modulus ofctx
. Ifop
is not invertible, thenf
is set to a factor of the modulus; otherwise, it is set to one.
-
void
_fq_pow
(fmpz *rop, const fmpz *op, slong len, const fmpz_t e, const fq_ctx_t ctx)¶ Sets
(rop, 2*d-1)
to(op,len)
raised to the power~`e`, reduced modulo \(f(X)\), the modulus ofctx
.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.
Roots¶
Output¶
-
int
fq_fprint_pretty
(FILE *file, const fq_t op, const fq_ctx_t ctx)¶ Prints a pretty representation of
op
tofile
.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.
-
int
fq_print_pretty
(const fq_t op, const fq_ctx_t ctx)¶ Prints a pretty representation of
op
tostdout
.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.
-
void
fq_fprint
(FILE * file, const fq_t op, const fq_ctx_t ctx)¶ Prints a representation of
op
tofile
.For further details on the representation used, see
fmpz_mod_poly_fprint()
.
-
void
fq_print
(const fq_t op, const fq_ctx_t ctx)¶ Prints a representation of
op
tostdout
.For further details on the representation used, see
fmpz_mod_poly_print()
.
Randomisation¶
-
void
fq_randtest
(fq_t rop, flint_rand_t state, const fq_ctx_t ctx)¶ Generates a random element of \(\mathbf{F}_q\).
Assignments and conversions¶
-
void
fq_set_si
(fq_t rop, const slong x, const fq_ctx_t ctx)¶ Sets
rop
tox
, considered as an element of \(\mathbf{F}_p\).
-
void
fq_set_ui
(fq_t rop, const ulong x, const fq_ctx_t ctx)¶ Sets
rop
tox
, considered as an element of \(\mathbf{F}_p\).
Comparison¶
-
int
fq_equal
(const fq_t op1, const fq_t op2, const fq_ctx_t ctx)¶ Returns whether
op1
andop2
are equal.
Special functions¶
-
void
_fq_trace
(fmpz_t rop, const fmpz *op, slong len, const fq_ctx_t ctx)¶ Sets
rop
to the trace of the non-zero element(op, len)
in \(\mathbf{F}_{q}\).
-
void
fq_trace
(fmpz_t rop, const fq_t op, const fq_ctx_t ctx)¶ Sets
rop
to the trace ofop
.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 \(\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_norm
(fmpz_t rop, const fmpz *op, slong len, const fq_ctx_t ctx)¶ Sets
rop
to the norm of the non-zero element(op, len)
in \(\mathbf{F}_{q}\).
-
void
fq_norm
(fmpz_t rop, const fq_t op, const fq_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 \(\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_frobenius
(fmpz *rop, const fmpz *op, slong len, slong e, const fq_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 neitherop
nore
are zero.
-
void
fq_frobenius
(fq_t rop, const fq_t op, slong e, const fq_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 \Gal(\mathbf{F}_q/\mathbf{F}_p)\) is the Frobenius element \(\sigma \colon x \mapsto x^p\).