nmod_poly.h – univariate polynomials over integers mod n (word-size n)¶
Description.
Helper functions¶
-
int
signed_mpn_sub_n
(mp_ptr res, mp_srcptr op1, mp_srcptr op2, slong n)¶ If
op1 >= op2
return 0 and setres
toop1 - op2
else return 1 and setres
toop2 - op1
.
Memory management¶
-
void
nmod_poly_init
(nmod_poly_t poly, mp_limb_t n)¶ Initialises
poly
. It will have coefficients modulo~`n`.
-
void
nmod_poly_init_preinv
(nmod_poly_t poly, mp_limb_t n, mp_limb_t ninv)¶ Initialises
poly
. It will have coefficients modulo~`n`. The caller supplies a precomputed inverse limb generated byn_preinvert_limb()
.
-
void
nmod_poly_init2
(nmod_poly_t poly, mp_limb_t n, slong alloc)¶ Initialises
poly
. It will have coefficients modulo~`n`. Up toalloc
coefficients may be stored inpoly
.
-
void
nmod_poly_init2_preinv
(nmod_poly_t poly, mp_limb_t n, mp_limb_t ninv, slong alloc)¶ Initialises
poly
. It will have coefficients modulo~`n`. The caller supplies a precomputed inverse limb generated byn_preinvert_limb()
. Up toalloc
coefficients may be stored inpoly
.
-
void
nmod_poly_realloc
(nmod_poly_t poly, slong alloc)¶ Reallocates
poly
to the given length. If the current length is less thanalloc
, the polynomial is truncated and normalised. Ifalloc
is zero, the polynomial is cleared.
-
void
nmod_poly_clear
(nmod_poly_t poly)¶ Clears the polynomial and releases any memory it used. The polynomial cannot be used again until it is initialised.
-
void
nmod_poly_fit_length
(nmod_poly_t poly, slong alloc)¶ Ensures
poly
has space for at leastalloc
coefficients. This function only ever grows the allocated space, so no data loss can occur.
-
void
_nmod_poly_normalise
(nmod_poly_t poly)¶ Internal function for normalising a polynomial so that the top coefficient, if there is one at all, is not zero.
Polynomial properties¶
-
slong
nmod_poly_length
(const nmod_poly_t poly)¶ Returns the length of the polynomial
poly
. The zero polynomial has length zero.
-
slong
nmod_poly_degree
(const nmod_poly_t poly)¶ Returns the degree of the polynomial
poly
. The zero polynomial is deemed to have degree~`-1`.
-
mp_limb_t
nmod_poly_modulus
(const nmod_poly_t poly)¶ Returns the modulus of the polynomial
poly
. This will be a positive integer.
-
mp_bitcnt_t
nmod_poly_max_bits
(const nmod_poly_t poly)¶ Returns the maximum number of bits of any coefficient of
poly
.
Assignment and basic manipulation¶
-
void
nmod_poly_set
(nmod_poly_t a, const nmod_poly_t b)¶ Sets
a
to a copy ofb
.
-
void
nmod_poly_swap
(nmod_poly_t poly1, nmod_poly_t poly2)¶ Efficiently swaps
poly1
andpoly2
by swapping pointers internally.
-
void
nmod_poly_zero
(nmod_poly_t res)¶ Sets
res
to the zero polynomial.
-
void
nmod_poly_truncate
(nmod_poly_t poly, slong len)¶ Truncates
poly
to the given length and normalises it. Iflen
is greater than the current length ofpoly
, then nothing happens.
-
void
nmod_poly_set_trunc
(nmod_poly_t res, const nmod_poly_t poly, slong n)¶ Notionally truncate
poly
to length \(n\) and setres
to the result. The result is normalised.
-
void
_nmod_poly_reverse
(mp_ptr output, mp_srcptr input, slong len, slong m)¶ 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. Supports aliasing ofoutput
andinput
, but the behaviour is undefined in case of partial overlap.
-
void
nmod_poly_reverse
(nmod_poly_t output, const nmod_poly_t input, slong m)¶ 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.
Randomization¶
-
void
nmod_poly_randtest
(nmod_poly_t poly, flint_rand_t state, slong len)¶ Generates a random polynomial with length up to
len
.
-
void
nmod_poly_randtest_irreducible
(nmod_poly_t poly, flint_rand_t state, slong len)¶ Generates a random irreducible polynomial with length up to
len
.
-
void
nmod_poly_randtest_monic
(nmod_poly_t poly, flint_rand_t state, slong len)¶ Generates a random monic polynomial with length
len
.
-
void
nmod_poly_randtest_monic_irreducible
(nmod_poly_t poly, flint_rand_t state, slong len)¶ Generates a random monic irreducible polynomial with length
len
.
-
void
nmod_poly_randtest_monic_primitive
(nmod_poly_t poly, flint_rand_t state, slong len)¶ Generates a random monic irreducible primitive polynomial with length
len
.
-
void
nmod_poly_randtest_trinomial
(nmod_poly_t poly, flint_rand_t state, slong len)¶ Generates a random monic trinomial of length
len
.
-
int
nmod_poly_randtest_trinomial_irreducible
(nmod_poly_t poly, flint_rand_t state, slong len, slong max_attempts)¶ Attempts to set
poly
to a monic irreducible trinomial of lengthlen
. It will generate up tomax_attempts
trinomials in attempt to find an irreducible one. Ifmax_attempts
is0
, then it will keep generating trinomials until an irreducible one is found. Returns \(1\) if one is found and \(0\) otherwise.
-
void
nmod_poly_randtest_pentomial
(nmod_poly_t poly, flint_rand_t state, slong len)¶ Generates a random monic pentomial of length
len
.
-
int
nmod_poly_randtest_pentomial_irreducible
(nmod_poly_t poly, flint_rand_t state, slong len, slong max_attempts)¶ Attempts to set
poly
to a monic irreducible pentomial of lengthlen
. It will generate up tomax_attempts
pentomials in attempt to find an irreducible one. Ifmax_attempts
is0
, then it will keep generating pentomials until an irreducible one is found. Returns \(1\) if one is found and \(0\) otherwise.
-
void
nmod_poly_randtest_sparse_irreducible
(nmod_poly_t poly, flint_rand_t state, slong len)¶ Attempts to set
poly
to a sparse, monic irreducible polynomial with lengthlen
. It attempts to find an irreducible trinomial. If that does not succeed, it attempts to find a irreducible pentomial. If that fails, thenpoly
is just set to a random monic irreducible polynomial.
Getting and setting coefficients¶
-
ulong
nmod_poly_get_coeff_ui
(const nmod_poly_t poly, slong j)¶ Returns the coefficient of
poly
at index~``j``, where coefficients are numbered with zero being the constant coefficient, and returns it as anulong
. Ifj
refers to a coefficient beyond the end ofpoly
, zero is returned.
-
void
nmod_poly_set_coeff_ui
(nmod_poly_t poly, slong j, ulong c)¶ Sets the coefficient of
poly
at indexj
, where coefficients are numbered with zero being the constant coefficient, to the valuec
reduced modulo the modulus ofpoly
. Ifj
refers to a coefficient beyond the current end ofpoly
, the polynomial is first resized, with intervening coefficients being set to zero.
Input and output¶
-
char *
nmod_poly_get_str
(const nmod_poly_t poly)¶ Writes
poly
to a string representation. The format is as described fornmod_poly_print()
. The string must be freed by the user when finished. For this it is sufficient to callflint_free()
.
-
char *
nmod_poly_get_str_pretty
(const nmod_poly_t poly, const char * x)¶ Writes
poly
to a pretty string representation. The format is as described fornmod_poly_print_pretty()
. The string must be freed by the user when finished. For this it is sufficient to callflint_free()
.It is assumed that the top coefficient is non-zero.
-
int
nmod_poly_set_str
(nmod_poly_t poly, const char * s)¶ Reads
poly
from a strings
. The format is as described fornmod_poly_print()
. If a polynomial in the correct format is read, a positive value is returned, otherwise a non-positive value is returned.
-
int
nmod_poly_print
(const nmod_poly_t a)¶ Prints the polynomial to
stdout
. The length is printed, followed by a space, then the modulus. If the length is zero this is all that is printed, otherwise two spaces followed by a space separated list of coefficients is printed, beginning with the constant coefficient.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
nmod_poly_print_pretty
(const nmod_poly_t a, const char * x)¶ Prints the polynomial to
stdout
using the stringx
to represent the indeterminate.It is assumed that the top coefficient is non-zero.
In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
nmod_poly_fread
(FILE * f, nmod_poly_t poly)¶ Reads
poly
from the file streamf
. If this is a file that has just been written, the file should be closed then opened again. The format is as described fornmod_poly_print()
. If a polynomial in the correct format is read, a positive value is returned, otherwise a non-positive value is returned.
-
int
nmod_poly_fprint
(FILE * f, const nmod_poly_t poly)¶ Writes a polynomial to the file stream
f
. If this is a file then the file should be closed and reopened before being read. The format is as described fornmod_poly_print()
. If the polynomial is written correctly, a positive value is returned, otherwise a non-positive value is returned.In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
nmod_poly_fprint_pretty
(FILE * f, const nmod_poly_t poly, const char * x)¶ Writes a polynomial to the file stream
f
. If this is a file then the file should be closed and reopened before being read. The format is as described fornmod_poly_print_pretty()
. If the polynomial is written correctly, a positive value is returned, otherwise a non-positive value is returned.It is assumed that the top coefficient is non-zero.
In case of success, returns a positive value. In case of failure, returns a non-positive value.
-
int
nmod_poly_read
(nmod_poly_t poly)¶ Read
poly
fromstdin
. The format is as described fornmod_poly_print()
. If a polynomial in the correct format is read, a positive value is returned, otherwise a non-positive value is returned.
Comparison¶
-
int
nmod_poly_equal
(const nmod_poly_t a, const nmod_poly_t b)¶ Returns~`1` if the polynomials are equal, otherwise~`0`.
-
int
nmod_poly_equal_trunc
(const nmod_poly_t poly1, const nmod_poly_t poly2, slong n)¶ Notionally truncate
poly1
andpoly2
to length \(n\) and return \(1\) if the truncations are equal, otherwise return \(0\).
-
int
nmod_poly_is_zero
(const nmod_poly_t poly)¶ Returns~`1` if the polynomial
poly
is the zero polynomial, otherwise returns~`0`.
-
int
nmod_poly_is_one
(const nmod_poly_t poly)¶ Returns~`1` if the polynomial
poly
is the constant polynomial 1, otherwise returns~`0`.
Shifting¶
-
void
_nmod_poly_shift_left
(mp_ptr res, mp_srcptr poly, slong len, slong k)¶ Sets
(res, len + k)
to(poly, len)
shifted left byk
coefficients. Assumes thatres
has space forlen + k
coefficients.
-
void
nmod_poly_shift_left
(nmod_poly_t res, const nmod_poly_t poly, slong k)¶ Sets
res
topoly
shifted left byk
coefficients, i.e.multiplied by \(x^k\).
-
void
_nmod_poly_shift_right
(mp_ptr res, mp_srcptr poly, slong len, slong k)¶ Sets
(res, len - k)
to(poly, len)
shifted left byk
coefficients. It is assumed thatk <= len
and thatres
has space for at leastlen - k
coefficients.
-
void
nmod_poly_shift_right
(nmod_poly_t res, const nmod_poly_t poly, slong k)¶ Sets
res
topoly
shifted right byk
coefficients, i.e.divide by \(x^k\) and throws away the remainder. Ifk
is greater than or equal to the length ofpoly
, the result is the zero polynomial.
Addition and subtraction¶
-
void
_nmod_poly_add
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Sets
res
to the sum of(poly1, len1)
and(poly2, len2)
. There are no restrictions on the lengths.
-
void
nmod_poly_add
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)¶ Sets
res
to the sum ofpoly1
andpoly2
.
-
void
nmod_poly_add_series
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n)¶ Notionally truncate
poly1
andpoly2
to length \(n\) and setres
to the sum.
-
void
_nmod_poly_sub
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Sets
res
to the difference of(poly1, len1)
and(poly2, len2)
. There are no restrictions on the lengths.
-
void
nmod_poly_sub
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)¶ Sets
res
to the difference ofpoly1
andpoly2
.
-
void
nmod_poly_sub_series
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n)¶ Notionally truncate
poly1
andpoly2
to length \(n\) and setres
to the difference.
-
void
nmod_poly_neg
(nmod_poly_t res, const nmod_poly_t poly)¶ Sets
res
to the negation ofpoly
.
Scalar multiplication and division¶
-
void
nmod_poly_scalar_mul_nmod
(nmod_poly_t res, const nmod_poly_t poly, ulong c)¶ Sets
res
to(poly, len)
multiplied by~`c`, where~`c` is reduced modulo the modulus ofpoly
.
-
void
_nmod_poly_make_monic
(mp_ptr output, mp_srcptr input, slong len, nmod_t mod)¶ Sets
output
to be the scalar multiple ofinput
of lengthlen > 0
that has leading coefficient one, if such a polynomial exists. If the leading coefficient ofinput
is not invertible,output
is set to the multiple ofinput
whose leading coefficient is the greatest common divisor of the leading coefficient and the modulus ofinput
.
-
void
nmod_poly_make_monic
(nmod_poly_t output, const nmod_poly_t input)¶ Sets
output
to be the scalar multiple ofinput
with leading coefficient one, if such a polynomial exists. Ifinput
is zero an exception is raised. If the leading coefficient ofinput
is not invertible,output
is set to the multiple ofinput
whose leading coefficient is the greatest common divisor of the leading coefficient and the modulus ofinput
.
Bit packing and unpacking¶
-
void
_nmod_poly_bit_pack
(mp_ptr res, mp_srcptr poly, slong len, mp_bitcnt_t bits)¶ Packs
len
coefficients ofpoly
into fields of the given number of bits in the large integerres
, i.e.evaluatespoly
at2^bits
and store the result inres
. Assumeslen > 0
andbits > 0
. Also assumes that no coefficient ofpoly
is bigger thanbits/2
bits. We also assumebits < 3 * FLINT_BITS
.
-
void
_nmod_poly_bit_unpack
(mp_ptr res, slong len, mp_srcptr mpn, ulong bits, nmod_t mod)¶ Unpacks
len
coefficients stored in the big integermpn
in bit fields of the given number of bits, reduces them modulo the given modulus, then stores them in the polynomialres
. We assumelen > 0
and3 * FLINT_BITS > bits > 0
. There are no restrictions on the size of the actual coefficients as stored within the bitfields.
-
void
nmod_poly_bit_pack
(fmpz_t f, const nmod_poly_t poly, mp_bitcnt_t bit_size)¶ Packs
poly
into bitfields of sizebit_size
, writing the result tof
.
-
void
nmod_poly_bit_unpack
(nmod_poly_t poly, const fmpz_t f, mp_bitcnt_t bit_size)¶ Unpacks the polynomial from fields of size
bit_size
as represented by the integerf
.
-
void
_nmod_poly_KS2_pack1
(mp_ptr res, mp_srcptr op, slong n, slong s, ulong b, ulong k, slong r)¶ Same as
_nmod_poly_KS2_pack
, but requiresb <= FLINT_BITS
.
-
void
_nmod_poly_KS2_pack
(mp_ptr res, mp_srcptr op, slong n, slong s, ulong b, ulong k, slong r)¶ Bit packing routine used by KS2 and KS4 multiplication.
-
void
_nmod_poly_KS2_unpack1
(mp_ptr res, mp_srcptr op, slong n, ulong b, ulong k)¶ Same as
_nmod_poly_KS2_unpack
, but requiresb <= FLINT_BITS
(i.e. writes one word per coefficient).
-
void
_nmod_poly_KS2_unpack2
(mp_ptr res, mp_srcptr op, slong n, ulong b, ulong k)¶ Same as
_nmod_poly_KS2_unpack
, but requiresFLINT_BITS < b <= 2 * FLINT_BITS
(i.e. writes two words per coefficient).
-
void
_nmod_poly_KS2_unpack3
(mp_ptr res, mp_srcptr op, slong n, ulong b, ulong k)¶ Same as
_nmod_poly_KS2_unpack
, but requires2 * FLINT_BITS < b < 3 * FLINT_BITS
(i.e. writes three words per coefficient).
-
void
_nmod_poly_KS2_unpack
(mp_ptr res, mp_srcptr op, slong n, ulong b, ulong k)¶ Bit unpacking code used by KS2 and KS4 multiplication.
KS2/KS4 Reduction¶
-
void
_nmod_poly_KS2_reduce
(mp_ptr res, slong s, mp_srcptr op, slong n, ulong w, nmod_t mod)¶ Reduction code used by KS2 and KS4 multiplication.
-
void
_nmod_poly_KS2_recover_reduce1
(mp_ptr res, slong s, mp_srcptr op1, mp_srcptr op2, slong n, ulong b, nmod_t mod)¶ Same as
_nmod_poly_KS2_recover_reduce
, but requires0 < 2 * b <= FLINT_BITS
.
-
void
_nmod_poly_KS2_recover_reduce2
(mp_ptr res, slong s, mp_srcptr op1, mp_srcptr op2, slong n, ulong b, nmod_t mod)¶ Same as
_nmod_poly_KS2_recover_reduce
, but requiresFLINT_BITS < 2 * b < 2*FLINT_BITS
.
-
void
_nmod_poly_KS2_recover_reduce2b
(mp_ptr res, slong s, mp_srcptr op1, mp_srcptr op2, slong n, ulong b, nmod_t mod)¶ Same as
_nmod_poly_KS2_recover_reduce
, but requiresb == FLINT_BITS
.
-
void
_nmod_poly_KS2_recover_reduce3
(mp_ptr res, slong s, mp_srcptr op1, mp_srcptr op2, slong n, ulong b, nmod_t mod)¶ Same as
_nmod_poly_KS2_recover_reduce
, but requires2 * FLINT_BITS < 2 * b <= 3 * FLINT_BITS
.
-
void
_nmod_poly_KS2_recover_reduce
(mp_ptr res, slong s, mp_srcptr op1, mp_srcptr op2, slong n, ulong b, nmod_t mod)¶ Reduction code used by KS4 multiplication.
Multiplication¶
-
void
_nmod_poly_mul_classical
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Sets
(res, len1 + len2 - 1)
to the product of(poly1, len1)
and(poly2, len2)
. Assumeslen1 >= len2 > 0
. Aliasing of inputs and output is not permitted.
-
void
nmod_poly_mul_classical
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)¶ Sets
res
to the product ofpoly1
andpoly2
.
-
void
_nmod_poly_mullow_classical
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, slong trunc, nmod_t mod)¶ Sets
res
to the lowertrunc
coefficients of the product of(poly1, len1)
and(poly2, len2)
. Assumes thatlen1 >= len2 > 0
andtrunc > 0
. Aliasing of inputs and output is not permitted.
-
void
nmod_poly_mullow_classical
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong trunc)¶ Sets
res
to the lowertrunc
coefficients of the product ofpoly1
andpoly2
.
-
void
_nmod_poly_mulhigh_classical
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, slong start, nmod_t mod)¶ 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
nmod_poly_mulhigh_classical
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong start)¶ 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
_nmod_poly_mul_KS
(mp_ptr out, mp_srcptr in1, slong len1, mp_srcptr in2, slong len2, mp_bitcnt_t bits, nmod_t mod)¶ Sets
res
to the product ofin1
andin2
assuming the output coefficients are at most the given number of bits wide. Ifbits
is set to \(0\) an appropriate value is computed automatically. Assumes thatlen1 >= len2 > 0
.
-
void
nmod_poly_mul_KS
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, mp_bitcnt_t bits)¶ Sets
res
to the product ofpoly1
andpoly2
assuming the output coefficients are at most the given number of bits wide. Ifbits
is set to \(0\) an appropriate value is computed automatically.
-
void
_nmod_poly_mul_KS2
(mp_ptr res, mp_srcptr op1, slong n1, mp_srcptr op2, slong n2, nmod_t mod)¶ Sets
res
to the product ofop1
andop2
. Assumes thatlen1 >= len2 > 0
.
-
void
nmod_poly_mul_KS2
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)¶ Sets
res
to the product ofpoly1
andpoly2
.
-
void
_nmod_poly_mul_KS4
(mp_ptr res, mp_srcptr op1, slong n1, mp_srcptr op2, slong n2, nmod_t mod)¶ Sets
res
to the product ofop1
andop2
. Assumes thatlen1 >= len2 > 0
.
-
void
nmod_poly_mul_KS4
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)¶ Sets
res
to the product ofpoly1
andpoly2
.
-
void
_nmod_poly_mullow_KS
(mp_ptr out, mp_srcptr in1, slong len1, mp_srcptr in2, slong len2, mp_bitcnt_t bits, slong n, nmod_t mod)¶ Sets
out
to the low \(n\) coefficients ofin1
of lengthlen1
timesin2
of lengthlen2
. The output must have space forn
coefficients. We assume thatlen1 >= len2 > 0
and that0 < n <= len1 + len2 - 1
.
-
void
nmod_poly_mullow_KS
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, mp_bitcnt_t bits, slong n)¶ Set
res
to the low \(n\) coefficients ofin1
of lengthlen1
timesin2
of lengthlen2
.
-
void
_nmod_poly_mul
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Sets
res
to the product ofpoly1
of lengthlen1
andpoly2
of lengthlen2
. Assumeslen1 >= len2 > 0
. No aliasing is permitted between the inputs and the output.
-
void
nmod_poly_mul
(nmod_poly_t res, const nmod_poly_t poly, const nmod_poly_t poly2)¶ Sets
res
to the product ofpoly1
andpoly2
.
-
void
_nmod_poly_mullow
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, slong n, nmod_t mod)¶ Sets
res
to the firstn
coefficients of the product ofpoly1
of lengthlen1
andpoly2
of lengthlen2
. It is assumed that0 < n <= len1 + len2 - 1
and thatlen1 >= len2 > 0
. No aliasing of inputs and output is permitted.
-
void
nmod_poly_mullow
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong trunc)¶ Sets
res
to the firsttrunc
coefficients of the product ofpoly1
andpoly2
.
-
void
_nmod_poly_mulhigh
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, slong n, nmod_t mod)¶ Sets all but the low \(n\) coefficients of
res
to the corresponding coefficients of the product ofpoly1
of lengthlen1
andpoly2
of lengthlen2
, the other coefficients being arbitrary. It is assumed thatlen1 >= len2 > 0
and that0 < n <= len1 + len2 - 1
. Aliasing of inputs and output is not permitted.
-
void
nmod_poly_mulhigh
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n)¶ Sets all but the low \(n\) coefficients of
res
to the corresponding coefficients of the product ofpoly1
andpoly2
, the remaining coefficients being arbitrary.
-
void
_nmod_poly_mulmod
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, mp_srcptr f, slong lenf, nmod_t mod)¶ 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_nmod_poly_mul
instead.Aliasing of
f
andres
is not permitted.
-
void
nmod_poly_mulmod
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, const nmod_poly_t f)¶ Sets
res
to the remainder of the product ofpoly1
andpoly2
upon polynomial division byf
.
-
void
_nmod_poly_mulmod_preinv
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, mp_srcptr f, slong lenf, mp_srcptr finv, slong lenfinv, nmod_t mod)¶ 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. It is required thatlen1 < lenf
andlen2 < lenf
. Otherwise, simply use_nmod_poly_mul
instead.Aliasing of
f
orfinv
andres
is not permitted.
-
void
nmod_poly_mulmod_preinv
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, const nmod_poly_t f, const nmod_poly_t finv)¶ Sets
res
to the remainder of the product ofpoly1
andpoly2
upon polynomial division byf
.finv
is the inverse of the reverse off
. It is required thatpoly1
andpoly2
are reduced modulof
.
Powering¶
-
void
_nmod_poly_pow_binexp
(mp_ptr res, mp_srcptr poly, slong len, ulong e, nmod_t mod)¶ Raises
poly
of lengthlen
to the powere
and setsres
to the result. We require thatres
has enough space for(len - 1)*e + 1
coefficients. Assumes thatlen > 0
,e > 1
. Aliasing is not permitted. Uses the binary exponentiation method.
-
void
nmod_poly_pow_binexp
(nmod_poly_t res, const nmod_poly_t poly, ulong e)¶ Raises
poly
to the powere
and setsres
to the result. Uses the binary exponentiation method.
-
void
_nmod_poly_pow
(mp_ptr res, mp_srcptr poly, slong len, ulong e, nmod_t mod)¶ Raises
poly
of lengthlen
to the powere
and setsres
to the result. We require thatres
has enough space for(len - 1)*e + 1
coefficients. Assumes thatlen > 0
,e > 1
. Aliasing is not permitted.
-
void
nmod_poly_pow
(nmod_poly_t res, const nmod_poly_t poly, ulong e)¶ Raises
poly
to the powere
and setsres
to the result.
-
void
_nmod_poly_pow_trunc_binexp
(mp_ptr res, mp_srcptr poly, ulong e, slong trunc, nmod_t mod)¶ Sets
res
to the lowtrunc
coefficients ofpoly
(assumed to be zero padded if necessary to lengthtrunc
) to the powere
. This is equivalent to doing a powering followed by a truncation. We require thatres
has enough space fortrunc
coefficients, thattrunc > 0
and thate > 1
. Aliasing is not permitted. Uses the binary exponentiation method.
-
void
nmod_poly_pow_trunc_binexp
(nmod_poly_t res, const nmod_poly_t poly, ulong e, slong trunc)¶ Sets
res
to the lowtrunc
coefficients ofpoly
to the powere
. This is equivalent to doing a powering followed by a truncation. Uses the binary exponentiation method.
-
void
_nmod_poly_pow_trunc
(mp_ptr res, mp_srcptr poly, ulong e, slong trunc, nmod_t mod)¶ Sets
res
to the lowtrunc
coefficients ofpoly
(assumed to be zero padded if necessary to lengthtrunc
) to the powere
. This is equivalent to doing a powering followed by a truncation. We require thatres
has enough space fortrunc
coefficients, thattrunc > 0
and thate > 1
. Aliasing is not permitted.
-
void
nmod_poly_pow_trunc
(nmod_poly_t res, const nmod_poly_t poly, ulong e, slong trunc)¶ Sets
res
to the lowtrunc
coefficients ofpoly
to the powere
. This is equivalent to doing a powering followed by a truncation.
-
void
_nmod_poly_powmod_ui_binexp
(mp_ptr res, mp_srcptr poly, ulong e, mp_srcptr f, slong lenf, nmod_t mod)¶ 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
nmod_poly_powmod_ui_binexp
(nmod_poly_t res, const nmod_poly_t poly, ulong e, const nmod_poly_t f)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree >= 0
.
-
void
_nmod_poly_powmod_ui_binexp_preinv
(mp_ptr res, mp_srcptr poly, ulong e, mp_srcptr f, slong lenf, mp_srcptr finv, slong lenfinv, nmod_t mod)¶ 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
nmod_poly_powmod_ui_binexp_preinv
(nmod_poly_t res, const nmod_poly_t poly, ulong e, const nmod_poly_t f, const nmod_poly_t finv)¶ 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
_nmod_poly_powmod_x_ui_preinv
(mp_ptr res, ulong e, mp_srcptr f, slong lenf, mp_srcptr finv, slong lenfinv, nmod_t mod)¶ 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
nmod_poly_powmod_x_ui_preinv
(nmod_poly_t res, ulong e, const nmod_poly_t f, const nmod_poly_t finv)¶ 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
.
-
void
_nmod_poly_powmod_mpz_binexp
(mp_ptr res, mp_srcptr poly, mpz_srcptr e, mp_srcptr f, slong lenf, nmod_t mod)¶ 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
nmod_poly_powmod_mpz_binexp
(nmod_poly_t res, const nmod_poly_t poly, mpz_srcptr e, const nmod_poly_t f)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree >= 0
.
-
void
_nmod_poly_powmod_mpz_binexp_preinv
(mp_ptr res, mp_srcptr poly, mpz_srcptr e, mp_srcptr f, slong lenf, mp_srcptr finv, slong lenfinv, nmod_t mod)¶ 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
nmod_poly_powmod_mpz_binexp_preinv
(nmod_poly_t res, const nmod_poly_t poly, mpz_srcptr e, const nmod_poly_t f, const nmod_poly_t finv)¶ Sets
res
topoly
raised to the powere
modulof
, using binary exponentiation. We requiree >= 0
. We requirefinv
to be the inverse of the reverse off
.
Division¶
-
void
_nmod_poly_divrem_basecase
(mp_ptr Q, mp_ptr R, mp_ptr W, mp_srcptr A, slong A_len, mp_srcptr B, slong B_len, nmod_t mod)¶ Finds \(Q\) and \(R\) such that \(A = B Q + R\) with \(\len(R) < \len(B)\). If \(\len(B) = 0\) an exception is raised. We require that
W
is temporary space ofNMOD_DIVREM_BC_ITCH(A_len, B_len, mod)
coefficients.
-
void
nmod_poly_divrem_basecase
(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B)¶ Finds \(Q\) and \(R\) such that \(A = B Q + R\) with \(\len(R) < \len(B)\). If \(\len(B) = 0\) an exception is raised.
-
void _nmod_poly_div_basecase(mp_ptr Q, mp_ptr W, mp_srcptr A, slong A_len, mp_srcptr B, slong B_len, nmod_t mod);
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. We require thatW
is temporary space ofNMOD_DIV_BC_ITCH(A_len, B_len, mod)
coefficients.
-
void nmod_poly_div_basecase(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B);
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
_nmod_poly_divrem_divconquer_recursive
(mp_ptr Q, mp_ptr BQ, mp_ptr W, mp_ptr V, mp_srcptr A, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R)\) less than
lenB
, whereA
is of length2 * lenB - 1
andB
is of lengthlenB
. SetsBQ
to the lowlenB - 1
coefficients ofB * Q
. We require thatQ
have space forlenB
coefficients, thatW
be temporary space of sizelenB - 1
andV
be temporary space for a number of coefficients computed byNMOD_DIVREM_DC_ITCH(lenB, mod)
.
-
void
_nmod_poly_divrem_divconquer
(mp_ptr Q, mp_ptr R, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R)\) less than
lenB
, whereA
is of lengthlenA
andB
is of lengthlenB
. We require thatQ
have space forlenA - lenB + 1
coefficients.
-
void
nmod_poly_divrem_divconquer
(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \len(B)\).
-
void
_nmod_poly_divrem_q0
(mp_ptr Q, mp_ptr R, mp_srcptr A, mp_srcptr B, slong lenA, nmod_t mod)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \len(B)\), where \(\len(A) = \len(B) > 0\).
Requires that \(Q\) and \(R\) have space for \(1\) and \(\len(B) - 1\) coefficients, respectively.
Does not support aliasing or zero-padding.
-
void
_nmod_poly_divrem_q1
(mp_ptr Q, mp_ptr R, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \len(B)\), where \(\len(A) = \len(B) + 1 \geq \len(B) > 0\).
Requires that \(Q\) and \(R\) have space for \(\len(A) - \len(B) + 1\) and \(\len(B) - 1\) coefficients, respectively.
Does not support aliasing or zero-padding.
-
void
_nmod_poly_divrem
(mp_ptr Q, mp_ptr R, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R)\) less than
lenB
, whereA
is of lengthlenA
andB
is of lengthlenB
. We require thatQ
have space forlenA - lenB + 1
coefficients.
-
void
nmod_poly_divrem
(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \len(B)\).
-
void
_nmod_poly_div_divconquer_recursive
(mp_ptr Q, mp_ptr W, mp_ptr V, mp_srcptr A, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R)\) less than
lenB
, whereA
is of length2 * lenB - 1
andB
is of lengthlenB
. We require thatQ
have space forlenB
coefficients and thatW
be temporary space of sizelenB - 1
andV
be temporary space for a number of coefficients computed byNMOD_DIV_DC_ITCH(lenB, mod)
.
-
void
_nmod_poly_div_divconquer
(mp_ptr Q, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ 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 returns onlyQ
. We require thatQ
have space forlenA - lenB + 1
coefficients.
-
void
nmod_poly_div_divconquer
(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B)¶ Notionally computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \len(B)\), but returns only \(Q\).
-
void
_nmod_poly_div
(mp_ptr Q, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ 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 returns onlyQ
. We require thatQ
have space forlenA - lenB + 1
coefficients.
-
void
nmod_poly_div
(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B)¶ Computes the quotient \(Q\) on polynomial division of \(A\) and \(B\).
-
void
_nmod_poly_rem_basecase
(mp_ptr R, mp_ptr W, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶
-
void
nmod_poly_rem_basecase
(nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B)¶
-
void
_nmod_poly_rem_q1
(mp_ptr R, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Notationally, computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \len(B)\), where \(\len(A) = \len(B) + 1 \geq \len(B) > 0\), but returns only the remainder.
Requires that \(R\) has space for \(\len(B) - 1\) coefficients, respectively.
Does not support aliasing or zero-padding.
-
void
_nmod_poly_rem
(mp_ptr R, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes the remainder \(R\) on polynomial division of \(A\) by \(B\).
-
void
nmod_poly_rem
(nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B)¶ Computes the remainder \(R\) on polynomial division of \(A\) by \(B\).
-
void
_nmod_poly_inv_series_basecase
(mp_ptr Qinv, mp_srcptr Q, slong Qlen, slong n, nmod_t mod)¶ Given
Q
of lengthQlen
whose leading coefficient is invertible modulo the given modulus, finds a polynomialQinv
of lengthn
such that the topn
coefficients of the productQ * Qinv
is \(x^{n - 1}\). Requires thatn > 0
. This function can be viewed as inverting a power series.
-
void
nmod_poly_inv_series_basecase
(nmod_poly_t Qinv, const nmod_poly_t Q, slong n)¶ Given
Q
of length at leastn
findQinv
of lengthn
such that the topn
coefficients of the productQ * Qinv
is \(x^{n - 1}\). An exception is raised ifn = 0
or if the length ofQ
is less thann
. The leading coefficient ofQ
must be invertible modulo the modulus ofQ
. This function can be viewed as inverting a power series.
-
void
_nmod_poly_inv_series_newton
(mp_ptr Qinv, mp_srcptr Q, slong Qlen, slong n, nmod_t mod)¶ Given
Q
of lengthQlen
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
nmod_poly_inv_series_newton
(nmod_poly_t Qinv, const nmod_poly_t Q, slong n)¶ 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
_nmod_poly_inv_series
(mp_ptr Qinv, mp_srcptr Q, slong Qlen, slong n, nmod_t mod)¶ Given
Q
of lengthQlenn
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.
-
void
nmod_poly_inv_series
(nmod_poly_t Qinv, const nmod_poly_t Q, slong n)¶ 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.
-
void
_nmod_poly_div_series_basecase
(mp_ptr Q, mp_srcptr A, slong Alen, mp_srcptr B, slong Blen, slong n, nmod_t mod)¶ Given polynomials
A
andB
of lengthAlen
andBlen
, finds the polynomialQ
of lengthn
such thatQ * B = A
modulo \(x^n\). We assumen > 0
and that the constant coefficient ofB
is invertible modulo the given modulus. The polynomialQ
must have space forn
coefficients.
-
void
nmod_poly_div_series_basecase
(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B, slong n)¶ Given polynomials
A
andB
considered modulon
, finds the polynomialQ
of length at mostn
such thatQ * B = A
modulo \(x^n\). We assumen > 0
and that the constant coefficient ofB
is invertible modulo the modulus. An exception is raised ifn == 0
or the constant coefficient ofB
is zero.
-
void
_nmod_poly_div_series
(mp_ptr Q, mp_srcptr A, slong Alen, mp_srcptr B, slong Blen, slong n, nmod_t mod)¶ Given polynomials
A
andB
of lengthAlen
andBlen
, finds the polynomialQ
of lengthn
such thatQ * B = A
modulo \(x^n\). We assumen > 0
and that the constant coefficient ofB
is invertible modulo the given modulus. The polynomialQ
must have space forn
coefficients.
-
void
nmod_poly_div_series
(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B, slong n)¶ Given polynomials
A
andB
considered modulon
, finds the polynomialQ
of length at mostn
such thatQ * B = A
modulo \(x^n\). We assumen > 0
and that the constant coefficient ofB
is invertible modulo the modulus. An exception is raised ifn == 0
or the constant coefficient ofB
is zero.
-
void
_nmod_poly_div_newton
(mp_ptr Q, mp_srcptr A, slong Alen, mp_srcptr B, slong Blen, nmod_t mod)¶ 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.The algorithm used is to reverse the polynomials and divide the resulting power series, then reverse the result.
-
void
nmod_poly_div_newton
(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B)¶ 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.
The algorithm used is to reverse the polynomials and divide the resulting power series, then reverse the result.
-
void
_nmod_poly_div_newton_n_preinv
(mp_ptr Q, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, mp_srcptr Binv, slong lenBinv, nmod_t mod)¶ 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
nmod_poly_div_newton_n_preinv
(nmod_poly_t Q, const nmod_poly_t A, const nmod_poly_t B, const nmod_poly_t Binv)¶ 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
_nmod_poly_divrem_newton
(mp_ptr Q, mp_ptr R, mp_srcptr A, slong Alen, mp_srcptr B, slong Blen, nmod_t mod)¶ 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. The algorithm used is to calldiv_newton()
and then multiply out and compute the remainder.
-
void
nmod_poly_divrem_newton
(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B)¶ Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\len(R) < \len(B)\). The algorithm used is to call
div_newton()
and then multiply out and compute the remainder.
-
void
_nmod_poly_divrem_newton_n_preinv
(mp_ptr Q, mp_ptr R, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, mp_srcptr Binv, slong lenBinv, nmod_t mod)¶ 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_n_preinv()
and then multiply out and compute the remainder.
-
void
nmod_poly_divrem_newton_n_preinv
(nmod_poly_t Q, nmod_poly_t R, const nmod_poly_t A, const nmod_poly_t B, const nmod_poly_t Binv)¶ 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_n()
and then multiply out and compute the remainder.
-
mp_limb_t
_nmod_poly_div_root
(mp_ptr Q, mp_srcptr A, slong len, mp_limb_t c, nmod_t mod)¶ Sets
(Q, len-1)
to the quotient of(A, len)
on division by \((x - c)\), and returns the remainder, equal to the value of \(A\) evaluated at \(c\). \(A\) and \(Q\) are allowed to be the same, but may not overlap partially in any other way.
-
mp_limb_t
nmod_poly_div_root
(nmod_poly_t Q, const nmod_poly_t A, mp_limb_t c)¶ Sets \(Q\) to the quotient of \(A\) on division by \((x - c)\), and returns the remainder, equal to the value of \(A\) evaluated at \(c\).
Derivative and integral¶
-
void
_nmod_poly_derivative
(mp_ptr x_prime, mp_srcptr x, slong len, nmod_t mod)¶ Sets the first
len - 1
coefficients ofx_prime
to the derivative ofx
which is assumed to be of lengthlen
. It is assumed thatlen > 0
.
-
void
nmod_poly_derivative
(nmod_poly_t x_prime, const nmod_poly_t x)¶ Sets
x_prime
to the derivative ofx
.
-
void
_nmod_poly_integral
(mp_ptr x_int, mp_srcptr x, slong len, nmod_t mod)¶ Set the first
len
coefficients ofx_int
to the integral ofx
which is assumed to be of lengthlen - 1
. The constant term ofx_int
is set to zero. It is assumed thatlen > 0
. The result is only well-defined if the modulus is a prime number strictly larger than the degree ofx
. Supports aliasing between the two polynomials.
-
void
nmod_poly_integral
(nmod_poly_t x_int, const nmod_poly_t x)¶ Set
x_int
to the indefinite integral ofx
with constant term zero. The result is only well-defined if the modulus is a prime number strictly larger than the degree ofx
.
Evaluation¶
-
mp_limb_t
_nmod_poly_evaluate_nmod
(mp_srcptr poly, slong len, mp_limb_t c, nmod_t mod)¶ Evaluates
poly
at the value~``c`` and reduces modulo the given modulus ofpoly
. The value~``c`` should be reduced modulo the modulus. The algorithm used is Horner’s method.
-
mp_limb_t
nmod_poly_evaluate_nmod
(nmod_poly_t poly, mp_limb_t c)¶ Evaluates
poly
at the value~``c`` and reduces modulo the modulus ofpoly
. The value~``c`` should be reduced modulo the modulus. The algorithm used is Horner’s method.
-
void
nmod_poly_evaluate_mat_horner
(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c)¶ Evaluates
poly
with matrix as an argument at the valuec
and stores the result indest
. The dimension and modulus ofdest
is assumed to be same as that ofc
.dest
andc
may be aliased. Horner’s Method is used to compute the result.
-
void
nmod_poly_evaluate_mat_paterson_stockmeyer
(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c)¶ Evaluates
poly
with matrix as an argument at the valuec
and stores the result indest
. The dimension and modulus ofdest
is assumed to be same as that ofc
.dest
andc
may be aliased. Paterson-Stockmeyer algorithm is used to compute the result. The algorithm is described in cite{Paterson1973}.
-
void
nmod_poly_evaluate_mat
(nmod_mat_t dest, const nmod_poly_t poly, const nmod_mat_t c)¶ Evaluates
poly
with matrix as an argument at the valuec
and stores the result indest
. The dimension and modulus ofdest
is assumed to be same as that ofc
.dest
andc
may be aliased. This function automatically switches between Horner’s method and the Paterson-Stockmeyer algorithm.
Multipoint evaluation¶
-
void
_nmod_poly_evaluate_nmod_vec_iter
(mp_ptr ys, mp_srcptr poly, slong len, mp_srcptr xs, slong n, nmod_t mod)¶ Evaluates (
coeffs
,len
) at then
values given in the vectorxs
, writing the output values toys
. The values inxs
should be reduced modulo the modulus.Uses Horner’s method iteratively.
-
void
nmod_poly_evaluate_nmod_vec_iter
(mp_ptr ys, const nmod_poly_t poly, mp_srcptr xs, slong n)¶ Evaluates
poly
at then
values given in the vectorxs
, writing the output values toys
. The values inxs
should be reduced modulo the modulus.Uses Horner’s method iteratively.
-
void
_nmod_poly_evaluate_nmod_vec_fast_precomp
(mp_ptr vs, mp_srcptr poly, slong plen, const mp_ptr * tree, slong len, nmod_t mod)¶ Evaluates (
poly
,plen
) at thelen
values given by the precomputed subproduct treetree
.
-
void
_nmod_poly_evaluate_nmod_vec_fast
(mp_ptr ys, mp_srcptr poly, slong len, mp_srcptr xs, slong n, nmod_t mod)¶ Evaluates (
coeffs
,len
) at then
values given in the vectorxs
, writing the output values toys
. The values inxs
should be reduced modulo the modulus.Uses fast multipoint evaluation, building a temporary subproduct tree.
-
void
nmod_poly_evaluate_nmod_vec_fast
(mp_ptr ys, const nmod_poly_t poly, mp_srcptr xs, slong n)¶ Evaluates
poly
at then
values given in the vectorxs
, writing the output values toys
. The values inxs
should be reduced modulo the modulus.Uses fast multipoint evaluation, building a temporary subproduct tree.
-
void
_nmod_poly_evaluate_nmod_vec
(mp_ptr ys, mp_srcptr poly, slong len, mp_srcptr xs, slong n, nmod_t mod)¶ Evaluates (
poly
,len
) at then
values given in the vectorxs
, writing the output values toys
. The values inxs
should be reduced modulo the modulus.
-
void
nmod_poly_evaluate_nmod_vec
(mp_ptr ys, const nmod_poly_t poly, mp_srcptr xs, slong n)¶ Evaluates
poly
at then
values given in the vectorxs
, writing the output values toys
. The values inxs
should be reduced modulo the modulus.
Interpolation¶
-
void
_nmod_poly_interpolate_nmod_vec
(mp_ptr poly, mp_srcptr xs, mp_srcptr ys, slong n, nmod_t mod)¶ Sets
poly
to the unique polynomial of length at mostn
that interpolates then
given evaluation pointsxs
and valuesys
. If the interpolating polynomial is shorter than lengthn
, the leading coefficients are set to zero.The values in
xs
andys
should be reduced modulo the modulus, and allxs
must be distinct. Aliasing betweenpoly
andxs
orys
is not allowed.
-
void
nmod_poly_interpolate_nmod_vec
(nmod_poly_t poly, mp_srcptr xs, mp_srcptr ys, slong n)¶ Sets
poly
to the unique polynomial of lengthn
that interpolates then
given evaluation pointsxs
and valuesys
. The values inxs
andys
should be reduced modulo the modulus, and allxs
must be distinct.
-
void
_nmod_poly_interpolation_weights
(mp_ptr w, const mp_ptr * tree, slong len, nmod_t mod)¶ Sets
w
to the barycentric interpolation weights for fast Lagrange interpolation with respect to a given subproduct tree.
-
void
_nmod_poly_interpolate_nmod_vec_fast_precomp
(mp_ptr poly, mp_srcptr ys, const mp_ptr * tree, mp_srcptr weights, slong len, nmod_t mod)¶ Performs interpolation using the fast Lagrange interpolation algorithm, generating a temporary subproduct tree.
The function values are given as
ys
. The function takes a precomputed subproduct treetree
and barycentric interpolation weightsweights
corresponding to the roots.
-
void
_nmod_poly_interpolate_nmod_vec_fast
(mp_ptr poly, mp_srcptr xs, mp_srcptr ys, slong n, nmod_t mod)¶ Performs interpolation using the fast Lagrange interpolation algorithm, generating a temporary subproduct tree.
-
void
nmod_poly_interpolate_nmod_vec_fast
(nmod_poly_t poly, mp_srcptr xs, mp_srcptr ys, slong n)¶ Performs interpolation using the fast Lagrange interpolation algorithm, generating a temporary subproduct tree.
-
void
_nmod_poly_interpolate_nmod_vec_newton
(mp_ptr poly, mp_srcptr xs, mp_srcptr ys, slong n, nmod_t mod)¶ Forms the interpolating polynomial in the Newton basis using the method of divided differences and then converts it to monomial form.
-
void
nmod_poly_interpolate_nmod_vec_newton
(nmod_poly_t poly, mp_srcptr xs, mp_srcptr ys, slong n)¶ Forms the interpolating polynomial in the Newton basis using the method of divided differences and then converts it to monomial form.
-
void
_nmod_poly_interpolate_nmod_vec_barycentric
(mp_ptr poly, mp_srcptr xs, mp_srcptr ys, slong n, nmod_t mod)¶ Forms the interpolating polynomial using a naive implementation of the barycentric form of Lagrange interpolation.
-
void
nmod_poly_interpolate_nmod_vec_barycentric
(nmod_poly_t poly, mp_srcptr xs, mp_srcptr ys, slong n)¶ Forms the interpolating polynomial using a naive implementation of the barycentric form of Lagrange interpolation.
Composition¶
-
void
_nmod_poly_compose_horner
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Composes
poly1
of lengthlen1
withpoly2
of lengthlen2
and setsres
to the result, i.e.evaluatespoly1
atpoly2
. The algorithm used is Horner’s algorithm. We require thatres
have space for(len1 - 1)*(len2 - 1) + 1
coefficients. It is assumed thatlen1 > 0
andlen2 > 0
.
-
void
nmod_poly_compose_horner
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)¶ Composes
poly1
withpoly2
and setsres
to the result, i.e.evaluatespoly1
atpoly2
. The algorithm used is Horner’s algorithm.
-
void
_nmod_poly_compose_divconquer
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Composes
poly1
of lengthlen1
withpoly2
of lengthlen2
and setsres
to the result, i.e.evaluatespoly1
atpoly2
. The algorithm used is the divide and conquer algorithm. We require thatres
have space for(len1 - 1)*(len2 - 1) + 1
coefficients. It is assumed thatlen1 > 0
andlen2 > 0
.
-
void
nmod_poly_compose_divconquer
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)¶ Composes
poly1
withpoly2
and setsres
to the result, i.e.evaluatespoly1
atpoly2
. The algorithm used is the divide and conquer algorithm.
-
void
_nmod_poly_compose
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Composes
poly1
of lengthlen1
withpoly2
of lengthlen2
and setsres
to the result, i.e.evaluatespoly1
atpoly2
. We require thatres
have space for(len1 - 1)*(len2 - 1) + 1
coefficients. It is assumed thatlen1 > 0
andlen2 > 0
.
-
void
nmod_poly_compose
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2)¶ Composes
poly1
withpoly2
and setsres
to the result, that is, evaluatespoly1
atpoly2
.
Taylor shift¶
-
void
_nmod_poly_taylor_shift_horner
(mp_ptr poly, mp_limb_t c, slong len, nmod_t mod)¶ Performs the Taylor shift composing
poly
by \(x+c\) in-place. Uses an efficient version Horner’s rule.
-
void
nmod_poly_taylor_shift_horner
(nmod_poly_t g, const nmod_poly_t f, mp_limb_t c)¶ Performs the Taylor shift composing
f
by \(x+c\).
-
void
_nmod_poly_taylor_shift_convolution
(mp_ptr poly, mp_limb_t c, slong len, nmod_t mod)¶ Performs the Taylor shift composing
poly
by \(x+c\) in-place. Writes the composition as a single convolution with cost \(O(M(n))\). We require that the modulus is a prime at least as large as the length.
-
void
nmod_poly_taylor_shift_convolution
(nmod_poly_t g, const nmod_poly_t f, mp_limb_t c)¶ Performs the Taylor shift composing
f
by \(x+c\). Writes the composition as a single convolution with cost \(O(M(n))\). We require that the modulus is a prime at least as large as the length.
-
void
_nmod_poly_taylor_shift
(mp_ptr poly, mp_limb_t c, slong len, nmod_t mod)¶ Performs the Taylor shift composing
poly
by \(x+c\) in-place. We require that the modulus is a prime.
-
void
nmod_poly_taylor_shift
(nmod_poly_t g, const nmod_poly_t f, mp_limb_t c)¶ Performs the Taylor shift composing
f
by \(x+c\). We require that the modulus is a prime.
Modular composition¶
-
void
_nmod_poly_compose_mod_horner
(mp_ptr res, mp_srcptr f, slong lenf, mp_srcptr g, mp_srcptr h, slong lenh, nmod_t mod)¶ 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
nmod_poly_compose_mod_horner
(nmod_poly_t res, const nmod_poly_t f, const nmod_poly_t g, const nmod_poly_t h)¶ Sets
res
to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero. The algorithm used is Horner’s rule.
-
void
_nmod_poly_compose_mod_brent_kung
(mp_ptr res, mp_srcptr f, slong lenf, mp_srcptr g, mp_srcptr h, slong lenh, nmod_t mod)¶ 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
nmod_poly_compose_mod_brent_kung
(nmod_poly_t res, const nmod_poly_t f, const nmod_poly_t g, const nmod_poly_t h)¶ 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
_nmod_poly_compose_mod_brent_kung_preinv
(mp_ptr res, mp_srcptr f, slong lenf, mp_srcptr g, mp_srcptr h, slong lenh, mp_srcptr hinv, slong lenhinv, nmod_t mod)¶ 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
nmod_poly_compose_mod_brent_kung_preinv
(nmod_poly_t res, const nmod_poly_t f, const nmod_poly_t g, const nmod_poly_t h, const nmod_poly_t hinv)¶ 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
_nmod_poly_reduce_matrix_mod_poly
(nmod_mat_t A, const nmod_mat_t B, const nmod_poly_t f)¶ 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 *
_nmod_poly_precompute_matrix_worker
(void * arg_ptr)¶ Worker function version of
_nmod_poly_precompute_matrix
. Input/output is stored innmod_poly_matrix_precompute_arg_t
.
-
void
_nmod_poly_precompute_matrix
(nmod_mat_t A, mp_srcptr f, mp_srcptr g, slong leng, mp_srcptr ginv, slong lenginv, nmod_t mod)¶ 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.f
has to be reduced modulog
and of length one less thanleng
(possibly with zero padding).
-
void
nmod_poly_precompute_matrix
(nmod_mat_t A, const nmod_poly_t f, const nmod_poly_t g, const nmod_poly_t ginv)¶ 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 *
_nmod_poly_compose_mod_brent_kung_precomp_preinv_worker
(void * arg_ptr)¶ Worker function version of
_nmod_poly_compose_mod_brent_kung_precomp_preinv
. Input/output is stored innmod_poly_compose_mod_precomp_preinv_arg_t
.
-
void
_nmod_poly_compose_mod_brent_kung_precomp_preinv
(mp_ptr res, mp_srcptr f, slong lenf, const nmod_mat_t A, mp_srcptr h, slong lenh, mp_srcptr hinv, slong lenhinv, nmod_t mod)¶ 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
nmod_poly_compose_mod_brent_kung_precomp_preinv
(nmod_poly_t res, const nmod_poly_t f, const nmod_mat_t A, const nmod_poly_t h, const nmod_poly_t hinv)¶ 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\).
-
void
_nmod_poly_compose_mod_brent_kung_vec_preinv
(nmod_poly_struct * res, const nmod_poly_struct * polys, slong len1, slong l, mp_srcptr h, slong lenh, mp_srcptr hinv, slong lenhinv, nmod_t mod)¶ Sets
res
to the composition \(f_i(g)\) modulo \(h\) for \(1\leq i \leq l\), where \(f_i\) are the firstl
elements ofpolys
and \(g\) is the last element ofpolys
. We require that \(h\) is nonzero and that the length of \(g\) is less than the length of \(h\). We also require that the length of \(f_i\) is less than the length of \(h\). We requireres
to have enough memory allocated to holdl
nmod_poly_struct
. The entries ofres
need to be initialised andl
needs to be less thanlen1
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
nmod_poly_compose_mod_brent_kung_vec_preinv
(nmod_poly_struct * res, const nmod_poly_struct * polys, slong len1, slong n, const nmod_poly_t h, const nmod_poly_t hinv)¶ Sets
res
to the composition \(f_i(g)\) modulo \(h\) for \(1\leq i \leq n\) where \(f_i\) are the firstn
elements ofpolys
and \(g\) is the last element ofpolys
. We requireres
to have enough memory allocated to holdn
nmod_poly_struct
. The entries ofres
need to be uninitialised andn
needs to be less thanlen1
. We require that \(h\) is nonzero and that \(f_i\) and \(g\) have smaller degree than \(h\). Furthermore, we requirehinv
to be the inverse of the reverse ofh
. No aliasing ofres
andpolys
is allowed. The algorithm used is the Brent-Kung matrix algorithm.
-
void
_nmod_poly_compose_mod_brent_kung_vec_preinv_threaded
(nmod_poly_struct * res, const nmod_poly_struct * polys, slong lenpolys, slong l, mp_srcptr poly, slong len, mp_srcptr polyinv, slong leninv, nmod_t mod)¶ Multithreaded version of
_nmod_poly_compose_mod_brent_kung_vec_preinv
. Distributing the Horner evaluations acrossflint_get_num_threads()
threads.
-
void
nmod_poly_compose_mod_brent_kung_vec_preinv_threaded
(nmod_poly_struct * res, const nmod_poly_struct * polys, slong len1, slong n, const nmod_poly_t poly, const nmod_poly_t polyinv)¶ Multithreaded version of
nmod_poly_compose_mod_brent_kung_vec_preinv
. Distributing the Horner evaluations acrossflint_get_num_threads()
threads.
-
void
_nmod_poly_compose_mod
(mp_ptr res, mp_srcptr f, slong lenf, mp_srcptr g, mp_srcptr h, slong lenh, nmod_t mod)¶ 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
nmod_poly_compose_mod
(nmod_poly_t res, const nmod_poly_t f, const nmod_poly_t g, const nmod_poly_t h)¶ Sets
res
to the composition \(f(g)\) modulo \(h\). We require that \(h\) is nonzero.
Greatest common divisor¶
-
slong
_nmod_poly_gcd_euclidean
(mp_ptr G, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes the GCD of \(A\) of length
lenA
and \(B\) of lengthlenB
, wherelenA >= lenB > 0
. 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
nmod_poly_gcd_euclidean
(nmod_poly_t G, const nmod_poly_t A, const nmod_poly_t B)¶ 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.
-
slong
_nmod_poly_hgcd
(mp_ptr *M, slong *lenM, mp_ptr A, slong *lenA, mp_ptr B, slong *lenB, mp_srcptr a, slong lena, mp_srcptr b, slong lenb, nmod_t mod)¶ 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)\).
-
slong
_nmod_poly_gcd_hgcd
(mp_ptr G, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes the monic GCD of \(A\) and \(B\), assuming that \(\len(A) \geq \len(B) > 0\).
Assumes that \(G\) has space for \(\len(B)\) coefficients and returns the length of \(G\) on output.
-
void
nmod_poly_gcd_hgcd
(nmod_poly_t G, const nmod_poly_t A, const nmod_poly_t B)¶ Computes the monic GCD of \(A\) and \(B\) using the HGCD algorithm.
As a special case, the GCD of two zero polynomials is defined to be the zero polynomial.
The time complexity of the algorithm is \(\mathcal{O}(n \log^2 n)\). For further details, see~citep{ThullYap1990}.
-
slong
_nmod_poly_gcd
(mp_ptr G, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes the GCD of \(A\) of length
lenA
and \(B\) of lengthlenB
, wherelenA >= lenB > 0
. 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
nmod_poly_gcd
(nmod_poly_t G, const nmod_poly_t A, const nmod_poly_t B)¶ 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.
-
slong
_nmod_poly_xgcd_euclidean
(mp_ptr G, mp_ptr S, mp_ptr T, mp_srcptr A, slong A_len, mp_srcptr B, slong B_len, nmod_t mod)¶ 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
nmod_poly_xgcd_euclidean
(nmod_poly_t G, nmod_poly_t S, nmod_poly_t T, const nmod_poly_t A, const nmod_poly_t B)¶ 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
_nmod_poly_xgcd_hgcd
(mp_ptr G, mp_ptr S, mp_ptr T, mp_srcptr A, slong A_len, mp_srcptr B, slong B_len, nmod_t mod)¶ Computes the GCD of \(A\) and \(B\), where \(\len(A) \geq \len(B) > 0\), together with cofactors \(S\) and \(T\) such that \(S A + T B = G\). Returns the length of \(G\).
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 \len(B) - \len(G)\) and \(\len(T) \leq \len(A) - \len(G)\).
Both \(S\) and \(T\) must have space for at least \(2\) coefficients.
No aliasing of input and output operands is permitted.
-
void
nmod_poly_xgcd_hgcd
(nmod_poly_t G, nmod_poly_t S, nmod_poly_t T, const nmod_poly_t A, const nmod_poly_t B)¶ 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
_nmod_poly_xgcd
(mp_ptr G, mp_ptr S, mp_ptr T, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, nmod_t mod)¶ Computes the GCD of \(A\) and \(B\), where \(\len(A) \geq \len(B) > 0\), together with cofactors \(S\) and \(T\) such that \(S A + T B = G\). Returns the length of \(G\).
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 \len(B) - \len(G)\) and \(\len(T) \leq \len(A) - \len(G)\).
No aliasing of input and output operands is permitted.
-
void
nmod_poly_xgcd
(nmod_poly_t G, nmod_poly_t S, nmod_poly_t T, const nmod_poly_t A, const nmod_poly_t B)¶ 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.
The polynomials
S
andT
are set such thatS*A + T*B = G
. The length ofS
will be at mostlenB
and the length ofT
will be at mostlenA
.
-
mp_limb_t
_nmod_poly_resultant_euclidean
(mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Returns the resultant of
(poly1, len1)
and(poly2, len2)
using the Euclidean algorithm.Assumes that
len1 >= len2 > 0
.Assumes that the modulus is prime.
-
mp_limb_t
nmod_poly_resultant_euclidean
(const nmod_poly_t f, const nmod_poly_t g)¶ Computes the resultant of \(f\) and \(g\) using the Euclidean algorithm.
For two non-zero polynomials \(f(x) = a_m x^m + \dotsb + a_0\) and \(g(x) = b_n x^n + \dotsb + b_0\) of degrees \(m\) and \(n\), the resultant is defined to be
\[a_m^n b_n^m \prod_{(x, y) : f(x) = g(y) = 0} (x - y).\]For convenience, we define the resultant to be equal to zero if either of the two polynomials is zero.
-
mp_limb_t
_nmod_poly_resultant_hgcd
(mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Returns the resultant of
(poly1, len1)
and(poly2, len2)
using the half-gcd algorithm.This algorithm computes the half-gcd as per
_nmod_poly_gcd_hgcd()
but additionally updates the resultant every time a division occurs. The half-gcd algorithm computes the GCD recursively. Given inputs \(a\) and \(b\) it letsm = len(a)/2
and (recursively) performs all quotients in the Euclidean algorithm which do not require the low \(m\) coefficients of \(a\) and \(b\).This performs quotients in exactly the same order as the ordinary Euclidean algorithm except that the low \(m\) coefficients of the polynomials in the remainder sequence are not computed. A correction step after hgcd has been called computes these low \(m\) coefficients (by matrix multiplication by a transformation matrix also computed by hgcd).
This means that from the point of view of the resultant, all but the last quotient performed by a recursive call to hgcd is an ordinary quotient as per the usual Euclidean algorithm. However, the final quotient may give a remainder of less than \(m + 1\) coefficients, which won’t be corrected until the hgcd correction step is performed afterwards.
To compute the adjustments to the resultant coming from this corrected quotient, we save the relevant information in an
nmod_poly_res_t
struct at the time the quotient is performed so that when the correction step is performed later, the adjustments to the resultant can be computed at that time also.The only time an adjustment to the resultant is not required after a call to hgcd is if hgcd does nothing (the remainder may already have had less than \(m + 1\) coefficients when hgcd was called).
Assumes that
len1 >= len2 > 0
.Assumes that the modulus is prime.
-
mp_limb_t
nmod_poly_resultant_hgcd
(const nmod_poly_t f, const nmod_poly_t g)¶ Computes the resultant of \(f\) and \(g\) using the half-gcd algorithm.
For two non-zero polynomials \(f(x) = a_m x^m + \dotsb + a_0\) and \(g(x) = b_n x^n + \dotsb + b_0\) of degrees \(m\) and \(n\), the resultant is defined to be
\[a_m^n b_n^m \prod_{(x, y) : f(x) = g(y) = 0} (x - y).\]For convenience, we define the resultant to be equal to zero if either of the two polynomials is zero.
-
mp_limb_t
_nmod_poly_resultant
(mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, nmod_t mod)¶ Returns the resultant of
(poly1, len1)
and(poly2, len2)
.Assumes that
len1 >= len2 > 0
.Assumes that the modulus is prime.
-
mp_limb_t
nmod_poly_resultant
(const nmod_poly_t f, const nmod_poly_t g)¶ Computes the resultant of \(f\) and \(g\).
For two non-zero polynomials \(f(x) = a_m x^m + \dotsb + a_0\) and \(g(x) = b_n x^n + \dotsb + b_0\) of degrees \(m\) and \(n\), the resultant is defined to be
\[a_m^n b_n^m \prod_{(x, y) : f(x) = g(y) = 0} (x - y).\]For convenience, we define the resultant to be equal to zero if either of the two polynomials is zero.
-
slong
_nmod_poly_gcdinv
(mp_ptr G, mp_ptr S, mp_srcptr A, slong lenA, mp_srcptr B, slong lenB, const nmod_t mod)¶ Computes
(G, lenA)
,(S, lenB-1)
such that \(G \cong S A \pmod{B}\), returning the actual length of \(G\).Assumes that \(0 < \len(A) < \len(B)\).
-
void
nmod_poly_gcdinv
(nmod_poly_t G, nmod_poly_t S, const nmod_poly_t A, const nmod_poly_t B)¶ Computes polynomials \(G\) and \(S\), both reduced modulo~`B`, such that \(G \cong S A \pmod{B}\), where \(B\) is assumed to have \(\len(B) \geq 2\).
In the case that \(A = 0 \pmod{B}\), returns \(G = S = 0\).
-
int
_nmod_poly_invmod
(mp_ptr A, mp_srcptr B, slong lenB, mp_srcptr P, slong lenP, const nmod_t mod)¶ Attempts to set
(A, lenP-1)
to the inverse of(B, lenB)
modulo the polynomial(P, lenP)
. Returns \(1\) if(B, lenB)
is invertible and \(0\) otherwise.Assumes that \(0 < \len(B) < \len(P)\), and hence also \(\len(P) \geq 2\), but supports zero-padding in
(B, lenB)
.Does not support aliasing.
Assumes that \(mod\) is a prime number.
-
int
nmod_poly_invmod
(nmod_poly_t A, const nmod_poly_t B, const nmod_poly_t P)¶ Attempts to set \(A\) to the inverse of \(B\) modulo \(P\) in the polynomial ring \((\mathbf{Z}/p\mathbf{Z})[X]\), where we assume that \(p\) is a prime number.
If \(\len(P) < 2\), raises an exception.
If the greatest common divisor of \(B\) and \(P\) is~`1`, returns~`1` and sets \(A\) to the inverse of \(B\). Otherwise, returns~`0` and the value of \(A\) on exit is undefined.
Power series composition¶
-
mp_limb_t
_nmod_poly_discriminant
(mp_srcptr poly, slong len, nmod_t mod)¶ Return the discriminant of
(poly, len)
. Assumeslen > 1
.
-
mp_limb_t
nmod_poly_discriminant
(const nmod_poly_t f)¶ Return the discriminant of \(f\). We normalise the discriminant so that \(\operatorname{disc}(f) = (-1)^(n(n-1)/2) \operatorname{res}(f, f') / \operatorname{lc}(f)^(n - m - 2)\), where
n = len(f)
andm = len(f')
. Thus \(\operatorname{disc}(f) = \operatorname{lc}(f)^(2n - 2) \prod_{i < j} (r_i - r_j)^2\), where \(\operatorname{lc}(f)\) is the leading coefficient of \(f\) and \(r_i\) are the roots of \(f\).
Power series composition¶
-
void
_nmod_poly_compose_series_horner
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, slong n)¶ Sets
res
to the composition ofpoly1
andpoly2
modulo \(x^n\), where the constant term ofpoly2
is required to be zero.Assumes that
len1, len2, n > 0
, thatlen1, len2 <= n
, and that(len1-1) * (len2-1) + 1 <= n
, and thatres
has space forn
coefficients. Does not support aliasing between any of the inputs and the output.This implementation uses the Horner scheme.
-
void
nmod_poly_compose_series_horner
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n)¶ Sets
res
to the composition ofpoly1
andpoly2
modulo \(x^n\), where the constant term ofpoly2
is required to be zero.This implementation uses the Horner scheme.
-
void
_nmod_poly_compose_series_brent_kung
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, slong n)¶ Sets
res
to the composition ofpoly1
andpoly2
modulo \(x^n\), where the constant term ofpoly2
is required to be zero.Assumes that
len1, len2, n > 0
, thatlen1, len2 <= n
, and that\(len1-1) * (len2-1) + 1 <= n
, and thatres
has space forn
coefficients. Does not support aliasing between any of the inputs and the output.This implementation uses Brent-Kung algorithm 2.1 cite{BrentKung1978}.
-
void
nmod_poly_compose_series_brent_kung
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n)¶ Sets
res
to the composition ofpoly1
andpoly2
modulo \(x^n\), where the constant term ofpoly2
is required to be zero.This implementation uses Brent-Kung algorithm 2.1 cite{BrentKung1978}.
-
void
_nmod_poly_compose_series_divconquer
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, slong N, nmod_t mod)¶ Composes
poly1
of length \(\ell_1\) withpoly2
of length \(\ell_2\) modulo \(x^N\) and setsres
to the result, i.e.evaluatespoly1
atpoly2
.Writes \(\min\{(\ell_1 - 1)(\ell_2 - 2) + 1, N\}\) coefficients to the vector
res
.The algorithm used is the divide and conquer algorithm. It is assumed that \(0 < \ell_1\) and \(0 < \ell_2 \leq N\).
Does not support aliasing between the inputs and the output.
-
void
nmod_poly_compose_series_divconquer
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong N)¶ Composes
poly1
withpoly2
modulo \(x^N\) and setsres
to the result, i.e.evaluatespoly1
atpoly2
.The algorithm used is the divide and conquer algorithm.
-
void
_nmod_poly_compose_series
(mp_ptr res, mp_srcptr poly1, slong len1, mp_srcptr poly2, slong len2, slong n)¶ Sets
res
to the composition ofpoly1
andpoly2
modulo \(x^n\), where the constant term ofpoly2
is required to be zero.Assumes that
len1, len2, n > 0
, thatlen1, len2 <= n
, and that\(len1-1) * (len2-1) + 1 <= n
, and thatres
has space forn
coefficients. Does not support aliasing between any of the inputs and the output.This implementation automatically switches between the Horner scheme and Brent-Kung algorithm 2.1 depending on the size of the inputs.
-
void
nmod_poly_compose_series
(nmod_poly_t res, const nmod_poly_t poly1, const nmod_poly_t poly2, slong n)¶ Sets
res
to the composition ofpoly1
andpoly2
modulo \(x^n\), where the constant term ofpoly2
is required to be zero.This implementation automatically switches between the Horner scheme and Brent-Kung algorithm 2.1 depending on the size of the inputs.
Power series reversion¶
-
void
_nmod_poly_revert_series_lagrange
(mp_ptr Qinv, mp_srcptr Q, slong n, nmod_t mod)¶ Sets
Qinv
to the compositional inverse or reversion ofQ
as a power series, i.e. computes \(Q^{-1}\) such that \(Q(Q^{-1}(x)) = Q^{-1}(Q(x)) = x \bmod x^n\). The arguments must both have lengthn
and may not be aliased.It is required that \(Q_0 = 0\) and that \(Q_1\) as well as the integers \(1, 2, \ldots, n-1\) are invertible modulo the modulus.
This implementation uses the Lagrange inversion formula.
-
void
nmod_poly_revert_series_lagrange
(nmod_poly_t Qinv, const nmod_poly_t Q, slong n)¶ Sets
Qinv
to the compositional inverse or reversion ofQ
as a power series, i.e. computes \(Q^{-1}\) such that \(Q(Q^{-1}(x)) = Q^{-1}(Q(x)) = x \bmod x^n\).It is required that \(Q_0 = 0\) and that \(Q_1\) as well as the integers \(1, 2, \ldots, n-1\) are invertible modulo the modulus.
This implementation uses the Lagrange inversion formula.
-
void
_nmod_poly_revert_series_lagrange_fast
(mp_ptr Qinv, mp_srcptr Q, slong n, nmod_t mod)¶ Sets
Qinv
to the compositional inverse or reversion ofQ
as a power series, i.e. computes \(Q^{-1}\) such that \(Q(Q^{-1}(x)) = Q^{-1}(Q(x)) = x \bmod x^n\). The arguments must both have lengthn
and may not be aliased.It is required that \(Q_0 = 0\) and that \(Q_1\) as well as the integers \(1, 2, \ldots, n-1\) are invertible modulo the modulus.
This implementation uses a reduced-complexity implementation of the Lagrange inversion formula.
-
void
nmod_poly_revert_series_lagrange_fast
(nmod_poly_t Qinv, const nmod_poly_t Q, slong n)¶ Sets
Qinv
to the compositional inverse or reversion ofQ
as a power series, i.e. computes \(Q^{-1}\) such that \(Q(Q^{-1}(x)) = Q^{-1}(Q(x)) = x \bmod x^n\).It is required that \(Q_0 = 0\) and that \(Q_1\) as well as the integers \(1, 2, \ldots, n-1\) are invertible modulo the modulus.
This implementation uses a reduced-complexity implementation of the Lagrange inversion formula.
-
void
_nmod_poly_revert_series_newton
(mp_ptr Qinv, mp_srcptr Q, slong n, nmod_t mod)¶ Sets
Qinv
to the compositional inverse or reversion ofQ
as a power series, i.e. computes \(Q^{-1}\) such that \(Q(Q^{-1}(x)) = Q^{-1}(Q(x)) = x \bmod x^n\). The arguments must both have lengthn
and may not be aliased.It is required that \(Q_0 = 0\) and that \(Q_1\) as well as the integers \(1, 2, \ldots, n-1\) are invertible modulo the modulus.
This implementation uses Newton iteration cite{BrentKung1978}.
-
void
nmod_poly_revert_series_newton
(nmod_poly_t Qinv, const nmod_poly_t Q, slong n)¶ Sets
Qinv
to the compositional inverse or reversion ofQ
as a power series, i.e. computes \(Q^{-1}\) such that \(Q(Q^{-1}(x)) = Q^{-1}(Q(x)) = x \bmod x^n\).It is required that \(Q_0 = 0\) and that \(Q_1\) as well as the integers \(1, 2, \ldots, n-1\) are invertible modulo the modulus.
This implementation uses Newton iteration cite{BrentKung1978}.
-
void
_nmod_poly_revert_series
(mp_ptr Qinv, mp_srcptr Q, slong n, nmod_t mod)¶ Sets
Qinv
to the compositional inverse or reversion ofQ
as a power series, i.e. computes \(Q^{-1}\) such that \(Q(Q^{-1}(x)) = Q^{-1}(Q(x)) = x \bmod x^n\). The arguments must both have lengthn
and may not be aliased.It is required that \(Q_0 = 0\) and that \(Q_1\) as well as the integers \(1, 2, \ldots, n-1\) are invertible modulo the modulus.
This implementation automatically chooses between the Lagrange inversion formula and Newton iteration based on the size of the input.
-
void
nmod_poly_revert_series
(nmod_poly_t Qinv, const nmod_poly_t Q, slong n)¶ Sets
Qinv
to the compositional inverse or reversion ofQ
as a power series, i.e. computes \(Q^{-1}\) such that \(Q(Q^{-1}(x)) = Q^{-1}(Q(x)) = x \bmod x^n\).It is required that \(Q_0 = 0\) and that \(Q_1\) as well as the integers \(1, 2, \ldots, n-1\) are invertible modulo the modulus.
This implementation automatically chooses between the Lagrange inversion formula and Newton iteration based on the size of the input.
Square roots¶
The series expansions for \(\sqrt{h}\) and \(1/\sqrt{h}\) are defined
by means of the generalised binomial theorem
h^r = (1+y)^r =
\sum_{k=0}^{\infty} {r \choose k} y^k.
It is assumed that \(h\) has constant term \(1\) and that the coefficients
\(2^{-k}\) exist in the coefficient ring (i.e. \(2\) must be invertible).
-
void
_nmod_poly_invsqrt_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t 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.
-
void
nmod_poly_invsqrt_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g\) to the series expansion of \(1/\sqrt{h}\) to order \(O(x^n)\). It is assumed that \(h\) has constant term 1.
-
void
_nmod_poly_sqrt_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ 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.
-
void
nmod_poly_sqrt_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g\) to the series expansion of \(\sqrt{h}\) to order \(O(x^n)\). It is assumed that \(h\) has constant term 1.
-
int
_nmod_poly_sqrt
(mp_ptr s, mp_srcptr p, slong n, nmod_t 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.
-
int
nmod_poly_sqrt
(nmod_poly_t s, const nmod_poly_t p)¶ If \(p\) is a perfect square, sets \(s\) to a square root of \(p\) and returns 1. Otherwise returns 0.
Power sums¶
-
void
_nmod_poly_power_sums_naive
(mp_ptr res, mp_srcptr poly, slong len, slong n, nmod_t mod)¶ Compute the (truncated) power sums series of the polynomial
(poly,len)
up to length \(n\) using Newton identities.
-
void
nmod_poly_power_sums_naive
(nmod_poly_t res, const nmod_poly_t poly, slong n)¶ Compute the (truncated) power sum series of the polynomial
poly
up to length \(n\) using Newton identities.
-
void
_nmod_poly_power_sums_schoenhage
(mp_ptr res, mp_srcptr poly, slong len, slong n, nmod_t mod)¶ Compute the (truncated) power sums series of the polynomial
(poly,len)
up to length \(n\) using a series expansion (a formula due to Schoenhage).
-
void
nmod_poly_power_sums_schoenhage
(nmod_poly_t res, const nmod_poly_t poly, slong n)¶ Compute the (truncated) power sums series of the polynomial
poly
up to length \(n\) using a series expansion (a formula due to Schoenhage).
-
void
_nmod_poly_power_sums
(mp_ptr res, mp_srcptr poly, slong len, slong n, nmod_t mod)¶ Compute the (truncated) power sums series of the polynomial
(poly,len)
up to length \(n\).
-
void
nmod_poly_power_sums
(nmod_poly_t res, const nmod_poly_t poly, slong n)¶ Compute the (truncated) power sums series of the polynomial
poly
up to length \(n\).
-
void
_nmod_poly_power_sums_to_poly_naive
(mp_ptr res, mp_srcptr poly, slong len, nmod_t mod)¶ Compute the (monic) polynomial given by its power sums series
(poly,len)
using Newton identities.
-
void
nmod_poly_power_sums_to_poly_naive
(nmod_poly_t res, const nmod_poly_t Q)¶ Compute the (monic) polynomial given by its power sums series
Q
using Newton identities.
-
void
_nmod_poly_power_sums_to_poly_schoenhage
(mp_ptr res, mp_srcptr poly, slong len, nmod_t mod)¶ Compute the (monic) polynomial given by its power sums series
(poly,len)
using series expansion (a formula due to Schoenhage).
-
void
nmod_poly_power_sums_to_poly_schoenhage
(nmod_poly_t res, const nmod_poly_t Q)¶ Compute the (monic) polynomial given by its power sums series
Q
using series expansion (a formula due to Schoenhage).
-
void
_nmod_poly_power_sums_to_poly
(mp_ptr res, mp_srcptr poly, slong len, nmod_t mod)¶ Compute the (monic) polynomial given by its power sums series
(poly,len)
.
-
void
nmod_poly_power_sums_to_poly
(nmod_poly_t res, const nmod_poly_t Q)¶ Compute the (monic) polynomial given by its power sums series
Q
.
Transcendental functions¶
The elementary transcendental functions of a formal power series \(h\)
are defined as
\exp(h(x)) = \sum_{k=0}^{\infty} \frac{(h(x))^k}{k!}
\log(h(x)) = \int_0^x \frac{h'(t)}{h(t)} dt
\operatorname{atan}(h(x)) = \int_0^x\frac{h'(t)}{1+(h(t))^2} dt
\operatorname{atanh}(h(x)) = \int_0^x\frac{h'(t)}{1-(h(t))^2} dt
\operatorname{asin}(h(x)) = \int_0^x\frac{h'(t)}{\sqrt{1-(h(t))^2}} dt
\operatorname{asinh}(h(x)) = \int_0^x\frac{h'(t)}{\sqrt{1+(h(t))^2}} dt
The functions sin, cos, tan, etc. are defined using standard inverse
or functional relations.
The logarithm function assumes that \(h\) has constant term \(1\). All
other functions assume that \(h\) has constant term \(0\).
All functions assume that the coefficient \(1/k\) or \(1/k!\) exists
for all indices \(k\). When computing to order \(O(x^n)\), the modulus \(p\)
must therefore be a prime satisfying \(p \ge n\). Further, we always
require that \(p > 2\) in order to be able to multiply by \(1/2\) for
internal purposes.
If the input does not satisfy all these conditions, results are undefined.
Except where otherwise noted, functions are implemented with optimal
(up to constants) complexity \(O(M(n))\), where \(M(n)\) is the cost
of polynomial multiplication.
-
void
_nmod_poly_log_series_monomial_ui
(mp_ptr g, mp_limb_t c, ulong r, slong n, nmod_t mod)¶ Set \(g = \log(1+cx^r) + O(x^n)\). Assumes \(n > 0\), \(r > 0\), and that the coefficient is reduced by the modulus. Works efficiently in linear time.
-
void
nmod_poly_log_series_monomial_ui
(nmod_poly_t g, mp_limb_t c, ulong r, slong n)¶ Set \(g = \log(1+cx^r) + O(x^n)\). Works efficiently in linear time.
-
void
_nmod_poly_log_series
(mp_ptr g, mp_srcptr h, slong hlen, slong n, nmod_t mod)¶ Set \(g = \log(h) + O(x^n)\). Assumes \(n > 0\) and
hlen > 0
. Aliasing of \(g\) and \(h\) is allowed.
-
void
nmod_poly_log_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \log(h) + O(x^n)\). The case \(h = 1+cx^r\) is automatically detected and handled efficiently.
-
void
_nmod_poly_exp_series_monomial_ui
(mp_ptr g, mp_limb_t c, ulong r, slong n, nmod_t mod)¶ Set \(g = \exp(cx^r) + O(x^n)\). Assumes \(n > 0\), \(r > 0\), and that the coefficient is reduced by the modulus. Works efficiently in linear time.
-
void
nmod_poly_exp_series_monomial_ui
(nmod_poly_t g, mp_limb_t c, ulong r, slong n)¶ Set \(g = \exp(cx^r) + O(x^n)\). Works efficiently in linear time.
-
void
_nmod_poly_exp_series_basecase
(mp_ptr g, mp_srcptr h, slong hlen, slong n, nmod_t mod)¶ Set \(g = \exp(h) + O(x^n)\) using a simple \(O(n^2)\) algorithm. Assumes \(n > 0\) and \(\operatorname{hlen} > 0\). Only the first \(\operatorname{hlen}\) coefficients of \(h\) will be read. Aliasing of \(f\) and \(h\) is allowed.
-
void
nmod_poly_exp_series_basecase
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \exp(h) + O(x^n)\) using a simple \(O(n^2)\) algorithm.
-
void
_nmod_poly_exp_series2
(mp_ptr f, mp_srcptr h, slong hlen, slong n, nmod_t mod)¶ Set \(f = \exp(h) + O(x^n)\) where
h
is a polynomial. Assume \(n > 0\). Aliasing of \(g\) and \(h\) is not allowed.Uses Newton iteration (the version given in cite{HanZim2004}). For small \(n\), falls back to the basecase algorithm.
-
void
_nmod_poly_exp_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Deprecated version of
_nmod_poly_exp_series2
in which the result(g,n)
and the input(h,n)
must have the same length (zero-padded if necessary).
-
void
_nmod_poly_exp_expinv_series
(mp_ptr f, mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(f = \exp(h) + O(x^n)\) and \(g = \exp(-h) + O(x^n)\), more efficiently for large \(n\) than performing a separate inversion to obtain \(g\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing is not allowed.
Uses Newton iteration (the version given in cite{HanZim2004}). For small \(n\), falls back to the basecase algorithm.
-
void
nmod_poly_exp_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \exp(h) + O(x^n)\). The case \(h = cx^r\) is automatically detected and handled efficiently. Otherwise this function automatically uses the basecase algorithm for small \(n\) and Newton iteration otherwise.
-
void
_nmod_poly_atan_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{atan}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is allowed.
-
void
nmod_poly_atan_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{atan}(h) + O(x^n)\).
-
void
_nmod_poly_atanh_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{atanh}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is allowed.
-
void
nmod_poly_atanh_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{atanh}(h) + O(x^n)\).
-
void
_nmod_poly_asin_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{asin}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is allowed. The modulus must be less than \(n\) and not equal to \(2\).
-
void
nmod_poly_asin_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{asin}(h) + O(x^n)\). The modulus must be less than \(n\) and not equal to \(2\).
-
void
_nmod_poly_asinh_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{asinh}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is allowed. The modulus must be less than \(n\) and not equal to \(2\).
-
void
nmod_poly_asinh_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{asinh}(h) + O(x^n)\). The modulus must be less than \(n\) and not equal to \(2\).
-
void
_nmod_poly_sin_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{sin}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is allowed. The modulus must be less than \(n\) and not equal to \(2\). The value is computed using the identity \(\sin(x) = 2 \tan(x/2)) / (1 + \tan^2(x/2)).\)
-
void
nmod_poly_sin_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{sin}(h) + O(x^n)\). The modulus must be less than \(n\) and not equal to \(2\).
-
void
_nmod_poly_cos_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{cos}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is allowed. The modulus must be less than \(n\) and not equal to \(2\). The value is computed using the identity \(\cos(x) = (1-\tan^2(x/2)) / (1 + \tan^2(x/2)).\)
-
void
nmod_poly_cos_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{cos}(h) + O(x^n)\). The modulus must be less than \(n\) and not equal to \(2\).
-
void
_nmod_poly_tan_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{tan}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is not allowed. The modulus must be less than \(n\). Uses Newton iteration to invert the atan function.
-
void
nmod_poly_tan_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{tan}(h) + O(x^n)\). The modulus must be less than \(n\).
-
void
_nmod_poly_sinh_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{sinh}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is not allowed. The modulus must be less than \(n\) and not equal to \(2\). Uses the identity \(\sinh(x) = (e^x - e^{-x})/2\).
-
void
nmod_poly_sinh_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{sinh}(h) + O(x^n)\). The modulus must be less than \(n\) and not equal to \(2\).
-
void
_nmod_poly_cosh_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{cos}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). Aliasing of \(g\) and \(h\) is not allowed. The modulus must be less than \(n\) and not equal to \(2\). Uses the identity \(\cosh(x) = (e^x + e^{-x})/2\).
-
void
nmod_poly_cosh_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{cosh}(h) + O(x^n)\). The modulus must be less than \(n\) and not equal to \(2\).
-
void
_nmod_poly_tanh_series
(mp_ptr g, mp_srcptr h, slong n, nmod_t mod)¶ Set \(g = \operatorname{tanh}(h) + O(x^n)\). Assumes \(n > 0\) and that \(h\) is zero-padded as necessary to length \(n\). The modulus must be less than \(n\) and not equal to \(2\). Uses the identity \(\tanh(x) = (e^{2x}-1)/(e^{2x}+1)\).
-
void
nmod_poly_tanh_series
(nmod_poly_t g, const nmod_poly_t h, slong n)¶ Set \(g = \operatorname{tanh}(h) + O(x^n)\). The modulus must be less than \(n\) and not equal to \(2\).
Products¶
-
void
_nmod_poly_product_roots_nmod_vec
(mp_ptr poly, mp_srcptr xs, slong n, nmod_t mod)¶ Sets
(poly, n + 1)
to the monic polynomial which is the product of \((x - x_0)(x - x_1) \cdots (x - x_{n-1})\), the roots \(x_i\) being given byxs
.Aliasing of the input and output is not allowed.
-
void
nmod_poly_product_roots_nmod_vec
(nmod_poly_t poly, mp_srcptr xs, slong n)¶ Sets
poly
to the monic polynomial which is the product of \((x - x_0)(x - x_1) \cdots (x - x_{n-1})\), the roots \(x_i\) being given byxs
.
Subproduct trees¶
-
mp_ptr *
_nmod_poly_tree_alloc
(slong len)¶ Allocates space for a subproduct tree of the given length, having linear factors at the lowest level.
Entry \(i\) in the tree is a pointer to a single array of limbs, capable of storing \(\lfloor n / 2^i \rfloor\) subproducts of degree \(2^i\) adjacently, plus a trailing entry if \(n / 2^i\) is not an integer.
For example, a tree of length 7 built from monic linear factors has the following structure, where spaces have been inserted for illustrative purposes:
X1 X1 X1 X1 X1 X1 X1 XX1 XX1 XX1 X1 XXXX1 XX1 X1 XXXXXXX1
-
void
_nmod_poly_tree_free
(mp_ptr * tree, slong len)¶ Free the allocated space for the subproduct.
-
void
_nmod_poly_tree_build
(mp_ptr * tree, mp_srcptr roots, slong len, nmod_t mod)¶ Builds a subproduct tree in the preallocated space from the
len
monic linear factors \((x-r_i)\). The top level product is not computed.
Inflation and deflation¶
-
void
nmod_poly_inflate
(nmod_poly_t result, const nmod_poly_t input, ulong inflation)¶ Sets
result
to the inflated polynomial \(p(x^n)\) where \(p\) is given byinput
and \(n\) is given bydeflation
.
-
void
nmod_poly_deflate
(nmod_poly_t result, const nmod_poly_t input, ulong deflation)¶ Sets
result
to the deflated polynomial \(p(x^{1/n})\) where \(p\) is given byinput
and \(n\) is given bydeflation
. Requires \(n > 0\).
-
ulong
nmod_poly_deflation
(const nmod_poly_t input)¶ 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.