fq_zech_poly.h – univariate polynomials over finite fields (Zech logarithm representation)¶
Description.
Memory management¶
-
void
fq_zech_poly_init
(fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Initialises
poly
for use, with context ctx, and setting its length to zero. A corresponding call tofq_zech_poly_clear()
must be made after finishing with thefq_zech_poly_t
to free the memory used by the polynomial.
-
void
fq_zech_poly_init2
(fq_zech_poly_t poly, slong alloc, const fq_zech_ctx_t ctx)¶ Initialises
poly
with space for at leastalloc
coefficients and sets the length to zero. The allocated coefficients are all set to zero. A corresponding call tofq_zech_poly_clear()
must be made after finishing with thefq_zech_poly_t
to free the memory used by the polynomial.
-
void
fq_zech_poly_realloc
(fq_zech_poly_t poly, slong alloc, const fq_zech_ctx_t ctx)¶ Reallocates the given polynomial to have space for
alloc
coefficients. Ifalloc
is zero the polynomial is cleared and then reinitialised. If the current length is greater thanalloc
the polynomial is first truncated to lengthalloc
.
-
void
fq_zech_poly_fit_length
(fq_zech_poly_t poly, slong len, const fq_zech_ctx_t ctx)¶ If
len
is greater than the number of coefficients currently allocated, then the polynomial is reallocated to have space for at leastlen
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.
-
void
_fq_zech_poly_set_length
(fq_zech_poly_t poly, slong newlen, const fq_zech_ctx_t ctx)¶ Sets the coefficients of
poly
beyondlen
to zero and sets the length ofpoly
tolen
.
-
void
fq_zech_poly_clear
(fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Clears the given polynomial, releasing any memory used. It must be reinitialised in order to be used again.
-
void
_fq_zech_poly_normalise
(fq_zech_poly_t poly, const fq_zech_ctx_t 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.
-
void
_fq_zech_poly_normalise2
(fq_zech_struct *poly, slong *length, const fq_zech_ctx_t 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.
-
void
fq_zech_poly_truncate
(fq_zech_poly_t poly, slong newlen, const fq_zech_ctx_t ctx)¶ Truncates the polynomial to length at most~`n`.
-
void
fq_zech_poly_set_trunc
(fq_zech_poly_t poly1, fq_zech_poly_t poly2, slong newlen, const fq_ctx_t ctx)¶ Sets
poly1
topoly2
truncated to length~`n`.
-
void
_fq_zech_poly_reverse
(fq_zech_struct* output, const fq_zech_struct* input, slong len, slong m, const fq_zech_ctx_t ctx)¶ Sets
output
to the reverse ofinput
, which is of lengthlen
, 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 polynomialoutput
must have space form
coefficients.
-
void
fq_zech_poly_reverse
(fq_zech_poly_t output, const fq_zech_poly_t input, slong m, const fq_zech_ctx_t ctx)¶ Sets
output
to the reverse ofinput
, 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¶
-
long
fq_zech_poly_degree
(fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Returns the degree of the polynomial
poly
.
-
long
fq_zech_poly_length
(fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Returns the length of the polynomial
poly
.
-
fq_zech_struct *
fq_zech_poly_lead
(const fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Returns a pointer to the leading coefficient of
poly
, orNULL
ifpoly
is the zero polynomial.
Randomisation¶
-
void
fq_zech_poly_randtest
(fq_zech_poly_t f, flint_rand_t state, slong len, const fq_zech_ctx_t ctx)¶ Sets \(f\) to a random polynomial of length at most
len
with entries in the field described byctx
.
-
void
fq_zech_poly_randtest_not_zero
(fq_zech_poly_t f, flint_rand_t state, slong len, const fq_zech_ctx_t ctx)¶ Same as
fq_zech_poly_randtest
but guarantees that the polynomial is not zero.
-
void
fq_zech_poly_randtest_monic
(fq_zech_poly_t f, flint_rand_t state, slong len, const fq_zech_ctx_t ctx)¶ Sets \(f\) to a random monic polynomial of length
len
with entries in the field described byctx
.
-
void
fq_zech_poly_randtest_irreducible
(fq_zech_poly_t f, flint_rand_t state, slong len, const fq_zech_ctx_t ctx)¶ Sets \(f\) to a random monic, irreducible polynomial of length
len
with entries in the field described byctx
.
Assignment and basic manipulation¶
-
void
_fq_zech_poly_set
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_ctx_t ctx)¶ Sets
(rop, len
) to(op, len)
.
-
void
fq_zech_poly_set
(fq_zech_poly_t poly1, const fq_zech_poly_t poly2, const fq_zech_ctx_t ctx)¶ Sets the polynomial
poly1
to the polynomialpoly2
.
-
void
fq_zech_poly_set_fq_zech
(fq_zech_poly_t poly, const fq_zech_t c, const fq_zech_ctx_t ctx)¶ Sets the polynomial
poly
toc
.
-
void
fq_zech_poly_set_fmpz_mod_poly
(fq_zech_poly_t rop, const fmpz_mod_poly_t op, fq_zech_ctx_t ctx)¶ Sets the polynomial
rop
to the polynomialop
-
void
fq_zech_poly_set_nmod_poly
(fq_zech_poly_t rop, const nmod_poly_t op, fq_zech_ctx_t ctx)¶ Sets the polynomial
rop
to the polynomialop
-
void
fq_zech_poly_swap
(fq_zech_poly_t op1, fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Swaps the two polynomials
op1
andop2
.
-
void
_fq_zech_poly_zero
(fq_zech_struct *rop, slong len, const fq_zech_ctx_t ctx)¶ Sets
(rop, len)
to the zero polynomial.
-
void
fq_zech_poly_zero
(fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Sets
poly
to the zero polynomial.
-
void void
fq_zech_poly_one
(fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Sets
poly
to the constant polynomial~`1`.
-
void void
fq_zech_poly_gen
(fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Sets
poly
to the polynomial~`x`.
-
void
fq_zech_poly_make_monic
(fq_zech_poly_t rop, const fq_zech_poly_t op, const fq_zech_ctx_t ctx)¶ Sets
rop
toop
, normed to have leading coefficient 1.
-
void
_fq_zech_poly_make_monic
(fq_zech_struct *rop, const fq_zech_struct *op, slong length, const fq_zech_ctx_t ctx)¶ Sets
rop
to(op,length)
, normed to have leading coefficient 1. Assumes thatrop
has enough space for the polynomial, assumes thatop
is not zero (and thus has an invertible leading coefficient).
Getting and setting coefficients¶
-
void
fq_zech_poly_get_coeff
(fq_zech_t x, const fq_zech_poly_t poly, slong n, const fq_zech_ctx_t ctx)¶ Sets \(x\) to the coefficient of \(X^n\) in
poly
.
-
void
fq_zech_poly_set_coeff
(fq_zech_poly_t poly, slong n, const fq_zech_t x, const fq_zech_ctx_t ctx)¶ Sets the coefficient of \(X^n\) in
poly
to \(x\).
-
void
fq_zech_poly_set_coeff_fmpz
(fq_zech_poly_t poly, slong n, const fmpz_t x, const fq_zech_ctx_t ctx)¶ Sets the coefficient of \(X^n\) in the polynomial to \(x\), assuming \(n \geq 0\).
Comparison¶
-
int
fq_zech_poly_equal
(const fq_zech_poly_t poly1, const fq_zech_poly_t poly2, const fq_zech_ctx_t ctx)¶ Returns nonzero if the two polynomials
poly1
andpoly2
are equal, otherwise return zero.
-
int
fq_zech_poly_equal_trunc
(const fq_poly_t poly1, const fq_poly_t poly2, slong n, const fq_ctx_t ctx)¶ Notionally truncate
poly1
andpoly2
to length \(n\) and return nonzero if they are equal, otherwise return zero.
-
int
fq_zech_poly_is_zero
(const fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Returns whether the polynomial
poly
is the zero polynomial.
-
int
fq_zech_poly_is_one
(const fq_zech_poly_t op)¶ Returns whether the polynomial
poly
is equal to the constant polynomial~`1`.
-
int
fq_zech_poly_is_gen
(const fq_zech_poly_t op, const fq_zech_ctx_t ctx)¶ Returns whether the polynomial
poly
is equal to the polynomial~`x`.
-
int
fq_zech_poly_is_unit
(const fq_zech_poly_t op, const fq_zech_ctx_t 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.
-
int
fq_zech_poly_equal_fq_zech
(const fq_zech_poly_t poly, const fq_zech_t c, const fq_zech_ctx_t ctx)¶ Returns whether the polynomial
poly
is equal the (constant) \(\mathbf{F}_q\) elementc
Addition and subtraction¶
-
void
_fq_zech_poly_add
(fq_zech_struct *res, const fq_zech_struct *poly1, slong len1, const fq_zech_struct *poly2, slong len2, const fq_zech_ctx_t ctx)¶ Sets
res
to the sum of(poly1,len1)
and(poly2,len2)
.
-
void
fq_zech_poly_add
(fq_zech_poly_t res, const fq_zech_poly_t poly1, const fq_zech_poly_t poly2, const fq_zech_ctx_t ctx)¶ Sets
res
to the sum ofpoly1
andpoly2
.
-
void
fq_zech_poly_add_series
(fq_poly_t res, const fq_poly_t poly1, const fq_poly_t poly2, slong n, const fq_ctx_t ctx)¶ Notionally truncate
poly1
andpoly2
to lengthn
and setres
to the sum.
-
void
_fq_zech_poly_sub
(fq_zech_struct *res, const fq_zech_struct *poly1, slong len1, const fq_zech_struct *poly2, slong len2, const fq_zech_ctx_t ctx)¶ Sets
res
to the difference of(poly1,len1)
and(poly2,len2)
.
-
void
fq_zech_poly_sub
(fq_zech_poly_t res, const fq_zech_poly_t poly1, const fq_zech_poly_t poly2, const fq_zech_ctx_t ctx)¶ Sets
res
to the difference ofpoly1
andpoly2
.
-
void
fq_zech_poly_sub_series
(fq_poly_t res, const fq_poly_t poly1, const fq_poly_t poly2, slong n, const fq_ctx_t ctx)¶ Notionally truncate
poly1
andpoly2
to lengthn
and setres
to the difference.
-
void
_fq_zech_poly_neg
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_ctx_t ctx)¶ Sets
rop
to the additive inverse of(op,len)
.
-
void
fq_zech_poly_neg
(fq_zech_poly_t res, const fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Sets
res
to the additive inverse ofpoly
.
Scalar multiplication and division¶
-
void
_fq_zech_poly_scalar_mul_fq_zech
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_t x, const fq_zech_ctx_t ctx)¶ Sets
(rop,len)
to the product of(op,len)
by the scalarx
, in the context defined byctx
.
-
void
fq_zech_poly_scalar_mul_fq_zech
(fq_zech_poly_t rop, const fq_zech_poly_t op, const fq_zech_t x, const fq_zech_ctx_t ctx)¶ Sets
(rop,len)
to the product of(op,len)
by the scalarx
, in the context defined byctx
.
-
void
_fq_zech_poly_scalar_addmul_fq_zech
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_t x, const fq_zech_ctx_t ctx)¶ Adds to
(rop,len)
the product of(op,len)
by the scalarx
, in the context defined byctx
. In particular, assumes the same length forop
androp
.
-
void
fq_zech_poly_scalar_addmul_fq_zech
(fq_zech_poly_t rop, const fq_zech_poly_t op, const fq_zech_t x, const fq_zech_ctx_t ctx)¶ Adds to
rop
the product ofop
by the scalarx
, in the context defined byctx
.
-
void
_fq_zech_poly_scalar_submul_fq_zech
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_t x, const fq_zech_ctx_t ctx)¶ Substracts from
(rop,len)
the product of(op,len)
by the scalarx
, in the context defined byctx
. In particular, assumes the same length forop
androp
.
-
void
fq_zech_poly_scalar_submul_fq_zech
(fq_zech_poly_t rop, const fq_zech_poly_t op, const fq_zech_t x, const fq_zech_ctx_t ctx)¶ Substracts from
rop
the product ofop
by the scalarx
, in the context defined byctx
.
Multiplication¶
-
void
_fq_zech_poly_mul_classical
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, const fq_zech_ctx_t ctx)¶ Sets
(rop, len1 + len2 - 1)
to the product of(op1, len1)
and(op2, len2)
, assuming thatlen1
is at leastlen2
and neither is zero.Permits zero padding. Does not support aliasing of
rop
with eitherop1
orop2
.
-
void
fq_zech_poly_mul_classical
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the product ofop1
andop2
using classical polynomial multiplication.
-
void
_fq_zech_poly_mul_reorder
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, const fq_zech_ctx_t ctx)¶ Sets
(rop, len1 + len2 - 1)
to the product of(op1, len1)
and(op2, len2)
, assuming thatlen1
andlen2
are non-zero.Permits zero padding. Supports aliasing.
-
void
fq_zech_poly_mul_reorder
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the product ofop1
andop2
, reordering the two indeterminates \(X\) and \(Y\) when viewing the polynomials as elements of \(\mathbf{F}_p[X,Y]\).Suppose \(\mathbf{F}_q = \mathbf{F}_p[X]/ (f(X))\) and recall that elements of \(\mathbf{F}_q\) are internally represented by elements of type
fmpz_poly
. For small degree extensions but polynomials in \(\mathbf{F}_q[Y]\) of large degree~`n`, we change the representation to\[\begin{split}\begin{split} g(Y) & = \sum_{i=0}^{n} a_i(X) Y^i \\ & = \sum_{j=0}^{d} \sum_{i=0}^{n} \text{Coeff}(a_i(X), j) Y^i. \end{split}\end{split}\]This allows us to use a poor algorithm (such as classical multiplication) in the \(X\)-direction and leverage the existing fast integer multiplication routines in the \(Y\)-direction where the polynomial degree~`n` is large.
-
void
_fq_zech_poly_mul_KS
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, const fq_zech_ctx_t 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
andlen2
. Supports aliasing.
-
void
fq_zech_poly_mul_KS
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the product ofop1
andop2
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.
-
void
_fq_zech_poly_mul
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, const fq_zech_ctx_t 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.
-
void
fq_zech_poly_mul
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the product ofop1
andop2
, choosing an appropriate algorithm.
-
void
_fq_zech_poly_mullow_classical
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, slong n, const fq_zech_ctx_t ctx)¶ Sets
(rop, n)
to the first \(n\) coefficients of(op1, len1)
multiplied by(op2, len2)
.Assumes
0 < n <= len1 + len2 - 1
. Assumes neitherlen1
norlen2
is zero.
-
void
fq_zech_poly_mullow_classical
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, slong n, const fq_zech_ctx_t ctx)¶ Sets
rop
to the product ofop1
andop2
, computed using the classical or schoolbook method.
-
void
_fq_zech_poly_mullow_KS
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, slong n, const fq_zech_ctx_t ctx)¶ Sets
(rop, n)
to the lowest \(n\) coefficients of the product of(op1, len1)
and(op2, len2)
.Assumes that
len1
andlen2
are positive, but does allow for the polynomials to be zero-padded. The polynomials may be zero, too. Assumes \(n\) is positive. Supports aliasing betweenrop
,op1
andop2
.
-
void
fq_zech_poly_mullow_KS
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, slong n, const fq_zech_ctx_t ctx)¶ Sets
rop
to the product ofop1
andop2
.
-
void
_fq_zech_poly_mullow
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, slong n, const fq_zech_ctx_t 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.
-
void
fq_zech_poly_mullow
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, slong n, const fq_zech_ctx_t ctx)¶ Sets
rop
to the lowest \(n\) coefficients of the product ofop1
andop2
.
-
void
_fq_zech_poly_mulhigh_classical
(fq_zech_struct *res, const fq_zech_struct *poly1, slong len1, const fq_zech_struct *poly2, slong len2, slong start, const fq_zech_ctx_t ctx)¶ Computes the product of
(poly1, len1)
and(poly2, len2)
and writes the coefficients fromstart
onwards into the high coefficients ofres
, the remaining coefficients being arbitrary but reduced. Assumes thatlen1 >= len2 > 0
. Aliasing of inputs and output is not permitted. Algorithm is classical multiplication.
-
void
fq_zech_poly_mulhigh_classical
(fq_zech_poly_t res, const fq_zech_poly_t poly1, const fq_zech_poly_t poly2, slong start, const fq_zech_ctx_t ctx)¶ Computes the product of
poly1
andpoly2
and writes the coefficients fromstart
onwards into the high coefficients ofres
, the remaining coefficients being arbitrary but reduced. Algorithm is classical multiplication.
-
void
_fq_zech_poly_mulhigh
(fq_zech_struct *res, const fq_zech_struct *poly1, slong len1, const fq_zech_struct *poly2, slong len2, slong start, const fq_zech_ctx_t ctx)¶ Computes the product of
(poly1, len1)
and(poly2, len2)
and writes the coefficients fromstart
onwards into the high coefficients ofres
, the remaining coefficients being arbitrary but reduced. Assumes thatlen1 >= len2 > 0
. Aliasing of inputs and output is not permitted.
-
void
fq_zech_poly_mulhigh
(fq_zech_poly_t res, const fq_zech_poly_t poly1, const fq_zech_poly_t poly2, slong start, const fq_zech_ctx_t ctx)¶ Computes the product of
poly1
andpoly2
and writes the coefficients fromstart
onwards into the high coefficients ofres
, the remaining coefficients being arbitrary but reduced.
-
void
_fq_zech_poly_mulmod
(fq_zech_struct* res, const fq_zech_struct* poly1, slong len1, const fq_zech_struct* poly2, slong len2, const fq_zech_struct* f, slong lenf, const fq_zech_ctx_t ctx)¶ Sets
res
to the remainder of the product ofpoly1
andpoly2
upon polynomial division byf
.It is required that
len1 + len2 - lenf > 0
, which is equivalent to requiring that the result will actually be reduced. Otherwise, simply use_fq_zech_poly_mul
instead.Aliasing of
f
andres
is not permitted.
-
void
fq_zech_poly_mulmod
(fq_zech_poly_t res, const fq_zech_poly_t poly1, const fq_zech_poly_t poly2, const fq_zech_poly_t f, const fq_zech_ctx_t ctx)¶ Sets
res
to the remainder of the product ofpoly1
andpoly2
upon polynomial division byf
.
-
void
_fq_zech_poly_mulmod_preinv
(fq_zech_struct* res, const fq_zech_struct* poly1, slong len1, const fq_zech_struct* poly2, slong len2, const fq_zech_struct* f, slong lenf, const fq_zech_struct* finv, slong lenfinv, const fq_zech_ctx_t ctx)¶ Sets
res
to the remainder of the product ofpoly1
andpoly2
upon polynomial division byf
.It is required that
finv
is the inverse of the reverse off
modx^lenf
. It is required thatlen1 + len2 - lenf > 0
, which is equivalent to requiring that the result will actually be reduced. Otherwise, simply use_fq_zech_poly_mul
instead.Aliasing of
f
orfinv
andres
is not permitted.
-
void
fq_zech_poly_mulmod_preinv
(fq_zech_poly_t res, const fq_zech_poly_t poly1, const fq_zech_poly_t poly2, const fq_zech_poly_t f, const fq_zech_poly_t finv, const fq_zech_ctx_t ctx)¶ Sets
res
to the remainder of the product ofpoly1
andpoly2
upon polynomial division byf
.finv
is the inverse of the reverse off
.
Squaring¶
-
void
_fq_zech_poly_sqr_classical
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_ctx_t 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 eitherop1
orop2
.
-
void
fq_zech_poly_sqr_classical
(fq_zech_poly_t rop, const fq_zech_poly_t op, const fq_zech_ctx_t ctx)¶ Sets
rop
to the square ofop
using classical polynomial multiplication.
-
void
_fq_zech_poly_sqr_KS
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_ctx_t ctx)¶ Sets
(rop, 2*len - 1)
to the square of(op, len)
.Permits zero padding and places no assumptions on the lengths
len1
andlen2
. Supports aliasing.
-
void
fq_zech_poly_sqr_KS
(fq_zech_poly_t rop, const fq_zech_poly_t op, const fq_zech_ctx_t ctx)¶ Sets
rop
to the squareop
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.
-
void
_fq_zech_poly_sqr
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_ctx_t ctx)¶ Sets
(rop, 2* len - 1)
to the square of(op, len)
, choosing an appropriate algorithm.Permits zero padding. Does not support aliasing.
-
void
fq_zech_poly_sqr
(fq_zech_poly_t rop, const fq_zech_poly_t op, const fq_zech_ctx_t ctx)¶ Sets
rop
to the square ofop
, choosing an appropriate algorithm.
Powering¶
-
void
_fq_zech_poly_pow
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, ulong e, const fq_zech_ctx_t ctx)¶ Sets
rop = op^e
, assuming thate, len > 0
and thatres
has space fore*(len - 1) + 1
coefficients. Does not support aliasing.
-
void
fq_zech_poly_pow
(fq_zech_poly_t rop, const fq_zech_poly_t op, ulong e, const fq_zech_ctx_t ctx)¶ Computes
rop = op^e
. If \(e\) is zero, returns one, so that in particular0^0 = 1
.
-
void
_fq_zech_poly_powmod_ui_binexp
(fq_zech_struct* res, const fq_zech_struct* poly, ulong e, const fq_zech_struct* f, slong lenf, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree > 0
.We require
lenf > 1
. It is assumed thatpoly
is already reduced modulof
and zero-padded as necessary to have length exactlylenf - 1
. The outputres
must have room forlenf - 1
coefficients.
-
void
fq_zech_poly_powmod_ui_binexp
(fq_zech_poly_t res, const fq_zech_poly_t poly, ulong e, const fq_zech_poly_t f, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree >= 0
.
-
void
_fq_zech_poly_powmod_ui_binexp_preinv
(fq_zech_struct* res, const fq_zech_struct* poly, ulong e, const fq_zech_struct* f, slong lenf, const fq_zech_struct* finv, slong lenfinv, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree > 0
. We requirefinv
to be the inverse of the reverse off
.We require
lenf > 1
. It is assumed thatpoly
is already reduced modulof
and zero-padded as necessary to have length exactlylenf - 1
. The outputres
must have room forlenf - 1
coefficients.
-
void
fq_zech_poly_powmod_ui_binexp_preinv
(fq_zech_poly_t res, const fq_zech_poly_t poly, ulong e, const fq_zech_poly_t f, const fq_zech_poly_t finv, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree >= 0
. We requirefinv
to be the inverse of the reverse off
.
-
void
_fq_zech_poly_powmod_fmpz_binexp
(fq_zech_struct* res, const fq_zech_struct* poly, fmpz_t e, const fq_zech_struct* f, slong lenf, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree > 0
.We require
lenf > 1
. It is assumed thatpoly
is already reduced modulof
and zero-padded as necessary to have length exactlylenf - 1
. The outputres
must have room forlenf - 1
coefficients.
-
void
fq_zech_poly_powmod_fmpz_binexp
(fq_zech_poly_t res, const fq_zech_poly_t poly, fmpz_t e, const fq_zech_poly_t f, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree >= 0
.
-
void
_fq_zech_poly_powmod_fmpz_binexp_preinv
(fq_zech_struct* res, const fq_zech_struct* poly, fmpz_t e, const fq_zech_struct* f, slong lenf, const fq_zech_struct* finv, slong lenfinv, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree > 0
. We requirefinv
to be the inverse of the reverse off
.We require
lenf > 1
. It is assumed thatpoly
is already reduced modulof
and zero-padded as necessary to have length exactlylenf - 1
. The outputres
must have room forlenf - 1
coefficients.
-
void
fq_zech_poly_powmod_fmpz_binexp_preinv
(fq_zech_poly_t res, const fq_zech_poly_t poly, fmpz_t e, const fq_zech_poly_t f, const fq_zech_poly_t finv, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree >= 0
. We requirefinv
to be the inverse of the reverse off
.
-
void
_fq_zech_poly_powmod_fmpz_sliding_preinv
(fq_zech_struct* res, const fq_zech_struct* poly, fmpz_t e, ulong k, const fq_zech_struct* f, slong lenf, const fq_zech_struct* finv, slong lenfinv, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using sliding-window exponentiation with window sizek
. We requiree > 0
. We requirefinv
to be the inverse of the reverse off
. Ifk
is set to zero, then an “optimum” size will be selected automatically base one
.We require
lenf > 1
. It is assumed thatpoly
is already reduced modulof
and zero-padded as necessary to have length exactlylenf - 1
. The outputres
must have room forlenf - 1
coefficients.
-
void
fq_zech_poly_powmod_fmpz_sliding_preinv
(fq_zech_poly_t res, const fq_zech_poly_t poly, fmpz_t e, ulong k, const fq_zech_poly_t f, const fq_zech_poly_t finv, const fq_zech_ctx_t ctx)¶ Sets
res
topoly
raised to the powere
modulof
, using sliding-window exponentiation with window sizek
. We requiree >= 0
. We requirefinv
to be the inverse of the reverse off
. Ifk
is set to zero, then an “optimum” size will be selected automatically base one
.
-
void
_fq_zech_poly_powmod_x_fmpz_preinv
(fq_zech_struct * res, const fmpz_t e, const fq_zech_struct * f, slong lenf, const fq_zech_struct * finv, slong lenfinv, const fq_zech_ctx_t ctx)¶ Sets
res
tox
raised to the powere
modulof
, using sliding window exponentiation. We requiree > 0
. We requirefinv
to be the inverse of the reverse off
.We require
lenf > 2
. The outputres
must have room forlenf - 1
coefficients.
-
void
fq_zech_poly_powmod_x_fmpz_preinv
(fq_zech_poly_t res, const fmpz_t e, const fq_zech_poly_t f, const fq_zech_poly_t finv, const fq_zech_ctx_t ctx)¶ Sets
res
tox
raised to the powere
modulof
, using sliding window exponentiation. We requiree >= 0
. We requirefinv
to be the inverse of the reverse off
.
Shifting¶
-
void
_fq_zech_poly_shift_left
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, slong n, const fq_zech_ctx_t 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 thatrop
fitslen + n
elements. Supports aliasing betweenrop
andop
.
-
void
fq_zech_poly_shift_left
(fq_zech_poly_t rop, const fq_zech_poly_t op, slong n, const fq_zech_ctx_t ctx)¶ Sets
rop
toop
shifted left by \(n\) coeffs. Zero coefficients are inserted.
-
void
_fq_zech_poly_shift_right
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, slong n, const fq_zech_ctx_t ctx)¶ Sets
(rop, len - n)
to(op, len)
shifted right by \(n\) coefficients.Assumes that
len
and \(n\) are positive, thatlen > n
, and thatrop
fitslen - n
elements. Supports aliasing betweenrop
andop
, although in this case the top coefficients ofop
are not set to zero.
-
void
fq_zech_poly_shift_right
(fq_zech_poly_t rop, const fq_zech_poly_t op, slong n, const fq_zech_ctx_t ctx)¶ Sets
rop
toop
shifted right by \(n\) coefficients. If \(n\) is equal to or greater than the current length ofop
,rop
is set to the zero polynomial.
Norms¶
-
long
_fq_zech_poly_hamming_weight
(const fq_zech_poly *op, slong len, const fq_zech_ctx_t ctx)¶ Returns the number of non-zero entries in
(op, len)
.
-
long
fq_zech_poly_hamming_weight
(const fq_zech_poly_t op, const fq_zech_ctx_t ctx)¶ Returns the number of non-zero entries in the polynomial
op
.
Euclidean division¶
-
void
_fq_zech_poly_divrem_basecase
(fq_zech_struct *Q, fq_zech_struct *R, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fq_zech_t invB, const fq_zech_ctx_t ctx)¶ Computes
(Q, lenA - lenB + 1)
,(R, lenA)
such that \(A = B Q + R\) with \(0 \leq \len(R) < \len(B)\).Assumes that the leading coefficient of \(B\) is invertible and that
invB
is its inverse.Assumes that \(\len(A), \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.
-
void
fq_zech_poly_divrem_basecase
(fq_zech_poly_t Q, fq_zech_poly_t R, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t ctx)¶ Computes \(Q\), \(R\) such that \(A = B Q + R\) with \(0 \leq \len(R) < \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.
-
void
_fq_zech_poly_divrem
(fq_zech_struct *Q, fq_zech_struct *R, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fq_zech_t invB, const fq_zech_ctx_t ctx)¶ Computes
(Q, lenA - lenB + 1)
,(R, lenA)
such that \(A = B Q + R\) with \(0 \leq \len(R) < \len(B)\).Assumes that the leading coefficient of \(B\) is invertible and that
invB
is its inverse.Assumes that \(\len(A), \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.
-
void
fq_zech_poly_divrem
(fq_zech_poly_t Q, fq_zech_poly_t R, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t ctx)¶ Computes \(Q\), \(R\) such that \(A = B Q + R\) with \(0 \leq \len(R) < \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.
-
void
fq_zech_poly_divrem_f
(fq_zech_t f, fq_zech_poly_t Q, fq_zech_poly_t R, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t 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 \len(R) < \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.
-
void
_fq_zech_poly_rem
(fq_zech_struct *R, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fq_zech_t invB, const fq_zech_ctx_t 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 thatinvB
is its inverse.
-
void
fq_zech_poly_rem
(fq_zech_poly_t R, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t ctx)¶ Sets
R
to the remainder of the division ofA
byB
in the context described byctx
.
-
void
_fq_zech_poly_div_basecase
(fq_zech_struct *Q, fq_zech_struct *R, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fq_zech_t invB, const fq_zech_ctx_t ctx)¶ Notationally, computes \(Q\), \(R\) such that \(A = B Q + R\) with \(0 \leq \len(R) < \len(B)\) but only sets
(Q, lenA - lenB + 1)
.Requires temporary space
(R, lenA)
. IfR
isNULL
, then the temporary space will be allocated. Allows aliasing only between \(A\) and \(R\). Allows zero-padding in \(A\) but not in \(B\). Assumes that the leading coefficient of \(B\) is a unit.
-
void
fq_zech_poly_div_basecase
(fq_zech_poly_t Q, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t ctx)¶ Notionally finds polynomials \(Q\) and \(R\) such that \(A = B Q + R\) with \(\len(R) < \len(B)\), but returns only
Q
. If \(\len(B) = 0\) an exception is raised.
-
void
_fq_zech_poly_divrem_divconquer_recursive
(fq_zech_struct * Q, fq_zech_struct * BQ, fq_zech_struct * W, const fq_zech_struct * A, const fq_zech_struct * B, slong lenB, const fq_zech_t invB, const fq_zech_ctx_t ctx)¶ Computes
(Q, lenB)
,(BQ, 2 lenB - 1)
such that \(BQ = B \times Q\) and \(A = B Q + R\) where \(0 \leq \len(R) < \len(B)\).Assumes that the leading coefficient of \(B\) is invertible and that
invB
is the inverse.Assumes \(\len(B) > 0\). Allows zero-padding in
(A, lenA)
. Requires a temporary array(W, 2 lenB - 1)
. No aliasing of input and output operands is allowed.This function does not read the bottom \(\len(B) - 1\) coefficients from \(A\), which means that they might not even need to exist in allocated memory.
-
void
_fq_zech_poly_divrem_divconquer
(fq_zech_struct * Q, fq_zech_struct * R, const fq_zech_struct * A, slong lenA, const fq_zech_struct * B, slong lenB, const fq_zech_t invB, const fq_zech_ctx_t ctx)¶ Computes
(Q, lenA - lenB + 1)
,(R, lenA)
such that \(A = B Q + R\) and \(0 \leq \len(R) < \len(B)\).Assumes that the leading coefficient of \(B\) is invertible and that
invB
is the inverse.Assumes \(\len(A) \geq \len(B) > 0\). Allows zero-padding in
(A, lenA)
. No aliasing of input and output operands is allowed.
-
void
fq_zech_poly_divrem_divconquer
(fq_zech_poly_t Q, fq_zech_poly_t R, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t ctx)¶ Computes \(Q\), \(R\) such that \(A = B Q + R\) and \(0 \leq \len(R) < \len(B)\).
Assumes that \(B\) is non-zero and that the leading coefficient of \(B\) is invertible.
-
void
_fq_zech_poly_div_newton_n_preinv
(fq_zech_struct* Q, const fq_zech_struct* A, slong lenA, const fq_zech_struct* B, slong lenB, const fq_zech_struct* Binv, slong lenBinv, const fq_zech_struct ctx_t)¶ Notionally computes polynomials \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R)\) less than
lenB
, whereA
is of lengthlenA
andB
is of lengthlenB
, 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^{\len(B)}\).The algorithm used is to reverse the polynomials and divide the resulting power series, then reverse the result.
-
void
fq_zech_poly_div_newton_n_preinv
(fq_zech_poly_t Q, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_poly_t Binv, const fq_zech_ctx_t ctx)¶ Notionally computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \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^{\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.
-
void
_fq_zech_poly_divrem_newton_n_preinv
(fq_zech_struct* Q, fq_zech_struct* R, const fq_zech_struct* A, slong lenA, const fq_zech_struct* B, slong lenB, const fq_zech_struct* Binv, slong lenBinv, const fq_zech_ctx_t ctx)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R)\) less than
lenB
, where \(A\) is of lengthlenA
and \(B\) is of lengthlenB
. We require that \(Q\) have space forlenA - lenB + 1
coefficients. Furthermore, we assume that \(Binv\) is the inverse of the reverse of \(B\) mod \(x^{\len(B)}\). The algorithm used is to calldiv_newton_preinv()
and then multiply out and compute the remainder.
-
void
fq_zech_poly_divrem_newton_n_preinv
(fq_zech_poly_t Q, fq_zech_poly_t R, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_poly_t Binv, const fq_zech_ctx_t ctx)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \len(B)\). We assume \(Binv\) is the inverse of the reverse of \(B\) mod \(x^{\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.
-
void
_fq_zech_poly_inv_series_newton
(fq_zech_struct* Qinv, const fq_zech_struct* Q, slong n, const fq_zech_ctx_t ctx)¶ Given
Q
of lengthn
whose constant coefficient is invertible modulo the given modulus, find a polynomialQinv
of lengthn
such thatQ * Qinv
is1
modulo \(x^n\). Requiresn > 0
. This function can be viewed as inverting a power series via Newton iteration.
-
void
fq_zech_poly_inv_series_newton
(fq_zech_poly_t Qinv, const fq_zech_poly_t Q, slong n, const fq_zech_ctx_t ctx)¶ Given
Q
findQinv
such thatQ * Qinv
is1
modulo \(x^n\). The constant coefficient ofQ
must be invertible modulo the modulus ofQ
. An exception is raised if this is not the case or ifn = 0
. This function can be viewed as inverting a power series via Newton iteration.
-
void
_fq_zech_poly_inv_series
(fq_zech_struct* Qinv, const fq_zech_struct* Q, slong n, const fq_zech_ctx_t ctx)¶ Given
Q
of lengthn
whose constant coefficient is invertible modulo the given modulus, find a polynomialQinv
of lengthn
such thatQ * Qinv
is1
modulo \(x^n\). Requiresn > 0
.
-
void
fq_zech_poly_inv_series
(fq_zech_poly_t Qinv, const fq_zech_poly_t Q, slong n, const fq_zech_ctx_t ctx)¶ Given
Q
findQinv
such thatQ * Qinv
is1
modulo \(x^n\). The constant coefficient ofQ
must be invertible modulo the modulus ofQ
. An exception is raised if this is not the case or ifn = 0
.
-
void
_fq_zech_poly_div_series
(fmpz * Q, const fmpz * A, slong Alen, const fmpz * B, slong Blen, slong n, fq_ctx_t ctx)¶ Set
(Q, n)
to the quotient of the series(A, Alen
) and(B, Blen)
assumingAlen, Blen <= n
. We assume the bottom coefficient ofB
is invertible.
-
void
fq_zech_poly_div_series
(fmpz_mod_poly_t Q, const fmpz_mod_poly_t A, const fmpz_mod_poly_t B, slong n, fq_ctx_t 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¶
-
void
fq_zech_poly_gcd
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the greatest common divisor ofop1
andop2
, 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.
-
long
_fq_zech_poly_gcd
(fq_zech_struct* G, const fq_zech_struct* A, slong lenA, const fq_zech_struct* B, slong lenB, const fq_zech_ctx_t ctx)¶ Computes the GCD of \(A\) of length
lenA
and \(B\) of lengthlenB
, wherelenA >= 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 forlenB
coefficients.
-
void
fq_zech_poly_gcd_euclidean
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the greatest common divisor ofop1
andop2
, using the Euclidean 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.
-
long
_fq_zech_poly_gcd_euclidean
(fq_zech_struct* G, const fq_zech_struct* A, slong lenA, const fq_zech_struct* B, slong lenB, const fq_zech_ctx_t ctx)¶ Computes the GCD of \(A\) of length
lenA
and \(B\) of lengthlenB
, wherelenA >= 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 forlenB
coefficients.
-
slong
_fq_zech_poly_hgcd
(fq_zech_struct **M, slong *lenM, fq_zech_struct *A, slong *lenA, fq_zech_struct *B, slong *lenB, const fq_zech_struct * a, slong lena, const fq_zech_struct *b, slong lenb, const fq_zech_ctx_t ctx)¶ Computes the HGCD of \(a\) and \(b\), that is, a matrix~`M`, a sign~`sigma` and two polynomials \(A\) and \(B\) such that
\[(A,B)^t = \sigma M^{-1} (a,b)^t.\]Assumes that \(\len(a) > \len(b) > 0\).
Assumes that \(A\) and \(B\) have space of size at least \(\len(a)\) and \(\len(b)\), respectively. On exit,
*lenA
and*lenB
will contain the correct lengths of \(A\) and \(B\).Assumes that
M[0]
,M[1]
,M[2]
, andM[3]
each point to a vector of size at least \(\len(a)\).
-
void
fq_zech_poly_gcd_hgcd
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the greatest common divisor ofop1
andop2
, using the 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.
-
long
_fq_zech_poly_gcd_hgcd
(fq_zech_struct* G, const fq_zech_struct* A, slong lenA, const fq_zech_struct* B, slong lenB, const fq_zech_ctx_t ctx)¶ Computes the GCD of \(A\) of length
lenA
and \(B\) of lengthlenB
using the HGCD algorithm, wherelenA >= 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 forlenB
coefficients.
-
slong
_fq_zech_poly_gcd_euclidean_f
(fq_zech_t f, fq_zech_struct *G, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fq_zech_ctx_t ctx)¶ Either sets \(f = 1\) and \(G\) to the greatest common divisor of \((A,\len(A))\) and \((B, \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 \(\len(A) \geq \len(B) > 0\) and that the vector \(G\) has space for sufficiently many coefficients.
-
void
fq_zech_poly_gcd_euclidean_f
(fq_zech_t f, fq_zech_poly_t G, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t 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
.
-
slong
_fq_zech_poly_xgcd_euclidean
(fq_zech_struct *G, fq_zech_struct *S, fq_zech_struct *T, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fmpz_t invB, const fq_zech_ctx_t 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 \(\len(A) \geq \len(B) \geq 1\) and \((\len(A),\len(B)) \neq (1,1)\).
No attempt is made to make the GCD monic.
Requires that \(G\) have space for \(\len(B)\) coefficients. Writes \(\len(B)-1\) and \(\len(A)-1\) coefficients to \(S\) and \(T\), respectively. Note that, in fact, \(\len(S) \leq \max(\len(B) - \len(G), 1)\) and \(\len(T) \leq \max(\len(A) - \len(G), 1)\).
No aliasing of input and output operands is permitted.
-
void
fq_zech_poly_xgcd_euclidean
(fq_zech_poly_t G, fq_zech_poly_t S, fq_zech_poly_t T, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t 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
andT
are computed such thatS*A + T*B = G
. The length ofS
will be at mostlenB
and the length ofT
will be at mostlenA
.
-
slong
_fq_zech_poly_xgcd
(fq_zech_struct *G, fq_zech_struct *S, fq_zech_struct *T, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fmpz_t invB, const fq_zech_ctx_t 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 \(\len(A) \geq \len(B) \geq 1\) and \((\len(A),\len(B)) \neq (1,1)\).
No attempt is made to make the GCD monic.
Requires that \(G\) have space for \(\len(B)\) coefficients. Writes \(\len(B)-1\) and \(\len(A)-1\) coefficients to \(S\) and \(T\), respectively. Note that, in fact, \(\len(S) \leq \max(\len(B) - \len(G), 1)\) and \(\len(T) \leq \max(\len(A) - \len(G), 1)\).
No aliasing of input and output operands is permitted.
-
void
fq_zech_poly_xgcd
(fq_zech_poly_t G, fq_zech_poly_t S, fq_zech_poly_t T, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t 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
andT
are computed such thatS*A + T*B = G
. The length ofS
will be at mostlenB
and the length ofT
will be at mostlenA
.
-
slong
_fq_zech_poly_xgcd_euclidean_f
(fq_zech_t f, fq_zech_struct *G, fq_zech_struct *S, fq_zech_struct *T, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fmpz_t invB, const fq_zech_ctx_t 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 \(\len(A) \geq \len(B) \geq 1\) and \((\len(A),\len(B)) \neq (1,1)\).
No attempt is made to make the GCD monic.
Requires that \(G\) have space for \(\len(B)\) coefficients. Writes \(\len(B)-1\) and \(\len(A)-1\) coefficients to \(S\) and \(T\), respectively. Note that, in fact, \(\len(S) \leq \max(\len(B) - \len(G), 1)\) and \(\len(T) \leq \max(\len(A) - \len(G), 1)\).
No aliasing of input and output operands is permitted.
-
void
fq_zech_poly_xgcd_euclidean_f
(fq_zech_t f, fq_zech_poly_t G, fq_zech_poly_t S, fq_zech_poly_t T, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t 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
andT
are computed such thatS*A + T*B = G
; otherwise, they are undefined. The length ofS
will be at mostlenB
and the length ofT
will be at mostlenA
.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¶
-
int
_fq_zech_poly_divides
(fq_zech_struct *Q, const fq_zech_struct *A, slong lenA, const fq_zech_struct *B, slong lenB, const fq_zech_t invB, const fq_zech_ctx_t ctx)¶ Returns \(1\) if
(B, lenB)
divides(A, lenA)
exactly and sets \(Q\) to the quotient, otherwise returns \(0\).It is assumed that \(\len(A) \geq \len(B) > 0\) and that \(Q\) has space for \(\len(A) - \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.
-
int
fq_zech_poly_divides
(fq_zech_poly_t Q, const fq_zech_poly_t A, const fq_zech_poly_t B, const fq_zech_ctx_t 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¶
-
void
_fq_zech_poly_derivative
(fq_zech_struct *rop, const fq_zech_struct *op, slong len, const fq_zech_ctx_t ctx)¶ Sets
(rop, len - 1)
to the derivative of(op, len)
. Also handles the cases wherelen
is \(0\) or \(1\) correctly. Supports aliasing ofrop
andop
.
-
void
fq_zech_poly_derivative
(fq_zech_poly_t rop, const fq_zech_poly_t op, const fq_zech_ctx_t ctx)¶ Sets
rop
to the derivative ofop
.
Evaluation¶
-
void
_fq_zech_poly_evaluate_fq_zech
(fq_zech_t rop, const fq_zech_struct *op, slong len, const fq_zech_t a, const fq_zech_ctx_t 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.
-
void
fq_zech_poly_evaluate_fq_zech
(fq_zech_t rop, const fq_zech_poly_t f, const fq_zech_t a, const fq_zech_ctx_t ctx)¶ Sets
rop
to the value of \(f(a)\).As the coefficient ring \(\mathbf{F}_q\) is finite, Horner’s method is sufficient.
Composition¶
-
void
_fq_zech_poly_compose_divconquer
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, const fq_zech_ctx_t ctx)¶ Computes the composition of
(op1, len1)
and(op2, len2)
using a divide and conquer approach and places the result intorop
, assumingrop
can hold the output of length(len1 - 1) * (len2 - 1) + 1
.Assumes
len1, len2 > 0
. Does not support aliasing betweenrop
and any of(op1, len1)
and(op2, len2)
.
-
void
fq_zech_poly_compose_divconquer
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the composition ofop1
andop2
. To be precise about the order of composition, denotingrop
,op1
, andop2
by \(f\), \(g\), and \(h\), respectively, sets \(f(t) = g(h(t))\).
-
void
_fq_zech_poly_compose_horner
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, const fq_zech_ctx_t 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 thatop1
andop2
are non-zero polynomials. Does not support aliasing between any of the inputs and the output.
-
void
fq_zech_poly_compose_horner
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the composition ofop1
andop2
. To be more precise, denotingrop
,op1
, andop2
by \(f\), \(g\), and \(h\), sets \(f(t) = g(h(t))\).This implementation uses Horner’s method.
-
void
_fq_zech_poly_compose
(fq_zech_struct *rop, const fq_zech_struct *op1, slong len1, const fq_zech_struct *op2, slong len2, const fq_zech_ctx_t 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 thatop1
andop2
are non-zero polynomials. Does not support aliasing between any of the inputs and the output.
-
void
fq_zech_poly_compose
(fq_zech_poly_t rop, const fq_zech_poly_t op1, const fq_zech_poly_t op2, const fq_zech_ctx_t ctx)¶ Sets
rop
to the composition ofop1
andop2
. To be precise about the order of composition, denotingrop
,op1
, andop2
by \(f\), \(g\), and \(h\), respectively, sets \(f(t) = g(h(t))\).
-
void
_fq_zech_poly_compose_mod_horner
(fq_zech_struct * res, const fq_zech_struct * f, slong lenf, const fq_zech_struct * g, const fq_zech_struct * h, slong lenh, const fq_zech_ctx_t 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.
-
void
fq_zech_poly_compose_mod_horner
(fq_zech_poly_t res, const fq_zech_poly_t f, const fq_zech_poly_t g, const fq_zech_poly_t h, const fq_zech_ctx_t ctx)¶ Sets
res
to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero. The algorithm used is Horner’s rule.
-
void
_fq_zech_poly_compose_mod_horner_preinv
(fq_zech_struct * res, const fq_zech_struct * f, slong lenf, const fq_zech_struct * g, const fq_zech_struct * h, slong lenh, const fq_zech_struct * hinv, slong lenhiv, const fq_zech_ctx_t 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 requirehinv
to be the inverse of the reverse ofh
. The output is not allowed to be aliased with any of the inputs.The algorithm used is Horner’s rule.
-
void
fq_zech_poly_compose_mod_horner_preinv
(fq_zech_poly_t res, const fq_zech_poly_t f, const fq_zech_poly_t g, const fq_zech_poly_t h, const fq_zech_poly_t hinv, const fq_zech_ctx_t 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 requirehinv
to be the inverse of the reverse ofh
. The algorithm used is Horner’s rule.
-
void
_fq_zech_poly_compose_mod_brent_kung
(fq_zech_struct * res, const fq_zech_struct * f, slong lenf, const fq_zech_struct * g, const fq_zech_struct * h, slong lenh, const fq_zech_ctx_t 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.
-
void
fq_zech_poly_compose_mod_brent_kung
(fq_zech_poly_t res, const fq_zech_poly_t f, const fq_zech_poly_t g, const fq_zech_poly_t h, const fq_zech_ctx_t 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.
-
void
_fq_zech_poly_compose_mod_brent_kung_preinv
(fq_zech_struct * res, const fq_zech_struct * f, slong lenf, const fq_zech_struct * g, const fq_zech_struct * h, slong lenh, const fq_zech_struct * hinv, slong lenhiv, const fq_zech_ctx_t 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 requirehinv
to be the inverse of the reverse ofh
. The output is not allowed to be aliased with any of the inputs.The algorithm used is the Brent-Kung matrix algorithm.
-
void
fq_zech_poly_compose_mod_brent_kung_preinv
(fq_zech_poly_t res, const fq_zech_poly_t f, const fq_zech_poly_t g, const fq_zech_poly_t h, const fq_zech_poly_t hinv, const fq_zech_ctx_t 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 requirehinv
to be the inverse of the reverse ofh
. The algorithm used is the Brent-Kung matrix algorithm.
-
void
_fq_zech_poly_compose_mod
(fq_zech_struct * res, const fq_zech_struct * f, slong lenf, const fq_zech_struct * g, const fq_zech_struct * h, slong lenh, const fq_zech_ctx_t 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.
-
void
fq_zech_poly_compose_mod
(fq_zech_poly_t res, const fq_zech_poly_t f, const fq_zech_poly_t g, const fq_zech_poly_t h, const fq_zech_ctx_t ctx)¶ Sets
res
to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero.
-
void
_fq_zech_poly_compose_mod_preinv
(fq_zech_struct * res, const fq_zech_struct * f, slong lenf, const fq_zech_struct * g, const fq_zech_struct * h, slong lenh, const fq_zech_struct * hinv, slong lenhiv, const fq_zech_ctx_t 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 requirehinv
to be the inverse of the reverse ofh
. The output is not allowed to be aliased with any of the inputs.
-
void
fq_zech_poly_compose_mod_preinv
(fq_zech_poly_t res, const fq_zech_poly_t f, const fq_zech_poly_t g, const fq_zech_poly_t h, const fq_zech_poly_t hinv, const fq_zech_ctx_t 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 requirehinv
to be the inverse of the reverse ofh
.
-
void
_fq_zech_poly_reduce_matrix_mod_poly
(fq_zech_mat_t A, const fq_zech_mat_t B, const fq_zech_poly_t f, const fq_zech_ctx_t 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.
-
void
_fq_zech_poly_precompute_matrix
(fq_zech_mat_t A, const fq_zech_struct* f, const fq_zech_struct* g, slong leng, const fq_zech_struct* ginv, slong lenginv, const fq_zech_ctx_t 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 requireginv
to be the inverse of the reverse ofg
and \(g\) to be nonzero.
-
void
fq_zech_poly_precompute_matrix
(fq_zech_mat_t A, const fq_zech_poly_t f, const fq_zech_poly_t g, const fq_zech_poly_t ginv, const fq_zech_ctx_t 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 requireginv
to be the inverse of the reverse ofg
.
-
void
_fq_zech_poly_compose_mod_brent_kung_precomp_preinv
(fq_zech_struct* res, const fq_zech_struct* f, slong lenf, const fq_zech_mat_t A, const fq_zech_struct* h, slong h, const fq_zech_struct* hinv, slong lenhinv, const fq_zech_ctx_t 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 requirehinv
to be the inverse of the reverse ofh
. The output is not allowed to be aliased with any of the inputs.The algorithm used is the Brent-Kung matrix algorithm.
-
void
fq_zech_poly_compose_mod_brent_kung_precomp_preinv
(fq_zech_poly_t res, const fq_zech_poly_t f, const fq_zech_mat_t A, const fq_zech_poly_t h, const fq_zech_poly_t hinv, const fq_zech_ctx_t 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 requirehinv
to be the inverse of the reverse ofh
. 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¶
-
int
_fq_zech_poly_fprint_pretty
(FILE *file, const fq_zech_struct *poly, slong len, const char *x, const fq_zech_ctx_t ctx)¶ Prints the pretty representation of
(poly, len)
to the streamfile
, using the stringx
to represent the indeterminate.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
fq_zech_poly_fprint_pretty
(FILE * file, const fq_zech_poly_t poly, const char *x, const fq_zech_ctx_t ctx)¶ Prints the pretty representation of
poly
to the streamfile
, using the stringx
to represent the indeterminate.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
_fq_zech_poly_print_pretty
(const fq_zech_struct *poly, slong len, const char *x, const fq_zech_ctx_t ctx)¶ Prints the pretty representation of
(poly, len)
tostdout
, using the stringx
to represent the indeterminate.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
fq_zech_poly_print_pretty
(const fq_zech_poly_t poly, const char *x, const fq_zech_ctx_t ctx)¶ Prints the pretty representation of
poly
tostdout
, using the stringx
to represent the indeterminate.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
_fq_zech_poly_fprint
(FILE *file, const fq_zech_struct *poly, slong len, const fq_zech_ctx_t ctx)¶ Prints the pretty representation of
(poly, len)
to the streamfile
.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
fq_zech_poly_fprint
(FILE * file, const fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Prints the pretty representation of
poly
to the streamfile
.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
_fq_zech_poly_print
(const fq_zech_struct *poly, slong len, const fq_zech_ctx_t ctx)¶ Prints the pretty representation of
(poly, len)
tostdout
.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
fq_zech_poly_print
(const fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Prints the representation of
poly
tostdout
.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
char *
_fq_zech_poly_get_str
(const fq_zech_struct * poly, slong len, const fq_zech_ctx_t ctx)¶ Returns the plain FLINT string representation of the polynomial
(poly, len)
.
-
char *
fq_zech_poly_get_str
(const fq_zech_poly_t poly, const fq_zech_ctx_t ctx)¶ Returns the plain FLINT string representation of the polynomial
poly
.
-
char *
_fq_zech_poly_get_str_pretty
(const fq_zech_struct * poly, slong len, const char * x, const fq_zech_ctx_t ctx)¶ Returns a pretty representation of the polynomial
(poly, len)
using the null-terminated string~``x`` as the variable name.
-
char *
fq_zech_poly_get_str_pretty
(const fq_zech_poly_t poly, const char * x, const fq_zech_ctx_t ctx)¶ Returns a pretty representation of the polynomial~``poly`` using the null-terminated string
x
as the variable name
Inflation and deflation¶
-
void
fq_zech_poly_inflate
(fq_zech_poly_t result, const fq_zech_poly_t input, ulong inflation, const fq_zech_ctx_t ctx)¶ Sets
result
to the inflated polynomial \(p(x^n)\) where \(p\) is given byinput
and \(n\) is given byinflation
.
-
void
fq_zech_poly_deflate
(fq_zech_poly_t result, const fq_zech_poly_t input, ulong deflation, const fq_zech_ctx_t ctx)¶ Sets
result
to the deflated polynomial \(p(x^{1/n})\) where \(p\) is given byinput
and \(n\) is given bydeflation
. Requires \(n > 0\).
-
ulong
fq_zech_poly_deflation
(const fq_zech_poly_t input, const fq_zech_ctx_t ctx)¶ Returns the largest integer by which
input
can be deflated. As special cases, returns 0 ifinput
is the zero polynomial and 1 ofinput
is a constant polynomial.