fq.h – finite fields¶
Description.
Types, macros and constants¶
-
type fq_ctx_struct¶
-
type fq_ctx_t¶
Description.
-
type fq_struct¶
-
type fq_t¶
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, const fmpz_mod_poly_t modulus, const fmpz_mod_ctx_t ctxp, const char *var)¶
Initialises the context for given
modulus
with namevar
for the generator.Assumes that
modulus
is an irreducible polynomial over the finite field \(\mathbf{F}_{p}\) inctxp
.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
file
. Returns 1 for a success and a negative number for an error.
Memory management¶
-
void fq_init(fq_t rop, const fq_ctx_t ctx)¶
Initialises the element
rop
, setting its value to \(0\).
-
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¶
-
int fq_sqrt(fq_t rop, const fq_t op1, const fq_ctx_t ctx)¶
Sets
rop
to the square root ofop1
if it is a square, and return \(1\), otherwise return \(0\).
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\).
-
void fq_randtest_not_zero(fq_t rop, flint_rand_t state, const fq_ctx_t ctx)¶
Generates a random non-zero element of \(\mathbf{F}_q\).
-
void fq_randtest_dense(fq_t rop, flint_rand_t state, const fq_ctx_t ctx)¶
Generates a random element of \(\mathbf{F}_q\) which has an underlying polynomial with dense coefficients.
-
void fq_rand(fq_t rop, flint_rand_t state, const fq_ctx_t ctx)¶
Generates a high quality random element of \(\mathbf{F}_q\).
-
void fq_rand_not_zero(fq_t rop, flint_rand_t state, const fq_ctx_t ctx)¶
Generates a high quality non-zero 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\).
-
void fq_set_fmpz(fq_t rop, const fmpz_t x, const fq_ctx_t ctx)¶
Sets
rop
tox
, considered as an element of \(\mathbf{F}_p\).
-
void fq_gen(fq_t rop, const fq_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_get_fmpz(fmpz_t rop, const fq_t op, const fq_ctx_t ctx)¶
If
op
has a lift to the integers, return \(1\) and setrop
to the lift in \([0,p)\). Otherwise, return \(0\) and leave \(rop\) undefined.
-
void fq_get_fmpz_poly(fmpz_poly_t a, const fq_t b, const fq_ctx_t ctx)¶
-
void fq_get_fmpz_mod_poly(fmpz_mod_poly_t a, const fq_t b, const fq_ctx_t ctx)¶
Set
a
to a representative ofb
inctx
. The representatives are taken in \((\mathbb{Z}/p\mathbb{Z})[x]/h(x)\) where \(h(x)\) is the defining polynomial inctx
.
-
void fq_set_fmpz_poly(fq_t a, const fmpz_poly_t b, const fq_ctx_t ctx)¶
-
void fq_set_fmpz_mod_poly(fq_t a, const fmpz_mod_poly_t b, const fq_ctx_t ctx)¶
Set
a
to the element inctx
with representativeb
. The representatives are taken in \((\mathbb{Z}/p\mathbb{Z})[x]/h(x)\) where \(h(x)\) is the defining polynomial inctx
.
-
void fq_get_fmpz_mod_mat(fmpz_mod_mat_t col, const fq_t a, const fq_ctx_t ctx)¶
Convert
a
to a column vector of lengthdegree(ctx)
.
-
void fq_set_fmpz_mod_mat(fq_t a, const fmpz_mod_mat_t col, const fq_ctx_t ctx)¶
Convert a column vector
col
of lengthdegree(ctx)
to an element ofctx
.
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 \(\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_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 \(\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_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 \operatorname{Gal}(\mathbf{F}_q/\mathbf{F}_p)\) is the Frobenius element \(\sigma \colon x \mapsto x^p\).
-
int fq_multiplicative_order(fmpz_t ord, const fq_t op, const fq_ctx_t ctx)¶
Computes the order of
op
as an element of the multiplicative group ofctx
.Returns 0 if
op
is 0, otherwise it returns 1 ifop
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.