Data.Number.Flint.Fq.NMod.Poly

Univariate polynomials over finite fields (word-size characteristic)

data FqNModPoly

Constructors

FqNModPoly !(ForeignPtr CFqNModPoly)

Instances

Storable CFqNModPoly

Defined in Data.Number.Flint.Fq.NMod.Poly.FFI

Methods

sizeOf :: CFqNModPoly -> Int

alignment :: CFqNModPoly -> Int

peekElemOff :: Ptr CFqNModPoly -> Int -> IO CFqNModPoly

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

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

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

peek :: Ptr CFqNModPoly -> IO CFqNModPoly

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

type CFqNModPoly = CFlint FqNModPoly

newFqNModPoly :: FqNModCtx -> IO FqNModPoly

withFqNModPoly :: FqNModPoly -> (Ptr CFqNModPoly -> IO a) -> IO (FqNModPoly, a)

Memory management

fq_nmod_poly_init :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_init poly ctx

Initialises poly for use, with context ctx, and setting its length to zero. A corresponding call to fq_nmod_poly_clear must be made after finishing with the fq_nmod_poly_t to free the memory used by the polynomial.

fq_nmod_poly_init2 :: Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_init2 poly alloc ctx

Initialises poly with space for at least alloc coefficients and sets the length to zero. The allocated coefficients are all set to zero. A corresponding call to fq_nmod_poly_clear must be made after finishing with the fq_nmod_poly_t to free the memory used by the polynomial.

fq_nmod_poly_realloc :: Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_realloc poly alloc ctx

Reallocates the given polynomial to have space for alloc coefficients. If alloc is zero the polynomial is cleared and then reinitialised. If the current length is greater than alloc the polynomial is first truncated to length alloc.

fq_nmod_poly_fit_length :: Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_fit_length poly len ctx

If len is greater than the number of coefficients currently allocated, then the polynomial is reallocated to have space for at least len coefficients. No data is lost when calling this function.

The function efficiently deals with the case where fit_length is called many times in small increments by at least doubling the number of allocated coefficients when length is larger than the number of coefficients currently allocated.

_fq_nmod_poly_set_length :: Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_set_length poly newlen ctx

Sets the coefficients of poly beyond len to zero and sets the length of poly to len.

fq_nmod_poly_clear :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_clear poly ctx

Clears the given polynomial, releasing any memory used. It must be reinitialised in order to be used again.

_fq_nmod_poly_normalise :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_normalise poly ctx

Sets the length of poly so that the top coefficient is non-zero. If all coefficients are zero, the length is set to zero. This function is mainly used internally, as all functions guarantee normalisation.

_fq_nmod_poly_normalise2 :: Ptr (Ptr CFqNMod) -> Ptr CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_normalise2 poly length ctx

Sets the length length of (poly,length) so that the top coefficient is non-zero. If all coefficients are zero, the length is set to zero. This function is mainly used internally, as all functions guarantee normalisation.

fq_nmod_poly_truncate :: Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_truncate poly newlen ctx

Truncates the polynomial to length at most n.

fq_nmod_poly_set_trunc :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqCtx -> IO ()

fq_nmod_poly_set_trunc poly1 poly2 newlen ctx

Sets poly1 to poly2 truncated to length \(n\).

_fq_nmod_poly_reverse :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_reverse output input len m ctx

Sets output to the reverse of input, which is of length len, but thinking of it as a polynomial of length m, notionally zero-padded if necessary. The length m must be non-negative, but there are no other restrictions. The polynomial output must have space for m coefficients.

fq_nmod_poly_reverse :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_reverse output input m ctx

Sets output to the reverse of input, thinking of it as a polynomial of length m, notionally zero-padded if necessary). The length m must be non-negative, but there are no other restrictions. The output polynomial will be set to length m and then normalised.

Polynomial parameters

fq_nmod_poly_degree :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CLong

fq_nmod_poly_degree poly ctx

Returns the degree of the polynomial poly.

fq_nmod_poly_length :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CLong

fq_nmod_poly_length poly ctx

Returns the length of the polynomial poly.

fq_nmod_poly_lead :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO (Ptr (Ptr CFqNMod))

fq_nmod_poly_lead poly ctx

Returns a pointer to the leading coefficient of poly, or NULL if poly is the zero polynomial.

Randomisation

fq_nmod_poly_randtest :: Ptr CFqNModPoly -> Ptr CFRandState -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_randtest f state len ctx

Sets \(f\) to a random polynomial of length at most len with entries in the field described by ctx.

fq_nmod_poly_randtest_not_zero :: Ptr CFqNModPoly -> Ptr CFRandState -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_randtest_not_zero f state len ctx

Same as fq_nmod_poly_randtest but guarantees that the polynomial is not zero.

fq_nmod_poly_randtest_monic :: Ptr CFqNModPoly -> Ptr CFRandState -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_randtest_monic f state len ctx

Sets \(f\) to a random monic polynomial of length len with entries in the field described by ctx.

fq_nmod_poly_randtest_irreducible :: Ptr CFqNModPoly -> Ptr CFRandState -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_randtest_irreducible f state len ctx

Sets \(f\) to a random monic, irreducible polynomial of length len with entries in the field described by ctx.

Assignment and basic manipulation

_fq_nmod_poly_set :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_set rop op len ctx

Sets (rop, len) to (op, len).

fq_nmod_poly_set :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_set poly1 poly2 ctx

Sets the polynomial poly1 to the polynomial poly2.

fq_nmod_poly_set_fq_nmod :: Ptr CFqNModPoly -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_set_fq_nmod poly c ctx

Sets the polynomial poly to c.

fq_nmod_poly_set_fmpz_mod_poly :: Ptr CFqNModPoly -> Ptr CFmpzModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_set_fmpz_mod_poly rop op ctx

Sets the polynomial rop to the polynomial op

fq_nmod_poly_set_nmod_poly :: Ptr CFqNModPoly -> Ptr CNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_set_nmod_poly rop op ctx

Sets the polynomial rop to the polynomial op

fq_nmod_poly_swap :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_swap op1 op2 ctx

Swaps the two polynomials op1 and op2.

_fq_nmod_poly_zero :: Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_zero rop len ctx

Sets (rop, len) to the zero polynomial.

fq_nmod_poly_zero :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_zero poly ctx

Sets poly to the zero polynomial.

fq_nmod_poly_one :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_one poly ctx

Sets poly to the constant polynomial \(1\).

fq_nmod_poly_gen :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_gen poly ctx

Sets poly to the polynomial \(x\).

fq_nmod_poly_make_monic :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_make_monic rop op ctx

Sets rop to op, normed to have leading coefficient 1.

_fq_nmod_poly_make_monic :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_make_monic rop op length ctx

Sets rop to (op,length), normed to have leading coefficient 1. Assumes that rop has enough space for the polynomial, assumes that op is not zero (and thus has an invertible leading coefficient).

Getting and setting coefficients

fq_nmod_poly_get_coeff :: Ptr CFqNMod -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_get_coeff x poly n ctx

Sets \(x\) to the coefficient of \(X^n\) in poly.

fq_nmod_poly_set_coeff :: Ptr CFqNModPoly -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_set_coeff poly n x ctx

Sets the coefficient of \(X^n\) in poly to \(x\).

fq_nmod_poly_set_coeff_fmpz :: Ptr CFqNModPoly -> CLong -> Ptr CFmpz -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_set_coeff_fmpz poly n x ctx

Sets the coefficient of \(X^n\) in the polynomial to \(x\), assuming \(n \geq 0\).

Comparison

fq_nmod_poly_equal :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_equal poly1 poly2 ctx

Returns nonzero if the two polynomials poly1 and poly2 are equal, otherwise return zero.

fq_nmod_poly_equal_trunc :: Ptr CFqPoly -> Ptr CFqPoly -> CLong -> Ptr CFqCtx -> IO CInt

fq_nmod_poly_equal_trunc poly1 poly2 n ctx

Notionally truncate poly1 and poly2 to length \(n\) and return nonzero if they are equal, otherwise return zero.

fq_nmod_poly_is_zero :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_is_zero poly ctx

Returns whether the polynomial poly is the zero polynomial.

fq_nmod_poly_is_one :: Ptr CFqNModPoly -> IO CInt

fq_nmod_poly_is_one op

Returns whether the polynomial poly is equal to the constant polynomial \(1\).

fq_nmod_poly_is_gen :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_is_gen op ctx

Returns whether the polynomial poly is equal to the polynomial \(x\).

fq_nmod_poly_is_unit :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_is_unit op ctx

Returns whether the polynomial poly is a unit in the polynomial ring \(\mathbf{F}_q[X]\), i.e. if it has degree \(0\) and is non-zero.

fq_nmod_poly_equal_fq_nmod :: Ptr CFqNModPoly -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_equal_fq_nmod poly c ctx

Returns whether the polynomial poly is equal the (constant) \(\mathbf{F}_q\) element c

Addition and subtraction

_fq_nmod_poly_add :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_add res poly1 len1 poly2 len2 ctx

Sets res to the sum of (poly1,len1) and (poly2,len2).

fq_nmod_poly_add :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_add res poly1 poly2 ctx

Sets res to the sum of poly1 and poly2.

fq_nmod_poly_add_si :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_add_si res poly1 c ctx

Sets res to the sum of poly1 and c.

fq_nmod_poly_add_series :: Ptr CFqPoly -> Ptr CFqPoly -> Ptr CFqPoly -> CLong -> Ptr CFqCtx -> IO ()

fq_nmod_poly_add_series res poly1 poly2 n ctx

Notionally truncate poly1 and poly2 to length n and set res to the sum.

_fq_nmod_poly_sub :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_sub res poly1 len1 poly2 len2 ctx

Sets res to the difference of (poly1,len1) and (poly2,len2).

fq_nmod_poly_sub :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_sub res poly1 poly2 ctx

Sets res to the difference of poly1 and poly2.

fq_nmod_poly_sub_series :: Ptr CFqPoly -> Ptr CFqPoly -> Ptr CFqPoly -> CLong -> Ptr CFqCtx -> IO ()

fq_nmod_poly_sub_series res poly1 poly2 n ctx

Notionally truncate poly1 and poly2 to length n and set res to the difference.

_fq_nmod_poly_neg :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_neg rop op len ctx

Sets rop to the additive inverse of (poly,len).

fq_nmod_poly_neg :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_neg res poly ctx

Sets res to the additive inverse of poly.

Scalar multiplication and division

_fq_nmod_poly_scalar_mul_fq_nmod :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_scalar_mul_fq_nmod rop op len x ctx

Sets (rop,len) to the product of (op,len) by the scalar x, in the context defined by ctx.

fq_nmod_poly_scalar_mul_fq_nmod :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_scalar_mul_fq_nmod rop op x ctx

Sets rop to the product of op by the scalar x, in the context defined by ctx.

_fq_nmod_poly_scalar_addmul_fq_nmod :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_scalar_addmul_fq_nmod rop op len x ctx

Adds to (rop,len) the product of (op,len) by the scalar x, in the context defined by ctx. In particular, assumes the same length for op and rop.

fq_nmod_poly_scalar_addmul_fq_nmod :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_scalar_addmul_fq_nmod rop op x ctx

Adds to rop the product of op by the scalar x, in the context defined by ctx.

_fq_nmod_poly_scalar_submul_fq_nmod :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_scalar_submul_fq_nmod rop op len x ctx

Subtracts from (rop,len) the product of (op,len) by the scalar x, in the context defined by ctx. In particular, assumes the same length for op and rop.

fq_nmod_poly_scalar_submul_fq_nmod :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_scalar_submul_fq_nmod rop op x ctx

Subtracts from rop the product of op by the scalar x, in the context defined by ctx.

Multiplication

_fq_nmod_poly_mul_classical :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mul_classical rop op1 len1 op2 len2 ctx

Sets (rop, len1 + len2 - 1) to the product of (op1, len1) and (op2, len2), assuming that len1 is at least len2 and neither is zero.

Permits zero padding. Does not support aliasing of rop with either op1 or op2.

fq_nmod_poly_mul_classical :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mul_classical rop op1 op2 ctx

Sets rop to the product of op1 and op2 using classical polynomial multiplication.

_fq_nmod_poly_mul_univariate :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mul_univariate rop op1 len1 op2 len2 ctx

Sets (rop, len1 + len2 - 1) to the product of (op1, len1) and (op2, len2).

Permits zero padding and makes no assumptions on len1 and len2. Supports aliasing.

fq_nmod_poly_mul_univariate :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mul_univariate rop op1 op2 ctx

Sets rop to the product of op1 and op2 using a bivariate to univariate transformation and reducing this problem to multiplying two univariate polynomials.

_fq_nmod_poly_mul_KS :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mul_KS rop op1 len1 op2 len2 ctx

Sets (rop, len1 + len2 - 1) to the product of (op1, len1) and (op2, len2).

Permits zero padding and places no assumptions on the lengths len1 and len2. Supports aliasing.

fq_nmod_poly_mul_KS :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mul_KS rop op1 op2 ctx

Sets rop to the product of op1 and op2 using Kronecker substitution, that is, by encoding each coefficient in \(\mathbf{F}_{q}\) as an integer and reducing this problem to multiplying two polynomials over the integers.

_fq_nmod_poly_mul :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mul rop op1 len1 op2 len2 ctx

Sets (rop, len1 + len2 - 1) to the product of (op1, len1) and (op2, len2), choosing an appropriate algorithm.

Permits zero padding. Does not support aliasing.

fq_nmod_poly_mul :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mul rop op1 op2 ctx

Sets rop to the product of op1 and op2, choosing an appropriate algorithm.

_fq_nmod_poly_mullow_classical :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mullow_classical rop op1 len1 op2 len2 n ctx

Sets (rop, n) to the first \(n\) coefficients of (op1, len1) multiplied by (op2, len2).

Assumes 0 < n <= len1 + len2 - 1. Assumes neither len1 nor len2 is zero.

fq_nmod_poly_mullow_classical :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mullow_classical rop op1 op2 n ctx

Sets rop to the product of op1 and op2, computed using the classical or schoolbook method.

_fq_nmod_poly_mullow_univariate :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mullow_univariate rop op1 len1 op2 len2 n ctx

Sets (rop, n) to the lowest \(n\) coefficients of the product of (op1, len1) and (op2, len2), computed using a bivariate to univariate transformation.

Assumes that len1 and len2 are positive, but does allow for the polynomials to be zero-padded. The polynomials may be zero, too. Assumes \(n\) is positive. Supports aliasing between rop, op1 and op2.

fq_nmod_poly_mullow_univariate :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mullow_univariate rop op1 op2 n ctx

Sets rop to the lowest \(n\) coefficients of the product of poly1 and poly2, computed using a bivariate to univariate transformation.

_fq_nmod_poly_mullow_KS :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mullow_KS rop op1 len1 op2 len2 n ctx

Sets (rop, n) to the lowest \(n\) coefficients of the product of (op1, len1) and (op2, len2).

Assumes that len1 and len2 are positive, but does allow for the polynomials to be zero-padded. The polynomials may be zero, too. Assumes \(n\) is positive. Supports aliasing between rop, op1 and op2.

fq_nmod_poly_mullow_KS :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mullow_KS rop op1 op2 n ctx

Sets rop to the product of op1 and op2.

_fq_nmod_poly_mullow :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mullow rop op1 len1 op2 len2 n ctx

Sets (rop, n) to the lowest \(n\) coefficients of the product of (op1, len1) and (op2, len2).

Assumes 0 < n <= len1 + len2 - 1. Allows for zero-padding in the inputs. Does not support aliasing between the inputs and the output.

fq_nmod_poly_mullow :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mullow rop op1 op2 n ctx

Sets rop to the lowest \(n\) coefficients of the product of op1 and op2.

_fq_nmod_poly_mulhigh_classical :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mulhigh_classical res poly1 len1 poly2 len2 start ctx

Computes the product of (poly1, len1) and (poly2, len2) and writes the coefficients from start onwards into the high coefficients of res, the remaining coefficients being arbitrary but reduced. Assumes that len1 >= len2 > 0. Aliasing of inputs and output is not permitted. Algorithm is classical multiplication.

fq_nmod_poly_mulhigh_classical :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mulhigh_classical res poly1 poly2 start ctx

Computes the product of poly1 and poly2 and writes the coefficients from start onwards into the high coefficients of res, the remaining coefficients being arbitrary but reduced. Algorithm is classical multiplication.

_fq_nmod_poly_mulhigh :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mulhigh res poly1 len1 poly2 len2 start ctx

Computes the product of (poly1, len1) and (poly2, len2) and writes the coefficients from start onwards into the high coefficients of res, the remaining coefficients being arbitrary but reduced. Assumes that len1 >= len2 > 0. Aliasing of inputs and output is not permitted.

fq_nmod_poly_mulhigh :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mulhigh res poly1 poly2 start ctx

Computes the product of poly1 and poly2 and writes the coefficients from start onwards into the high coefficients of res, the remaining coefficients being arbitrary but reduced.

_fq_nmod_poly_mulmod :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mulmod res poly1 len1 poly2 len2 f lenf ctx

Sets res to the remainder of the product of poly1 and poly2 upon polynomial division by f.

It is required that len1 + len2 - lenf > 0, which is equivalent to requiring that the result will actually be reduced. Otherwise, simply use _fq_nmod_poly_mul instead.

Aliasing of f and res is not permitted.

fq_nmod_poly_mulmod :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mulmod res poly1 poly2 f ctx

Sets res to the remainder of the product of poly1 and poly2 upon polynomial division by f.

_fq_nmod_poly_mulmod_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_mulmod_preinv res poly1 len1 poly2 len2 f lenf finv lenfinv ctx

Sets res to the remainder of the product of poly1 and poly2 upon polynomial division by f.

It is required that finv is the inverse of the reverse of f mod x^lenf.

Aliasing of res with any of the inputs is not permitted.

fq_nmod_poly_mulmod_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_mulmod_preinv res poly1 poly2 f finv ctx

Sets res to the remainder of the product of poly1 and poly2 upon polynomial division by f. finv is the inverse of the reverse of f.

Squaring

_fq_nmod_poly_sqr_classical :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_sqr_classical rop op len ctx

Sets (rop, 2*len - 1) to the square of (op, len), assuming that (op,len) is not zero and using classical polynomial multiplication.

Permits zero padding. Does not support aliasing of rop with either op1 or op2.

fq_nmod_poly_sqr_classical :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_sqr_classical rop op ctx

Sets rop to the square of op using classical polynomial multiplication.

_fq_nmod_poly_sqr_KS :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_sqr_KS rop op len ctx

Sets (rop, 2*len - 1) to the square of (op, len).

Permits zero padding and places no assumptions on the lengths len1 and len2. Supports aliasing.

fq_nmod_poly_sqr_KS :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_sqr_KS rop op ctx

Sets rop to the square op using Kronecker substitution, that is, by encoding each coefficient in \(\mathbf{F}_{q}\) as an integer and reducing this problem to multiplying two polynomials over the integers.

_fq_nmod_poly_sqr :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_sqr rop op len ctx

Sets (rop, 2* len - 1) to the square of (op, len), choosing an appropriate algorithm.

Permits zero padding. Does not support aliasing.

fq_nmod_poly_sqr :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_sqr rop op ctx

Sets rop to the square of op, choosing an appropriate algorithm.

Powering

_fq_nmod_poly_pow :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> CULong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_pow rop op len e ctx

Sets rop = op^e, assuming that e, len > 0 and that rop has space for e*(len - 1) + 1 coefficients. Does not support aliasing.

fq_nmod_poly_pow :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CULong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_pow rop op e ctx

Computes rop = op^e. If \(e\) is zero, returns one, so that in particular 0^0 = 1.

_fq_nmod_poly_powmod_ui_binexp :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CULong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_powmod_ui_binexp res poly e f lenf ctx

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e > 0.

We require lenf > 1. It is assumed that poly is already reduced modulo f and zero-padded as necessary to have length exactly lenf - 1. The output res must have room for lenf - 1 coefficients.

fq_nmod_poly_powmod_ui_binexp :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CULong -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_powmod_ui_binexp res poly e f ctx

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e >= 0.

_fq_nmod_poly_powmod_ui_binexp_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CULong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_powmod_ui_binexp_preinv res poly e f lenf finv lenfinv ctx

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e > 0. We require finv to be the inverse of the reverse of f.

We require lenf > 1. It is assumed that poly is already reduced modulo f and zero-padded as necessary to have length exactly lenf - 1. The output res must have room for lenf - 1 coefficients.

fq_nmod_poly_powmod_ui_binexp_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CULong -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_powmod_ui_binexp_preinv res poly e f finv ctx

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e >= 0. We require finv to be the inverse of the reverse of f.

_fq_nmod_poly_powmod_fmpz_binexp :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr CFmpz -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_powmod_fmpz_binexp res poly e f lenf ctx

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e > 0.

We require lenf > 1. It is assumed that poly is already reduced modulo f and zero-padded as necessary to have length exactly lenf - 1. The output res must have room for lenf - 1 coefficients.

fq_nmod_poly_powmod_fmpz_binexp :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFmpz -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_powmod_fmpz_binexp res poly e f ctx

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e >= 0.

_fq_nmod_poly_powmod_fmpz_binexp_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr CFmpz -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_powmod_fmpz_binexp_preinv res poly e f lenf finv lenfinv ctx

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e > 0. We require finv to be the inverse of the reverse of f.

We require lenf > 1. It is assumed that poly is already reduced modulo f and zero-padded as necessary to have length exactly lenf - 1. The output res must have room for lenf - 1 coefficients.

fq_nmod_poly_powmod_fmpz_binexp_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFmpz -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_powmod_fmpz_binexp_preinv res poly e f finv ctx

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e >= 0. We require finv to be the inverse of the reverse of f.

_fq_nmod_poly_powmod_fmpz_sliding_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr CFmpz -> CULong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_powmod_fmpz_sliding_preinv res poly e k f lenf finv lenfinv ctx

Sets res to poly raised to the power e modulo f, using sliding-window exponentiation with window size k. We require e > 0. We require finv to be the inverse of the reverse of f. If k is set to zero, then an "optimum" size will be selected automatically base on e.

We require lenf > 1. It is assumed that poly is already reduced modulo f and zero-padded as necessary to have length exactly lenf - 1. The output res must have room for lenf - 1 coefficients.

fq_nmod_poly_powmod_fmpz_sliding_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFmpz -> CULong -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_powmod_fmpz_sliding_preinv res poly e k f finv ctx

Sets res to poly raised to the power e modulo f, using sliding-window exponentiation with window size k. We require e >= 0. We require finv to be the inverse of the reverse of f. If k is set to zero, then an "optimum" size will be selected automatically base on e.

_fq_nmod_poly_powmod_x_fmpz_preinv :: Ptr (Ptr CFqNMod) -> Ptr CFmpz -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_powmod_x_fmpz_preinv res e f lenf finv lenfinv ctx

Sets res to x raised to the power e modulo f, using sliding window exponentiation. We require e > 0. We require finv to be the inverse of the reverse of f.

We require lenf > 2. The output res must have room for lenf - 1 coefficients.

fq_nmod_poly_powmod_x_fmpz_preinv :: Ptr CFqNModPoly -> Ptr CFmpz -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_powmod_x_fmpz_preinv res e f finv ctx

Sets res to x raised to the power e modulo f, using sliding window exponentiation. We require e >= 0. We require finv to be the inverse of the reverse of f.

_fq_nmod_poly_pow_trunc_binexp :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CULong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_pow_trunc_binexp res poly e trunc ctx

Sets res to the low trunc coefficients of poly (assumed to be zero padded if necessary to length trunc) to the power e. This is equivalent to doing a powering followed by a truncation. We require that res has enough space for trunc coefficients, that trunc > 0 and that e > 1. Aliasing is not permitted. Uses the binary exponentiation method.

fq_nmod_poly_pow_trunc_binexp :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CULong -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_pow_trunc_binexp res poly e trunc ctx

Sets res to the low trunc coefficients of poly to the power e. This is equivalent to doing a powering followed by a truncation. Uses the binary exponentiation method.

_fq_nmod_poly_pow_trunc :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CULong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_pow_trunc res poly e trunc mod

Sets res to the low trunc coefficients of poly (assumed to be zero padded if necessary to length trunc) to the power e. This is equivalent to doing a powering followed by a truncation. We require that res has enough space for trunc coefficients, that trunc > 0 and that e > 1. Aliasing is not permitted.

fq_nmod_poly_pow_trunc :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CULong -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_pow_trunc res poly e trunc ctx

Sets res to the low trunc coefficients of poly to the power e. This is equivalent to doing a powering followed by a truncation.

Shifting

_fq_nmod_poly_shift_left :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_shift_left rop op len n ctx

Sets (rop, len + n) to (op, len) shifted left by \(n\) coefficients.

Inserts zero coefficients at the lower end. Assumes that len and \(n\) are positive, and that rop fits len + n elements. Supports aliasing between rop and op.

fq_nmod_poly_shift_left :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_shift_left rop op n ctx

Sets rop to op shifted left by \(n\) coeffs. Zero coefficients are inserted.

_fq_nmod_poly_shift_right :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_shift_right rop op len n ctx

Sets (rop, len - n) to (op, len) shifted right by \(n\) coefficients.

Assumes that len and \(n\) are positive, that len > n, and that rop fits len - n elements. Supports aliasing between rop and op, although in this case the top coefficients of op are not set to zero.

fq_nmod_poly_shift_right :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_shift_right rop op n ctx

Sets rop to op shifted right by \(n\) coefficients. If \(n\) is equal to or greater than the current length of op, rop is set to the zero polynomial.

Norms

_fq_nmod_poly_hamming_weight :: Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO CLong

_fq_nmod_poly_hamming_weight op len ctx

Returns the number of non-zero entries in (op, len).

fq_nmod_poly_hamming_weight :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CLong

fq_nmod_poly_hamming_weight op ctx

Returns the number of non-zero entries in the polynomial op.

Euclidean division

_fq_nmod_poly_divrem :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_divrem Q R A lenA B lenB invB ctx

Computes (Q, lenA - lenB + 1), (R, lenA) such that \(A = B Q + R\) with \(0 \leq \operatorname{len}(R) < \operatorname{len}(B)\).

Assumes that the leading coefficient of \(B\) is invertible and that invB is its inverse.

Assumes that \(\operatorname{len}(A), \operatorname{len}(B) > 0\). Allows zero-padding in (A, lenA). \(R\) and \(A\) may be aliased, but apart from this no aliasing of input and output operands is allowed.

fq_nmod_poly_divrem :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_divrem Q R A B ctx

Computes \(Q\), \(R\) such that \(A = B Q + R\) with \(0 \leq \operatorname{len}(R) < \operatorname{len}(B)\).

Assumes that the leading coefficient of \(B\) is invertible. This can be taken for granted the context is for a finite field, that is, when \(p\) is prime and \(f(X)\) is irreducible.

fq_nmod_poly_divrem_f :: Ptr CFqNMod -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_divrem_f f Q R A B ctx

Either finds a non-trivial factor \(f\) of the modulus of ctx, or computes \(Q\), \(R\) such that \(A = B Q + R\) and \(0 \leq \operatorname{len}(R) < \operatorname{len}(B)\).

If the leading coefficient of \(B\) is invertible, the division with remainder operation is carried out, \(Q\) and \(R\) are computed correctly, and \(f\) is set to \(1\). Otherwise, \(f\) is set to a non-trivial factor of the modulus and \(Q\) and \(R\) are not touched.

Assumes that \(B\) is non-zero.

_fq_nmod_poly_rem :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_rem R A lenA B lenB invB ctx

Sets R to the remainder of the division of (A,lenA) by (B,lenB). Assumes that the leading coefficient of (B,lenB) is invertible and that invB is its inverse.

fq_nmod_poly_rem :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_rem R A B ctx

Sets R to the remainder of the division of A by B in the context described by ctx.

_fq_nmod_poly_div :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_div Q A lenA B lenB invB ctx

Notationally, computes \(Q\), \(R\) such that \(A = B Q + R\) with (0 leq operatorname{len}(R) < operatorname{len}(B)) but only sets (Q, lenA - lenB + 1).

Allows zero-padding in \(A\) but not in \(B\). Assumes that the leading coefficient of \(B\) is a unit.

fq_nmod_poly_div :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_div Q A B ctx

Notionally finds polynomials \(Q\) and \(R\) such that \(A = B Q + R\) with \(\operatorname{len}(R) < \operatorname{len}(B)\), but returns only Q. If \(\operatorname{len}(B) = 0\) an exception is raised.

_fq_nmod_poly_div_newton_n_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> IO ()

_fq_nmod_poly_div_newton_n_preinv Q A lenA B lenB Binv lenBinv ctx_t

Notionally computes polynomials \(Q\) and \(R\) such that \(A = BQ + R\) with \(\operatorname{len}(R)\) less than lenB, where A is of length lenA and B is of length lenB, but return only \(Q\).

We require that \(Q\) have space for lenA - lenB + 1 coefficients and assume that the leading coefficient of \(B\) is a unit. Furthermore, we assume that \(Binv\) is the inverse of the reverse of \(B\) mod \(x^{\operatorname{len}(B)}\).

The algorithm used is to reverse the polynomials and divide the resulting power series, then reverse the result.

fq_nmod_poly_div_newton_n_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_div_newton_n_preinv Q A B Binv ctx

Notionally computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\operatorname{len}(R) < \operatorname{len}(B)\), but returns only \(Q\).

We assume that the leading coefficient of \(B\) is a unit and that \(Binv\) is the inverse of the reverse of \(B\) mod \(x^{\operatorname{len}(B)}\).

It is required that the length of \(A\) is less than or equal to 2*the length of \(B\) - 2.

The algorithm used is to reverse the polynomials and divide the resulting power series, then reverse the result.

_fq_nmod_poly_divrem_newton_n_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_divrem_newton_n_preinv Q R A lenA B lenB Binv lenBinv ctx

Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\operatorname{len}(R)\) less than lenB, where \(A\) is of length lenA and \(B\) is of length lenB. We require that \(Q\) have space for lenA - lenB + 1 coefficients. Furthermore, we assume that \(Binv\) is the inverse of the reverse of \(B\) mod \(x^{\operatorname{len}(B)}\). The algorithm used is to call div_newton_preinv and then multiply out and compute the remainder.

fq_nmod_poly_divrem_newton_n_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_divrem_newton_n_preinv Q R A B Binv ctx

Computes \(Q\) and \(R\) such that \(A = BQ + R\) with (operatorname{len}(R) < operatorname{len}(B)). We assume \(Binv\) is the inverse of the reverse of \(B\) mod \(x^{\operatorname{len}(B)}\).

It is required that the length of \(A\) is less than or equal to 2*the length of \(B\) - 2.

The algorithm used is to call div_newton and then multiply out and compute the remainder.

_fq_nmod_poly_inv_series_newton :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_inv_series_newton Qinv Q n ctx

Given Q of length n whose constant coefficient is invertible modulo the given modulus, find a polynomial Qinv of length n such that Q * Qinv is 1 modulo \(x^n\). Requires n > 0. This function can be viewed as inverting a power series via Newton iteration.

fq_nmod_poly_inv_series_newton :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_inv_series_newton Qinv Q n ctx

Given Q find Qinv such that Q * Qinv is 1 modulo \(x^n\). The constant coefficient of Q must be invertible modulo the modulus of Q. An exception is raised if this is not the case or if n = 0. This function can be viewed as inverting a power series via Newton iteration.

_fq_nmod_poly_inv_series :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_inv_series Qinv Q n ctx

Given Q of length n whose constant coefficient is invertible modulo the given modulus, find a polynomial Qinv of length n such that Q * Qinv is 1 modulo \(x^n\). Requires n > 0.

fq_nmod_poly_inv_series :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_inv_series Qinv Q n ctx

Given Q find Qinv such that Q * Qinv is 1 modulo \(x^n\). The constant coefficient of Q must be invertible modulo the modulus of Q. An exception is raised if this is not the case or if n = 0.

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

_fq_nmod_poly_div_series Q A Alen B Blen n ctx

Set (Q, n) to the quotient of the series (A, Alen) and (B, Blen) assuming Alen, Blen <= n. We assume the bottom coefficient of B is invertible.

fq_nmod_poly_div_series :: Ptr CFmpzModPoly -> Ptr CFmpzModPoly -> Ptr CFmpzModPoly -> CLong -> Ptr CFqCtx -> IO ()

fq_nmod_poly_div_series Q A B n ctx

Set \(Q\) to the quotient of the series \(A\) by \(B\), thinking of the series as though they were of length \(n\). We assume that the bottom coefficient of \(B\) is invertible.

Greatest common divisor

fq_nmod_poly_gcd :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_gcd rop op1 op2 ctx

Sets rop to the greatest common divisor of op1 and op2, using the either the Euclidean or HGCD algorithm. The GCD of zero polynomials is defined to be zero, whereas the GCD of the zero polynomial and some other polynomial \(P\) is defined to be \(P\). Except in the case where the GCD is zero, the GCD \(G\) is made monic.

_fq_nmod_poly_gcd :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CLong

_fq_nmod_poly_gcd G A lenA B lenB ctx

Computes the GCD of \(A\) of length lenA and \(B\) of length lenB, where lenA >= lenB > 0 and sets \(G\) to it. The length of the GCD \(G\) is returned by the function. No attempt is made to make the GCD monic. It is required that \(G\) have space for lenB coefficients.

_fq_nmod_poly_gcd_euclidean_f :: Ptr CFqNMod -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CLong

_fq_nmod_poly_gcd_euclidean_f f G A lenA B lenB ctx

Either sets \(f = 1\) and \(G\) to the greatest common divisor of \((A,\operatorname{len}(A))\) and \((B, \operatorname{len}(B))\) and returns its length, or sets \(f\) to a non-trivial factor of the modulus of ctx and leaves the contents of the vector \((G, lenB)\) undefined.

Assumes that \(\operatorname{len}(A) \geq \operatorname{len}(B) > 0\) and that the vector \(G\) has space for sufficiently many coefficients.

fq_nmod_poly_gcd_euclidean_f :: Ptr CFqNMod -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_gcd_euclidean_f f G A B ctx

Either sets \(f = 1\) and \(G\) to the greatest common divisor of \(A\) and \(B\) or sets \(f\) to a factor of the modulus of ctx.

_fq_nmod_poly_xgcd :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CLong

_fq_nmod_poly_xgcd G S T A lenA B lenB ctx

Computes the GCD of \(A\) and \(B\) together with cofactors \(S\) and \(T\) such that \(S A + T B = G\). Returns the length of \(G\).

Assumes that \(\operatorname{len}(A) \geq \operatorname{len}(B) \geq 1\) and \((\operatorname{len}(A),\operatorname{len}(B)) \neq (1,1)\).

No attempt is made to make the GCD monic.

Requires that \(G\) have space for \(\operatorname{len}(B)\) coefficients. Writes \(\operatorname{len}(B)-1\) and \(\operatorname{len}(A)-1\) coefficients to \(S\) and \(T\), respectively. Note that, in fact, \(\operatorname{len}(S) \leq \max(\operatorname{len}(B) - \operatorname{len}(G), 1)\) and \(\operatorname{len}(T) \leq \max(\operatorname{len}(A) - \operatorname{len}(G), 1)\).

No aliasing of input and output operands is permitted.

fq_nmod_poly_xgcd :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_xgcd G S T A B ctx

Computes the GCD of \(A\) and \(B\). The GCD of zero polynomials is defined to be zero, whereas the GCD of the zero polynomial and some other polynomial \(P\) is defined to be \(P\). Except in the case where the GCD is zero, the GCD \(G\) is made monic.

Polynomials S and T are computed such that S*A + T*B = G. The length of S will be at most lenB and the length of T will be at most lenA.

_fq_nmod_poly_xgcd_euclidean_f :: Ptr CFqNMod -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFmpz -> Ptr CFqNModCtx -> IO CLong

_fq_nmod_poly_xgcd_euclidean_f f G S T A lenA B lenB invB ctx

Either sets \(f = 1\) and computes the GCD of \(A\) and \(B\) together with cofactors \(S\) and \(T\) such that \(S A + T B = G\); otherwise, sets \(f\) to a non-trivial factor of the modulus of ctx and leaves \(G\), \(S\), and \(T\) undefined. Returns the length of \(G\).

Assumes that \(\operatorname{len}(A) \geq \operatorname{len}(B) \geq 1\) and \((\operatorname{len}(A),\operatorname{len}(B)) \neq (1,1)\).

No attempt is made to make the GCD monic.

Requires that \(G\) have space for \(\operatorname{len}(B)\) coefficients. Writes \(\operatorname{len}(B)-1\) and \(\operatorname{len}(A)-1\) coefficients to \(S\) and \(T\), respectively. Note that, in fact, \(\operatorname{len}(S) \leq \max(\operatorname{len}(B) - \operatorname{len}(G), 1)\) and \(\operatorname{len}(T) \leq \max(\operatorname{len}(A) - \operatorname{len}(G), 1)\).

No aliasing of input and output operands is permitted.

fq_nmod_poly_xgcd_euclidean_f :: Ptr CFqNMod -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_xgcd_euclidean_f f G S T A B ctx

Either sets \(f = 1\) and computes the GCD of \(A\) and \(B\) or sets \(f\) to a non-trivial factor of the modulus of ctx.

If the GCD is computed, polynomials S and T are computed such that S*A + T*B = G; otherwise, they are undefined. The length of S will be at most lenB and the length of T will be at most lenA.

The GCD of zero polynomials is defined to be zero, whereas the GCD of the zero polynomial and some other polynomial \(P\) is defined to be \(P\). Except in the case where the GCD is zero, the GCD \(G\) is made monic.

Divisibility testing

_fq_nmod_poly_divides :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO CInt

_fq_nmod_poly_divides Q A lenA B lenB invB ctx

Returns \(1\) if (B, lenB) divides (A, lenA) exactly and sets \(Q\) to the quotient, otherwise returns \(0\).

It is assumed that \(\operatorname{len}(A) \geq \operatorname{len}(B) > 0\) and that \(Q\) has space for \(\operatorname{len}(A) - \operatorname{len}(B) + 1\) coefficients.

Aliasing of \(Q\) with either of the inputs is not permitted.

This function is currently unoptimised and provided for convenience only.

fq_nmod_poly_divides :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_divides Q A B ctx

Returns \(1\) if \(B\) divides \(A\) exactly and sets \(Q\) to the quotient, otherwise returns \(0\).

This function is currently unoptimised and provided for convenience only.

Derivative

_fq_nmod_poly_derivative :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_derivative rop op len ctx

Sets (rop, len - 1) to the derivative of (op, len). Also handles the cases where len is \(0\) or \(1\) correctly. Supports aliasing of rop and op.

fq_nmod_poly_derivative :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_derivative rop op ctx

Sets rop to the derivative of op.

Square root

_fq_nmod_poly_invsqrt_series :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_invsqrt_series g h n mod

Set the first \(n\) terms of \(g\) to the series expansion of \(1/\sqrt{h}\). It is assumed that \(n > 0\), that \(h\) has constant term 1 and that \(h\) is zero-padded as necessary to length \(n\). Aliasing is not permitted.

fq_nmod_poly_invsqrt_series :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_invsqrt_series g h n ctx

Set \(g\) to the series expansion of \(1/\sqrt{h}\) to order \(O(x^n)\). It is assumed that \(h\) has constant term 1.

_fq_nmod_poly_sqrt_series :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_sqrt_series g h n ctx

Set the first \(n\) terms of \(g\) to the series expansion of \(\sqrt{h}\). It is assumed that \(n > 0\), that \(h\) has constant term 1 and that \(h\) is zero-padded as necessary to length \(n\). Aliasing is not permitted.

fq_nmod_poly_sqrt_series :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_sqrt_series g h n ctx

Set \(g\) to the series expansion of \(\sqrt{h}\) to order \(O(x^n)\). It is assumed that \(h\) has constant term 1.

_fq_nmod_poly_sqrt :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CInt

_fq_nmod_poly_sqrt s p n mod

If (p, n) is a perfect square, sets (s, n / 2 + 1) to a square root of \(p\) and returns 1. Otherwise returns 0.

fq_nmod_poly_sqrt :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_sqrt s p mod

If \(p\) is a perfect square, sets \(s\) to a square root of \(p\) and returns 1. Otherwise returns 0.

Evaluation

_fq_nmod_poly_evaluate_fq_nmod :: Ptr CFqNMod -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_evaluate_fq_nmod rop op len a ctx

Sets rop to (op, len) evaluated at \(a\).

Supports zero padding. There are no restrictions on len, that is, len is allowed to be zero, too.

fq_nmod_poly_evaluate_fq_nmod :: Ptr CFqNMod -> Ptr CFqNModPoly -> Ptr CFqNMod -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_evaluate_fq_nmod rop f a ctx

Sets rop to the value of \(f(a)\).

As the coefficient ring \(\mathbf{F}_q\) is finite, Horner's method is sufficient.

Composition

_fq_nmod_poly_compose :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_compose rop op1 len1 op2 len2 ctx

Sets rop to the composition of (op1, len1) and (op2, len2).

Assumes that rop has space for (len1-1)*(len2-1) + 1 coefficients. Assumes that op1 and op2 are non-zero polynomials. Does not support aliasing between any of the inputs and the output.

fq_nmod_poly_compose :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_compose rop op1 op2 ctx

Sets rop to the composition of op1 and op2. To be precise about the order of composition, denoting rop, op1, and op2 by \(f\), \(g\), and \(h\), respectively, sets \(f(t) = g(h(t))\).

_fq_nmod_poly_compose_mod_horner :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_compose_mod_horner res f lenf g h lenh ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that the length of \(g\) is one less than the length of \(h\) (possibly with zero padding). The output is not allowed to be aliased with any of the inputs.

The algorithm used is Horner's rule.

fq_nmod_poly_compose_mod_horner :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_compose_mod_horner res f g h ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero. The algorithm used is Horner's rule.

_fq_nmod_poly_compose_mod_horner_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_compose_mod_horner_preinv res f lenf g h lenh hinv lenhiv ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that the length of \(g\) is one less than the length of \(h\) (possibly with zero padding). We also require that the length of \(f\) is less than the length of \(h\). Furthermore, we require hinv to be the inverse of the reverse of h. The output is not allowed to be aliased with any of the inputs.

The algorithm used is Horner's rule.

fq_nmod_poly_compose_mod_horner_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_compose_mod_horner_preinv res f g h hinv ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that \(f\) has smaller degree than \(h\). Furthermore, we require hinv to be the inverse of the reverse of h. The algorithm used is Horner's rule.

_fq_nmod_poly_compose_mod_brent_kung :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_compose_mod_brent_kung res f lenf g h lenh ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that the length of \(g\) is one less than the length of \(h\) (possibly with zero padding). We also require that the length of \(f\) is less than the length of \(h\). The output is not allowed to be aliased with any of the inputs.

The algorithm used is the Brent-Kung matrix algorithm.

fq_nmod_poly_compose_mod_brent_kung :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_compose_mod_brent_kung res f g h ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that \(f\) has smaller degree than \(h\). The algorithm used is the Brent-Kung matrix algorithm.

_fq_nmod_poly_compose_mod_brent_kung_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_compose_mod_brent_kung_preinv res f lenf g h lenh hinv lenhiv ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that the length of \(g\) is one less than the length of \(h\) (possibly with zero padding). We also require that the length of \(f\) is less than the length of \(h\). Furthermore, we require hinv to be the inverse of the reverse of h. The output is not allowed to be aliased with any of the inputs.

The algorithm used is the Brent-Kung matrix algorithm.

fq_nmod_poly_compose_mod_brent_kung_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_compose_mod_brent_kung_preinv res f g h hinv ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that \(f\) has smaller degree than \(h\). Furthermore, we require hinv to be the inverse of the reverse of h. The algorithm used is the Brent-Kung matrix algorithm.

_fq_nmod_poly_compose_mod :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_compose_mod res f lenf g h lenh ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that the length of \(g\) is one less than the length of \(h\) (possibly with zero padding). The output is not allowed to be aliased with any of the inputs.

fq_nmod_poly_compose_mod :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_compose_mod res f g h ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero.

_fq_nmod_poly_compose_mod_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_compose_mod_preinv res f lenf g h lenh hinv lenhiv ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that the length of \(g\) is one less than the length of \(h\) (possibly with zero padding). We also require that the length of \(f\) is less than the length of \(h\). Furthermore, we require hinv to be the inverse of the reverse of h. The output is not allowed to be aliased with any of the inputs.

fq_nmod_poly_compose_mod_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_compose_mod_preinv res f g h hinv ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero and that \(f\) has smaller degree than \(h\). Furthermore, we require hinv to be the inverse of the reverse of h.

_fq_nmod_poly_reduce_matrix_mod_poly :: Ptr CFqNModMat -> Ptr CFqNModMat -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_reduce_matrix_mod_poly A B f ctx

Sets the ith row of A to the reduction of the ith row of \(B\) modulo \(f\) for \(i=1,\ldots,\sqrt{\deg(f)}\). We require \(B\) to be at least a \(\sqrt{\deg(f)}\times \deg(f)\) matrix and \(f\) to be nonzero.

_fq_nmod_poly_precompute_matrix :: Ptr CFqNModMat -> Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_precompute_matrix A f g leng ginv lenginv ctx

Sets the ith row of A to \(f^i\) modulo \(g\) for \(i=1,\ldots,\sqrt{\deg(g)}\). We require \(A\) to be a \(\sqrt{\deg(g)}\times \deg(g)\) matrix. We require ginv to be the inverse of the reverse of g and \(g\) to be nonzero.

fq_nmod_poly_precompute_matrix :: Ptr CFqNModMat -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_precompute_matrix A f g ginv ctx

Sets the ith row of A to \(f^i\) modulo \(g\) for \(i=1,\ldots,\sqrt{\deg(g)}\). We require \(A\) to be a \(\sqrt{\deg(g)}\times \deg(g)\) matrix. We require ginv to be the inverse of the reverse of g.

_fq_nmod_poly_compose_mod_brent_kung_precomp_preinv :: Ptr (Ptr CFqNMod) -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModMat -> Ptr (Ptr CFqNMod) -> CLong -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO ()

_fq_nmod_poly_compose_mod_brent_kung_precomp_preinv res f lenf A h lenh hinv lenhinv ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero. We require that the ith row of \(A\) contains \(g^i\) for \(i=1,\ldots,\sqrt{\deg(h)}\), i.e. \(A\) is a \(\sqrt{\deg(h)}\times \deg(h)\) matrix. We also require that the length of \(f\) is less than the length of \(h\). Furthermore, we require hinv to be the inverse of the reverse of h. The output is not allowed to be aliased with any of the inputs.

The algorithm used is the Brent-Kung matrix algorithm.

fq_nmod_poly_compose_mod_brent_kung_precomp_preinv :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModMat -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_compose_mod_brent_kung_precomp_preinv res f A h hinv ctx

Sets res to the composition \(f(g)\) modulo \(h\). We require that the ith row of \(A\) contains \(g^i\) for \(i=1,\ldots,\sqrt{\deg(h)}\), i.e. \(A\) is a (sqrt{deg(h)}times deg(h)) matrix. We require that \(h\) is nonzero and that \(f\) has smaller degree than \(h\). Furthermore, we require hinv to be the inverse of the reverse of h. This version of Brent-Kung modular composition is particularly useful if one has to perform several modular composition of the form \(f(g)\) modulo \(h\) for fixed \(g\) and \(h\).

Output

_fq_nmod_poly_fprint_pretty :: Ptr CFile -> Ptr (Ptr CFqNMod) -> CLong -> CString -> Ptr CFqNModCtx -> IO CInt

_fq_nmod_poly_fprint_pretty file poly len x ctx

Prints the pretty representation of (poly, len) to the stream file, using the string x to represent the indeterminate.

In case of success, returns a positive value. In case of failure, returns a non-positive value.

fq_nmod_poly_fprint_pretty :: Ptr CFile -> Ptr CFqNModPoly -> CString -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_fprint_pretty file poly x ctx

Prints the pretty representation of poly to the stream file, using the string x to represent the indeterminate.

In case of success, returns a positive value. In case of failure, returns a non-positive value.

_fq_nmod_poly_print_pretty :: Ptr (Ptr CFqNMod) -> CLong -> CString -> Ptr CFqNModCtx -> IO CInt

_fq_nmod_poly_print_pretty poly len x ctx

Prints the pretty representation of (poly, len) to stdout, using the string x to represent the indeterminate.

In case of success, returns a positive value. In case of failure, returns a non-positive value.

fq_nmod_poly_print_pretty :: Ptr CFqNModPoly -> CString -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_print_pretty poly x ctx

Prints the pretty representation of poly to stdout, using the string x to represent the indeterminate.

In case of success, returns a positive value. In case of failure, returns a non-positive value.

_fq_nmod_poly_fprint :: Ptr CFile -> Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CInt

_fq_nmod_poly_fprint file poly len ctx

Prints the pretty representation of (poly, len) to the stream file.

In case of success, returns a positive value. In case of failure, returns a non-positive value.

fq_nmod_poly_fprint :: Ptr CFile -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_fprint file poly ctx

Prints the pretty representation of poly to the stream file.

In case of success, returns a positive value. In case of failure, returns a non-positive value.

_fq_nmod_poly_print :: Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CInt

_fq_nmod_poly_print poly len ctx

Prints the pretty representation of (poly, len) to stdout.

In case of success, returns a positive value. In case of failure, returns a non-positive value.

fq_nmod_poly_print :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_print poly ctx

Prints the representation of poly to stdout.

In case of success, returns a positive value. In case of failure, returns a non-positive value.

_fq_nmod_poly_get_str :: Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CString

_fq_nmod_poly_get_str poly len ctx

Returns the plain FLINT string representation of the polynomial (poly, len).

fq_nmod_poly_get_str :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CString

fq_nmod_poly_get_str poly ctx

Returns the plain FLINT string representation of the polynomial poly.

_fq_nmod_poly_get_str_pretty :: Ptr (Ptr CFqNMod) -> CLong -> CString -> Ptr CFqNModCtx -> IO CString

_fq_nmod_poly_get_str_pretty poly len x ctx

Returns a pretty representation of the polynomial (poly, len) using the null-terminated string x as the variable name.

fq_nmod_poly_get_str_pretty :: Ptr CFqNModPoly -> CString -> Ptr CFqNModCtx -> IO CString

fq_nmod_poly_get_str_pretty poly x ctx

Returns a pretty representation of the polynomial poly using the null-terminated string x as the variable name

Inflation and deflation

fq_nmod_poly_inflate :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CULong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_inflate result input inflation ctx

Sets result to the inflated polynomial \(p(x^n)\) where \(p\) is given by input and \(n\) is given by inflation.

fq_nmod_poly_deflate :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> CULong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_deflate result input deflation ctx

Sets result to the deflated polynomial \(p(x^{1/n})\) where \(p\) is given by input and \(n\) is given by deflation. Requires \(n > 0\).

fq_nmod_poly_deflation :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CULong

fq_nmod_poly_deflation input ctx

Returns the largest integer by which input can be deflated. As special cases, returns 0 if input is the zero polynomial and 1 of input is a constant polynomial.