fq_default.h – unified finite fields¶
Types, macros and constants¶
-
type fq_default_ctx_t¶
-
type fq_default_t¶
Context Management¶
-
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 stringvar
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 argumenttype
is required which sets which representation to use. These values can be:0
(which then will act just likefq_default_ctx_init
),FQ_DEFAULT_FQ_ZECH
,FQ_DEFAULT_FQ_NMOD
,FQ_DEFAULT_FQ
,FQ_DEFAULT_NMOD
andFQ_DEFAULT_FMPZ_MOD
.
-
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 polynomialmodulus
. For thefmpz_mod_poly
type, the context structuremod_ctx
for the polynomial must also be given. Sets the printing of variable of the field to the stringvar
, 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
andfq
.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
orfq_default_ctx_init_modulus
, it chooses the best representation for performance.For
fq_default_ctx_init_modulus_nmod_type
orfq_default_ctx_init_modulus_type
, it expectstype
to be one of the following choices:FQ_DEFAULT_FQ_ZECH
,FQ_DEFAULT_FQ_NMOD
,FQ_DEFAULT_FQ
,FQ_DEFAULT_NMOD
orFQ_DEFAULT_FMPZ_MOD
. To be clear: if the Zech logarithm is chosen but the polynomial is not primitive, another representation will be chosen.
-
void fq_default_ctx_clear(fq_default_ctx_t ctx)¶
Clears all memory that has been allocated as part of the context.
-
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 anfq_mod
context and \(3\) if it contains anfq
context.
-
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.
-
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\).
-
void fq_default_ctx_prime(fmpz_t prime, const fq_default_ctx_t ctx)¶
Sets \(prime\) to the prime \(p\) in the context.
-
void fq_default_ctx_order(fmpz_t f, const fq_default_ctx_t ctx)¶
Sets \(f\) to be the size of the finite field.
-
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..
-
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.
-
void fq_default_ctx_print(const fq_default_ctx_t ctx)¶
Prints the context information to
stdout
.
-
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 thatfq_default_ctx_init
has not been called onctx
already.
-
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¶
-
void fq_default_init(fq_default_t rop, const fq_default_ctx_t ctx)¶
Initialises the element
rop
, setting its value to \(0\).
-
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 ofctx
and sets it to \(0\).
-
void fq_default_clear(fq_default_t rop, const fq_default_ctx_t ctx)¶
Clears the element
rop
.
Predicates¶
-
int fq_default_is_invertible(const fq_default_t op, const fq_default_ctx_t ctx)¶
Return
1
ifop
is an invertible element.
Basic arithmetic¶
-
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 ofop1
andop2
.
-
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 ofop1
andop2
.
-
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 ofop1
and \(1\).
-
void fq_default_neg(fq_default_t rop, const fq_default_t op, const fq_default_ctx_t ctx)¶
Sets
rop
to the negative ofop
.
-
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 ofop1
andop2
, reducing the output in the given context.
-
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 ofop
and \(x\), reducing the output in the given context.
-
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 ofop
and \(x\), reducing the output in the given context.
-
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 ofop
and \(x\), reducing the output in the given context.
-
void fq_default_sqr(fq_default_t rop, const fq_default_t op, const fq_default_ctx_t ctx)¶
Sets
rop
to the square ofop
, reducing the output in the given context.
-
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 ofop1
andop2
, reducing the output in the given context.
-
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 elementop
.
-
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
theop
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_default_pow_ui(fq_default_t rop, const fq_default_t op, const ulong e, const fq_default_ctx_t ctx)¶
Sets
rop
theop
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_default_sqrt(fq_default_t rop, const fq_default_t op1, const fq_default_ctx_t ctx)¶
Sets
rop
to the square root ofop1
if it is a square, and return \(1\), otherwise return \(0\).
-
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 ofop1
. Currently, this computes the root by raisingop1
to \(p^{d-1}\) where \(d\) is the degree of the extension.
-
int fq_default_is_square(const fq_default_t op, const fq_default_ctx_t ctx)¶
Return
1
ifop
is a square.
Output¶
-
int fq_default_fprint_pretty(FILE *file, const fq_default_t op, const fq_default_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.
-
void fq_default_print_pretty(const fq_default_t op, const fq_default_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.
-
int fq_default_fprint(FILE *file, const fq_default_t op, const fq_default_ctx_t ctx)¶
Prints a representation of
op
tofile
.
-
void fq_default_print(const fq_default_t op, const fq_default_ctx_t ctx)¶
Prints a representation of
op
tostdout
.
-
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
.
-
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 stringx
as the variable name.
Randomisation¶
-
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\).
-
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\).
-
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\).
-
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¶
-
void fq_default_set(fq_default_t rop, const fq_default_t op, const fq_default_ctx_t ctx)¶
Sets
rop
toop
.
-
void fq_default_set_si(fq_default_t rop, const slong x, const fq_default_ctx_t ctx)¶
Sets
rop
tox
, considered as an element of \(\mathbf{F}_p\).
-
void fq_default_set_ui(fq_default_t rop, const ulong x, const fq_default_ctx_t ctx)¶
Sets
rop
tox
, considered as an element of \(\mathbf{F}_p\).
-
void fq_default_set_fmpz(fq_default_t rop, const fmpz_t x, const fq_default_ctx_t ctx)¶
Sets
rop
tox
, considered as an element of \(\mathbf{F}_p\).
-
void fq_default_swap(fq_default_t op1, fq_default_t op2, const fq_default_ctx_t ctx)¶
Swaps the two elements
op1
andop2
.
-
void fq_default_zero(fq_default_t rop, const fq_default_ctx_t ctx)¶
Sets
rop
to zero.
-
void fq_default_one(fq_default_t rop, const fq_default_ctx_t ctx)¶
Sets
rop
to one, reduced in the given context.
-
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.
-
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 setrop
to the lift in \([0,p)\). Otherwise, return \(0\) and leave \(rop\) undefined.
-
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 ofop
. Assumes the characteristic of the field and the modulus of the polynomial are the same. No checking of this occurs.
-
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 polynomialpoly
. Assumes the characteristic of the field and the modulus of the polynomial are the same. No checking of this occurs.
-
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 ofop
. Assumes the characteristic of the field and the modulus of the polynomial are the same. No checking of this occurs.
-
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 polynomialpoly
. Assumes the characteristic of the field and the modulus of the polynomial are the same. No checking of this occurs.
-
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 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_default_set_fmpz_poly(fq_default_t a, const fmpz_poly_t b, const fq_default_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
.
Comparison¶
-
int fq_default_is_zero(const fq_default_t op, const fq_default_ctx_t ctx)¶
Returns whether
op
is equal to zero.
-
int fq_default_is_one(const fq_default_t op, const fq_default_ctx_t ctx)¶
Returns whether
op
is equal to one.
-
int fq_default_equal(const fq_default_t op1, const fq_default_t op2, const fq_default_ctx_t ctx)¶
Returns whether
op1
andop2
are equal.
Special functions¶
-
void fq_default_trace(fmpz_t rop, const fq_default_t op, const fq_default_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_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.
-
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\).