Data.Number.Flint.Fq.Zech

Finite fields (Zech logarithm representation)

data FqZech

Constructors

FqZech !(ForeignPtr CFqZech)

Instances

Storable CFqZech

Defined in Data.Number.Flint.Fq.Zech.FFI

Methods

sizeOf :: CFqZech -> Int

alignment :: CFqZech -> Int

peekElemOff :: Ptr CFqZech -> Int -> IO CFqZech

pokeElemOff :: Ptr CFqZech -> Int -> CFqZech -> IO ()

peekByteOff :: Ptr b -> Int -> IO CFqZech

pokeByteOff :: Ptr b -> Int -> CFqZech -> IO ()

peek :: Ptr CFqZech -> IO CFqZech

poke :: Ptr CFqZech -> CFqZech -> IO ()

type CFqZech = CFlint FqZech

newFqZech :: FqZechCtx -> IO FqZech

withFqZech :: FqZech -> (Ptr CFqZech -> IO a) -> IO (FqZech, a)

Context

data FqZechCtx

Constructors

FqZechCtx !(ForeignPtr CFqZechCtx)

Instances

Storable CFqZechCtx

Defined in Data.Number.Flint.Fq.Zech.FFI

Methods

sizeOf :: CFqZechCtx -> Int

alignment :: CFqZechCtx -> Int

peekElemOff :: Ptr CFqZechCtx -> Int -> IO CFqZechCtx

pokeElemOff :: Ptr CFqZechCtx -> Int -> CFqZechCtx -> IO ()

peekByteOff :: Ptr b -> Int -> IO CFqZechCtx

pokeByteOff :: Ptr b -> Int -> CFqZechCtx -> IO ()

peek :: Ptr CFqZechCtx -> IO CFqZechCtx

poke :: Ptr CFqZechCtx -> CFqZechCtx -> IO ()

type CFqZechCtx = CFlint FqZechCtx

create new context

newFqZechCtx :: Fmpz -> CLong -> String -> IO FqZechCtx

newFqZechCtxConway :: Fmpz -> CLong -> String -> IO FqZechCtx

newFqZechCtxRandom :: Fmpz -> CLong -> String -> IO FqZechCtx

newFqZechCtxModulus :: p -> NModPoly -> String -> IO FqZechCtx

newFqZechCtxModulusCheck :: p -> NModPoly -> String -> IO FqZechCtx

newFqZechCtxFqNModCtx :: p -> FqNModCtx -> IO FqZechCtx

newFqZechCtxFqNModCtxCheck :: p -> FqNModCtx -> IO FqZechCtx

work with context

withFqZechCtx :: FqZechCtx -> (Ptr CFqZechCtx -> IO a) -> IO (FqZechCtx, a)

Context Management

fq_zech_ctx_init :: Ptr CFqZechCtx -> Ptr CFmpz -> CLong -> CString -> IO ()

fq_zech_ctx_init ctx p d 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 primitive polynomial will be used.

Assumes that $p$ is a prime and $p^d < 2^{\mathtt{FLINT\_BITS}}$.

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

_fq_zech_ctx_init_conway :: Ptr CFqZechCtx -> Ptr CFmpz -> CLong -> CString -> IO CInt

_fq_zech_ctx_init_conway ctx p d 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 and $p^d < 2^\mathtt{FLINT\_BITS}$.

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

fq_zech_ctx_init_conway :: Ptr CFqZechCtx -> Ptr CFmpz -> CLong -> CString -> IO ()

fq_zech_ctx_init_conway ctx p d 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 and $p^d < 2^\mathtt{FLINT\_BITS}$.

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

fq_zech_ctx_init_random :: Ptr CFqZechCtx -> Ptr CFmpz -> CLong -> CString -> IO ()

fq_zech_ctx_init_random ctx p d var

Initialises the context for prime $p$ and extension degree $d$, with name var for the generator using a random primitive polynomial.

Assumes that $p$ is a prime and $p^d < 2^\mathtt{FLINT\_BITS}$.

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

fq_zech_ctx_init_modulus :: Ptr CFqZechCtx -> Ptr CNModPoly -> CString -> IO ()

fq_zech_ctx_init_modulus ctx modulus var

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

Assumes that modulus is an primitive polynomial over $\mathbf{F}_{p}$. An exception is raised if a non-primitive modulus is detected.

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

fq_zech_ctx_init_modulus_check :: Ptr CFqZechCtx -> Ptr CNModPoly -> CString -> IO CInt

fq_zech_ctx_init_modulus_check ctx modulus var

As per the previous function, but returns $0$ if the modulus was not primitive and $1$ if the context was successfully initialised with the given modulus. No exception is raised.

fq_zech_ctx_init_fq_nmod_ctx :: Ptr CFqZechCtx -> Ptr CFqNModCtx -> IO ()

fq_zech_ctx_init_fq_nmod_ctx ctx ctxn

Initializes the context ctx to be the Zech representation for the finite field given by ctxn.

fq_zech_ctx_init_fq_nmod_ctx_check :: Ptr CFqZechCtx -> Ptr CFqNModCtx -> IO CInt

fq_zech_ctx_init_fq_nmod_ctx_check ctx ctxn

As per the previous function but returns $0$ if a non-primitive modulus is detected. Returns $0$ if the Zech representation was successfully initialised.

fq_zech_ctx_clear :: Ptr CFqZechCtx -> IO ()

fq_zech_ctx_clear ctx

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

fq_zech_ctx_modulus :: Ptr CFqZechCtx -> IO (Ptr (Ptr CNModPoly))

fq_zech_ctx_modulus ctx

Returns a pointer to the modulus in the context.

fq_zech_ctx_degree :: Ptr CFqZechCtx -> IO CLong

fq_zech_ctx_degree ctx

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

fq_zech_ctx_order :: Ptr CFmpz -> Ptr CFqZechCtx -> IO ()

fq_zech_ctx_order f ctx

Sets $f$ to be the size of the finite field.

fq_zech_ctx_order_ui :: Ptr CFqZechCtx -> IO CMpLimb

fq_zech_ctx_order_ui ctx

Returns the size of the finite field.

fq_zech_ctx_get_str :: Ptr CFqZechCtx -> IO CString

fq_zech_ctx_fprint :: Ptr CFile -> Ptr CFqZechCtx -> IO CInt

fq_zech_ctx_fprint file ctx

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

fq_zech_ctx_print :: Ptr CFqZechCtx -> IO ()

fq_zech_ctx_print ctx

Prints the context information to {tt{stdout}}.

fq_zech_ctx_randtest :: Ptr CFqZechCtx -> IO ()

fq_zech_ctx_randtest ctx

Initializes ctx to a random finite field. Assumes that fq_zech_ctx_init has not been called on ctx already.

fq_zech_ctx_randtest_reducible :: Ptr CFqZechCtx -> IO ()

fq_zech_ctx_randtest_reducible ctx

Since the Zech logarithm representation does not work with a non-irreducible modulus, does the same as fq_zech_ctx_randtest.

Memory management

fq_zech_init :: Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_init rop ctx

Initialises the element rop, setting its value to $0$.

fq_zech_init2 :: Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_init2 rop ctx

Initialises poly with at least enough space for it to be an element of ctx and sets it to $0$.

fq_zech_clear :: Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_clear rop ctx

Clears the element rop.

fq_zech_reduce :: Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_reduce rop ctx

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

Basic arithmetic

fq_zech_add :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_add rop op1 op2 ctx

Sets rop to the sum of op1 and op2.

fq_zech_sub :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_sub rop op1 op2 ctx

Sets rop to the difference of op1 and op2.

fq_zech_sub_one :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_sub_one rop op1 ctx

Sets rop to the difference of op1 and $1$.

fq_zech_neg :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_neg rop op ctx

Sets rop to the negative of op.

fq_zech_mul :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_mul rop op1 op2 ctx

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

fq_zech_mul_fmpz :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFmpz -> Ptr CFqZechCtx -> IO ()

fq_zech_mul_fmpz rop op x ctx

Sets rop to the product of op and $x$, reducing the output in the given context.

fq_zech_mul_si :: Ptr CFqZech -> Ptr CFqZech -> CLong -> Ptr CFqZechCtx -> IO ()

fq_zech_mul_si rop op x ctx

Sets rop to the product of op and $x$, reducing the output in the given context.

fq_zech_mul_ui :: Ptr CFqZech -> Ptr CFqZech -> CULong -> Ptr CFqZechCtx -> IO ()

fq_zech_mul_ui rop op x ctx

Sets rop to the product of op and $x$, reducing the output in the given context.

fq_zech_sqr :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_sqr rop op ctx

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

fq_zech_div :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_div rop op1 op2 ctx

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

fq_zech_inv :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_inv rop op ctx

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

fq_zech_gcdinv :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_gcdinv f inv op ctx

Sets inv to be the inverse of op modulo the modulus of ctx and sets f to one. Since the modulus for ctx is always irreducible, op is always invertible.

fq_zech_pow :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFmpz -> Ptr CFqZechCtx -> IO ()

fq_zech_pow rop op e ctx

Sets rop the 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$.

fq_zech_pow_ui :: Ptr CFqZech -> Ptr CFqZech -> CULong -> Ptr CFqZechCtx -> IO ()

fq_zech_pow_ui rop op e ctx

Sets rop the 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

fq_zech_sqrt :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_sqrt rop op1 ctx

Sets rop to the square root of op1 if it is a square, and return $1$, otherwise return $0$.

fq_zech_pth_root :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_pth_root rop op1 ctx

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

fq_zech_is_square :: Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_is_square op ctx

Return 1 if op is a square.

Output

fq_zech_fprint_pretty :: Ptr CFile -> Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_fprint_pretty file op ctx

Prints a pretty representation of op to file.

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.

fq_zech_print_pretty :: Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_print_pretty op ctx

Prints a pretty representation of op to stdout.

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.

fq_zech_fprint :: Ptr CFile -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_fprint file op ctx

Prints a representation of op to file.

fq_zech_print :: Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_print op ctx

Prints a representation of op to stdout.

fq_zech_get_str :: Ptr CFqZech -> Ptr CFqZechCtx -> IO CString

fq_zech_get_str op ctx

Returns the plain FLINT string representation of the element op.

fq_zech_get_str_pretty :: Ptr CFqZech -> Ptr CFqZechCtx -> IO CString

fq_zech_get_str_pretty op ctx

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

Randomisation

fq_zech_randtest :: Ptr CFqZech -> Ptr CFRandState -> Ptr CFqZechCtx -> IO ()

fq_zech_randtest rop state ctx

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

fq_zech_randtest_not_zero :: Ptr CFqZech -> Ptr CFRandState -> Ptr CFqZechCtx -> IO ()

fq_zech_randtest_not_zero rop state ctx

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

fq_zech_rand :: Ptr CFqZech -> Ptr CFRandState -> Ptr CFqZechCtx -> IO ()

fq_zech_rand rop state ctx

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

fq_zech_rand_not_zero :: Ptr CFqZech -> Ptr CFRandState -> Ptr CFqZechCtx -> IO ()

fq_zech_rand_not_zero rop state ctx

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

Assignments and conversions

fq_zech_set :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_set rop op ctx

Sets rop to op.

fq_zech_set_si :: Ptr CFqZech -> CLong -> Ptr CFqZechCtx -> IO ()

fq_zech_set_si rop x ctx

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

fq_zech_set_ui :: Ptr CFqZech -> CULong -> Ptr CFqZechCtx -> IO ()

fq_zech_set_ui rop x ctx

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

fq_zech_set_fmpz :: Ptr CFqZech -> Ptr CFmpz -> Ptr CFqZechCtx -> IO ()

fq_zech_set_fmpz rop x ctx

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

fq_zech_swap :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_swap op1 op2 ctx

Swaps the two elements op1 and op2.

fq_zech_zero :: Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_zero rop ctx

Sets rop to zero.

fq_zech_one :: Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_one rop ctx

Sets rop to one, reduced in the given context.

fq_zech_gen :: Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_gen rop ctx

Sets rop to a generator for the finite field. There is no guarantee this is a multiplicative generator of the finite field.

fq_zech_get_fmpz :: Ptr CFmpz -> Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_get_fmpz rop op 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.

fq_zech_get_fq_nmod :: Ptr CFqNMod -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_get_fq_nmod rop op ctx

Sets rop to the fq_nmod_t element corresponding to op.

fq_zech_set_fq_nmod :: Ptr CFqZech -> Ptr CFqNMod -> Ptr CFqZechCtx -> IO ()

fq_zech_set_fq_nmod rop op ctx

Sets rop to the fq_zech_t element corresponding to op.

fq_zech_get_nmod_poly :: Ptr CNModPoly -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_get_nmod_poly a b 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.

fq_zech_set_nmod_poly :: Ptr CFqZech -> Ptr CNModPoly -> Ptr CFqZechCtx -> IO ()

fq_zech_set_nmod_poly a b 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.

fq_zech_get_nmod_mat :: Ptr CNModMat -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_get_nmod_mat col a ctx

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

fq_zech_set_nmod_mat :: Ptr CFqZech -> Ptr CNModMat -> Ptr CFqZechCtx -> IO ()

fq_zech_set_nmod_mat a col ctx

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

Comparison

fq_zech_is_zero :: Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_is_zero op ctx

Returns whether op is equal to zero.

fq_zech_is_one :: Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_is_one op ctx

Returns whether op is equal to one.

fq_zech_equal :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_equal op1 op2 ctx

Returns whether op1 and op2 are equal.

fq_zech_is_invertible :: Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_is_invertible op ctx

Returns whether op is an invertible element.

fq_zech_is_invertible_f :: Ptr CFqZech -> Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_is_invertible_f f op ctx

Returns whether op is an invertible element. If it is not, then f is set of a factor of the modulus. Since the modulus for an fq_zech_ctx_t is always irreducible, then any non-zero op will be invertible.

Special functions

fq_zech_trace :: Ptr CFmpz -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_trace rop op 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).

fq_zech_norm :: Ptr CFmpz -> Ptr CFqZech -> Ptr CFqZechCtx -> IO ()

fq_zech_norm rop op 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.

fq_zech_frobenius :: Ptr CFqZech -> Ptr CFqZech -> CLong -> Ptr CFqZechCtx -> IO ()

fq_zech_frobenius rop op e 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$.

fq_zech_multiplicative_order :: Ptr CFmpz -> Ptr CFqZech -> Ptr CFqZechCtx -> IO CInt

fq_zech_multiplicative_order ord op 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.

Note that ctx must already correspond to a finite field defined by a primitive polynomial and so this function cannot be used to check primitivity of the generator, but can be used to check that other elements are primitive.

Bit packing

fq_zech_bit_pack :: Ptr CFmpz -> Ptr CFqZech -> CFBitCnt -> Ptr CFqZechCtx -> IO ()

fq_zech_bit_pack f op bit_size ctx

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

fq_zech_bit_unpack :: Ptr CFqZech -> Ptr CFmpz -> CFBitCnt -> Ptr CFqZechCtx -> IO ()

fq_zech_bit_unpack rop f bit_size ctx

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