Data.Number.Flint.Fq

Finite fields

This module implements operations over the finite field \(\mathbb F_q\) where \( q = p^d \) with \(p\) prime.

Basic usage

Consider the finite field \(\mathbb F_{11^4}\). Here we initialize the context and set x to the generator of the field and print it and its fourth power.

import Data.Number.Flint

main = do
  ctx <- newFqCtx 11 4 "alpha"
  withNewFq ctx $ \x -> do 
    withFqCtx ctx $ \ctx -> do
      fq_ctx_print ctx
      putStr "\n"
      fq_gen x ctx
      fq_print_pretty x ctx
      putStr "\n"
      fq_pow_ui x x 4 ctx
      fq_print_pretty x ctx
      putStr "\n"

Running main yields:

>>> main
p = 11
d = 4
f(X) = X^4+8*X^2+10*X+2

alpha 
3*alpha^2+alpha+9

Finite fields

Finite field element

The type Fq represents an element of the finite field \(\mathbb F_q\).

data Fq

Constructors

Fq !(ForeignPtr CFq)

type CFq = CFmpzPoly

newFq :: FqCtx -> IO Fq

Create a new Fq with context ctx.

withFq :: Fq -> (Ptr CFq -> IO a) -> IO (Fq, a)

Use Fq.

withNewFq :: FqCtx -> (Ptr CFq -> IO a) -> IO (Fq, a)

Use a new Fq.

Finite field context

data FqCtx

Context of the finite field (opaque pointer)

Constructors

FqCtx !(ForeignPtr CFqCtx)

Instances

Storable CFqCtx

Defined in Data.Number.Flint.Fq.FFI

Methods

sizeOf :: CFqCtx -> Int

alignment :: CFqCtx -> Int

peekElemOff :: Ptr CFqCtx -> Int -> IO CFqCtx

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

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

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

peek :: Ptr CFqCtx -> IO CFqCtx

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

type CFqCtx = CFlint FqCtx

newFqCtx :: Fmpz -> CLong -> String -> IO FqCtx

Create a new Fq context using fq_ctx_init.

withFqCtx :: FqCtx -> (Ptr CFqCtx -> IO a) -> IO (FqCtx, a)

Use the FqCtx.

withNewFqCtx :: Fmpz -> CLong -> String -> (Ptr CFqCtx -> IO a) -> IO (FqCtx, a)

Apply function to new FqCtx. parameters as in newFqCtx.

newFqCtxConway :: Fmpz -> CLong -> String -> IO FqCtx

Create a new Fq context using fq_ctx_init_conway.

withNewFqCtxConway :: Fmpz -> CLong -> String -> (Ptr CFqCtx -> IO a) -> IO (FqCtx, a)

Apply function to new Fq initialized with fq_ctx_init_conway.

newFqCtxModulus :: FmpzModPoly -> FmpzModCtx -> String -> IO FqCtx

Create a new Fq context using fq_ctx_init_modulus.

withNewFqCtxModulus :: FmpzModPoly -> FmpzModCtx -> String -> (Ptr CFqCtx -> IO a) -> IO (FqCtx, a)

Create a new Fq initialized using fq_ctx_init_modulus.

Context Management

fq_ctx_init :: Ptr CFqCtx -> Ptr CFmpz -> CLong -> CString -> IO ()

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

_fq_ctx_init_conway :: Ptr CFqCtx -> Ptr CFmpz -> CLong -> CString -> IO CInt

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

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

fq_ctx_init_conway :: Ptr CFqCtx -> Ptr CFmpz -> CLong -> CString -> IO ()

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

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

fq_ctx_init_modulus :: Ptr CFqCtx -> Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> CString -> IO ()

fq_ctx_init_modulus ctx modulus ctxp var

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

Assumes that modulus is an irreducible polynomial over the finite field \(\mathbf{F}_{p}\) in ctxp.

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

fq_ctx_clear :: Ptr CFqCtx -> IO ()

fq_ctx_clear ctx

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

fq_ctx_modulus :: Ptr CFqCtx -> IO (Ptr CFmpzModPoly)

fq_ctx_modulus ctx

Returns a pointer to the modulus in the context.

fq_ctx_degree :: Ptr CFqCtx -> IO CLong

fq_ctx_degree ctx

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

fq_ctx_prime :: Ptr CFqCtx -> IO (Ptr CFmpz)

fq_ctx_prime ctx

Returns a pointer to the prime \(p\) in the context.

fq_ctx_order :: Ptr CFmpz -> Ptr CFqCtx -> IO ()

fq_ctx_order f ctx

Sets \(f\) to be the size of the finite field.

fq_ctx_get_str :: Ptr CFqCtx -> IO CString

fq_ctx_fprint :: Ptr CFile -> Ptr CFqCtx -> IO CInt

fq_ctx_fprint file ctx

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

fq_ctx_print :: Ptr CFqCtx -> IO ()

fq_ctx_print ctx

Prints the context information to stdout.

fq_ctx_randtest :: Ptr CFqCtx -> IO ()

fq_ctx_randtest ctx

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

fq_ctx_randtest_reducible :: Ptr CFqCtx -> IO ()

fq_ctx_randtest_reducible ctx

Initializes ctx to a random extension of a prime field. The modulus may or may not be irreducible. Assumes that fq_ctx_init has not been called on ctx already.

Memory management

fq_init :: Ptr CFq -> Ptr CFqCtx -> IO ()

fq_init rop ctx

Initialises the element rop, setting its value to \(0\).

fq_init2 :: Ptr CFq -> Ptr CFqCtx -> IO ()

fq_init2 rop ctx

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

fq_clear :: Ptr CFq -> Ptr CFqCtx -> IO ()

fq_clear rop ctx

Clears the element rop.

_fq_sparse_reduce :: Ptr CFmpz -> CLong -> Ptr CFqCtx -> IO ()

_fq_sparse_reduce R lenR ctx

Reduces (R, lenR) modulo the polynomial \(f\) given by the modulus of ctx.

_fq_dense_reduce :: Ptr CFmpz -> CLong -> Ptr CFqCtx -> IO ()

_fq_dense_reduce R lenR ctx

Reduces (R, lenR) modulo the polynomial \(f\) given by the modulus of ctx using Newton division.

_fq_reduce :: Ptr CFmpz -> CLong -> Ptr CFqCtx -> IO ()

_fq_reduce r lenR 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.

fq_reduce :: Ptr CFq -> Ptr CFqCtx -> IO ()

fq_reduce rop ctx

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

Basic arithmetic

fq_add :: Ptr CFq -> Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_add rop op1 op2 ctx

Sets rop to the sum of op1 and op2.

fq_sub :: Ptr CFq -> Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_sub rop op1 op2 ctx

Sets rop to the difference of op1 and op2.

fq_sub_one :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_sub_one rop op1 ctx

Sets rop to the difference of op1 and \(1\).

fq_neg :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_neg rop op ctx

Sets rop to the negative of op.

fq_mul :: Ptr CFq -> Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_mul rop op1 op2 ctx

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

fq_mul_fmpz :: Ptr CFq -> Ptr CFq -> Ptr CFmpz -> Ptr CFqCtx -> IO ()

fq_mul_fmpz rop op x ctx

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

fq_mul_si :: Ptr CFq -> Ptr CFq -> CLong -> Ptr CFqCtx -> IO ()

fq_mul_si rop op x ctx

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

fq_mul_ui :: Ptr CFq -> Ptr CFq -> CULong -> Ptr CFqCtx -> IO ()

fq_mul_ui rop op x ctx

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

fq_sqr :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_sqr rop op ctx

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

fq_div :: Ptr CFq -> Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_div rop op1 op2 ctx

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

_fq_inv :: Ptr CFmpz -> Ptr CFmpz -> CLong -> Ptr CFqCtx -> IO ()

_fq_inv rop op len ctx

Sets (rop, d) to the inverse of the non-zero element (op, len).

fq_inv :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_inv rop op ctx

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

fq_gcdinv :: Ptr CFq -> Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_gcdinv f inv op 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.

_fq_pow :: Ptr CFmpz -> Ptr CFmpz -> CLong -> Ptr CFmpz -> Ptr CFqCtx -> IO ()

_fq_pow rop op len e 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.

fq_pow :: Ptr CFq -> Ptr CFq -> Ptr CFmpz -> Ptr CFqCtx -> IO ()

fq_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_pow_ui :: Ptr CFq -> Ptr CFq -> CULong -> Ptr CFqCtx -> IO ()

fq_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_sqrt :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_sqrt rop op1 ctx

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

fq_pth_root :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_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_is_square :: Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_is_square op ctx

Return 1 if op is a square.

Output

fq_fprint_pretty :: Ptr CFile -> Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_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_print_pretty :: Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_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_fprint :: Ptr CFile -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_fprint file op ctx

Prints a representation of op to file.

For further details on the representation used, see fmpz_mod_poly_fprint.

fq_print :: Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_print op ctx

Prints a representation of op to stdout.

For further details on the representation used, see fmpz_mod_poly_print.

fq_get_str :: Ptr CFq -> Ptr CFqCtx -> IO CString

fq_get_str op ctx

Returns the plain FLINT string representation of the element op.

fq_get_str_pretty :: Ptr CFq -> Ptr CFqCtx -> IO CString

fq_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_randtest :: Ptr CFq -> Ptr CFRandState -> Ptr CFqCtx -> IO ()

fq_randtest rop state ctx

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

fq_randtest_not_zero :: Ptr CFq -> Ptr CFRandState -> Ptr CFqCtx -> IO ()

fq_randtest_not_zero rop state ctx

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

fq_randtest_dense :: Ptr CFq -> Ptr CFRandState -> Ptr CFqCtx -> IO ()

fq_randtest_dense rop state ctx

Generates a random element of \(\mathbf{F}_q\) which has an underlying polynomial with dense coefficients.

fq_rand :: Ptr CFq -> Ptr CFRandState -> Ptr CFqCtx -> IO ()

fq_rand rop state ctx

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

fq_rand_not_zero :: Ptr CFq -> Ptr CFRandState -> Ptr CFqCtx -> IO ()

fq_rand_not_zero rop state ctx

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

Assignments and conversions

fq_set :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_set rop op ctx

Sets rop to op.

fq_set_si :: Ptr CFq -> CLong -> Ptr CFqCtx -> IO ()

fq_set_si rop x ctx

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

fq_set_ui :: Ptr CFq -> CULong -> Ptr CFqCtx -> IO ()

fq_set_ui rop x ctx

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

fq_set_fmpz :: Ptr CFq -> Ptr CFmpz -> Ptr CFqCtx -> IO ()

fq_set_fmpz rop x ctx

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

fq_swap :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_swap op1 op2 ctx

Swaps the two elements op1 and op2.

fq_zero :: Ptr CFq -> Ptr CFqCtx -> IO ()

fq_zero rop ctx

Sets rop to zero.

fq_one :: Ptr CFq -> Ptr CFqCtx -> IO ()

fq_one rop ctx

Sets rop to one, reduced in the given context.

fq_gen :: Ptr CFq -> Ptr CFqCtx -> IO ()

fq_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_get_fmpz :: Ptr CFmpz -> Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_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_get_fmpz_poly :: Ptr CFmpzPoly -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_get_fmpz_mod_poly :: Ptr CFmpzModPoly -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_get_fmpz_mod_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_set_fmpz_poly :: Ptr CFq -> Ptr CFmpzPoly -> Ptr CFqCtx -> IO ()

fq_set_fmpz_mod_poly :: Ptr CFq -> Ptr CFmpzModPoly -> Ptr CFqCtx -> IO ()

fq_set_fmpz_mod_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_get_fmpz_mod_mat :: Ptr CFmpzModMat -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_get_fmpz_mod_mat col a ctx

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

fq_set_fmpz_mod_mat :: Ptr CFq -> Ptr CFmpzModMat -> Ptr CFqCtx -> IO ()

fq_set_fmpz_mod_mat a col ctx

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

Comparison

fq_is_zero :: Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_is_zero op ctx

Returns whether op is equal to zero.

fq_is_one :: Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_is_one op ctx

Returns whether op is equal to one.

fq_equal :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_equal op1 op2 ctx

Returns whether op1 and op2 are equal.

fq_is_invertible :: Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_is_invertible op ctx

Returns whether op is an invertible element.

fq_is_invertible_f :: Ptr CFq -> Ptr CFq -> Ptr CFqCtx -> IO CInt

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

Special functions

_fq_trace :: Ptr CFmpz -> Ptr CFmpz -> CLong -> Ptr CFqCtx -> IO ()

_fq_trace rop op len ctx

Sets rop to the trace of the non-zero element (op, len) in \(\mathbf{F}_{q}\).

fq_trace :: Ptr CFmpz -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_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_norm :: Ptr CFmpz -> Ptr CFmpz -> CLong -> Ptr CFqCtx -> IO ()

_fq_norm rop op len ctx

Sets rop to the norm of the non-zero element (op, len) in \(\mathbf{F}_{q}\).

fq_norm :: Ptr CFmpz -> Ptr CFq -> Ptr CFqCtx -> IO ()

fq_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_frobenius :: Ptr CFmpz -> Ptr CFmpz -> CLong -> CLong -> Ptr CFqCtx -> IO ()

_fq_frobenius rop op len e 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.

fq_frobenius :: Ptr CFq -> Ptr CFq -> CLong -> Ptr CFqCtx -> IO ()

fq_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_multiplicative_order :: Ptr CFmpz -> Ptr CFq -> Ptr CFqCtx -> IO CInt

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

This function can also be used to check primitivity of a generator of a finite field whose defining polynomial is not primitive.

fq_is_primitive :: Ptr CFq -> Ptr CFqCtx -> IO CInt

fq_is_primitive op ctx

Returns whether op is primitive, i.e., whether it is a generator of the multiplicative group of ctx.

Bit packing

fq_bit_pack :: Ptr CFmpz -> Ptr CFq -> CFBitCnt -> Ptr CFqCtx -> IO ()

fq_bit_pack f op bit_size ctx

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

fq_bit_unpack :: Ptr CFq -> Ptr CFmpz -> CFBitCnt -> Ptr CFqCtx -> IO ()

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