signed_mpn_sub_n res op1 op2 n

If op1 >= op2 return 0 and set res to op1 - op2 else return 1 and set res to op2 - op1.

nmod_poly_init poly n

Initialises poly. It will have coefficients modulo~`n`.

nmod_poly_init_preinv poly n ninv

Initialises poly. It will have coefficients modulo~`n`. The caller supplies a precomputed inverse limb generated by n_preinvert_limb.

nmod_poly_init_mod poly mod

Initialises poly using an already initialised modulus mod.

nmod_poly_init2 poly n alloc

Initialises poly. It will have coefficients modulo~`n`. Up to alloc coefficients may be stored in poly.

nmod_poly_init2_preinv poly n ninv alloc

Initialises poly. It will have coefficients modulo~`n`. The caller supplies a precomputed inverse limb generated by n_preinvert_limb. Up to alloc coefficients may be stored in poly.

nmod_poly_realloc poly alloc

Reallocates poly to the given length. If the current length is less than alloc, the polynomial is truncated and normalised. If alloc is zero, the polynomial is cleared.

nmod_poly_clear poly

Clears the polynomial and releases any memory it used. The polynomial cannot be used again until it is initialised.

nmod_poly_fit_length poly alloc

Ensures poly has space for at least alloc coefficients. This function only ever grows the allocated space, so no data loss can occur.

_nmod_poly_normalise poly

Internal function for normalising a polynomial so that the top coefficient, if there is one at all, is not zero.

nmod_poly_length poly

Returns the length of the polynomial poly. The zero polynomial has length zero.

nmod_poly_degree poly

Returns the degree of the polynomial poly. The zero polynomial is deemed to have degree~`-1`.

nmod_poly_modulus poly

Returns the modulus of the polynomial poly. This will be a positive integer.

nmod_poly_max_bits poly

Returns the maximum number of bits of any coefficient of poly.

nmod_poly_set a b

Sets a to a copy of b.

nmod_poly_swap poly1 poly2

Efficiently swaps poly1 and poly2 by swapping pointers internally.

nmod_poly_zero res

Sets res to the zero polynomial.

nmod_poly_truncate poly len

Truncates poly to the given length and normalises it. If len is greater than the current length of poly, then nothing happens.

nmod_poly_set_trunc res poly n

Notionally truncate poly to length \(n\) and set res to the result. The result is normalised.

_nmod_poly_reverse output input len m

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

nmod_poly_reverse output input m

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

nmod_poly_randtest poly state len

Generates a random polynomial with length up to len.

nmod_poly_randtest_irreducible poly state len

Generates a random irreducible polynomial with length up to len.

nmod_poly_randtest_monic poly state len

Generates a random monic polynomial with length len.

nmod_poly_randtest_monic_irreducible poly state len

Generates a random monic irreducible polynomial with length len.

nmod_poly_randtest_monic_primitive poly state len

Generates a random monic irreducible primitive polynomial with length len.

nmod_poly_randtest_trinomial poly state len

Generates a random monic trinomial of length len.

nmod_poly_randtest_trinomial_irreducible poly state len max_attempts

Attempts to set poly to a monic irreducible trinomial of length len. It will generate up to max_attempts trinomials in attempt to find an irreducible one. If max_attempts is 0, then it will keep generating trinomials until an irreducible one is found. Returns \(1\) if one is found and \(0\) otherwise.

nmod_poly_randtest_pentomial poly state len

Generates a random monic pentomial of length len.

nmod_poly_randtest_pentomial_irreducible poly state len max_attempts

Attempts to set poly to a monic irreducible pentomial of length len. It will generate up to max_attempts pentomials in attempt to find an irreducible one. If max_attempts is 0, then it will keep generating pentomials until an irreducible one is found. Returns \(1\) if one is found and \(0\) otherwise.

nmod_poly_randtest_sparse_irreducible poly state len

Attempts to set poly to a sparse, monic irreducible polynomial with length len. It attempts to find an irreducible trinomial. If that does not succeed, it attempts to find a irreducible pentomial. If that fails, then poly is just set to a random monic irreducible polynomial.

nmod_poly_get_coeff_ui poly j

Returns the coefficient of poly at index~j, where coefficients are numbered with zero being the constant coefficient, and returns it as an ulong. If j refers to a coefficient beyond the end of poly, zero is returned.

nmod_poly_set_coeff_ui poly j c

Sets the coefficient of poly at index j, where coefficients are numbered with zero being the constant coefficient, to the value c reduced modulo the modulus of poly. If j refers to a coefficient beyond the current end of poly, the polynomial is first resized, with intervening coefficients being set to zero.

nmod_poly_get_str poly

Writes poly to a string representation. The format is as described for nmod_poly_print. The string must be freed by the user when finished. For this it is sufficient to call flint_free.

nmod_poly_get_str_pretty poly x

Writes poly to a pretty string representation. The format is as described for nmod_poly_print_pretty. The string must be freed by the user when finished. For this it is sufficient to call flint_free.

It is assumed that the top coefficient is non-zero.

nmod_poly_set_str poly s

Reads poly from a string s. The format is as described for nmod_poly_print. If a polynomial in the correct format is read, a positive value is returned, otherwise a non-positive value is returned.

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

nmod_poly_print_pretty a x

Prints the polynomial to stdout using the string x 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.

nmod_poly_fread f poly

Reads poly from the file stream f. If this is a file that has just been written, the file should be closed then opened again. The format is as described for nmod_poly_print. If a polynomial in the correct format is read, a positive value is returned, otherwise a non-positive value is returned.

nmod_poly_fprint f 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 for nmod_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.

nmod_poly_fprint_pretty f poly 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 for nmod_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.

nmod_poly_read poly

Read poly from stdin. The format is as described for nmod_poly_print. If a polynomial in the correct format is read, a positive value is returned, otherwise a non-positive value is returned.

nmod_poly_equal a b

Returns~`1` if the polynomials are equal, otherwise~`0`.

nmod_poly_equal_trunc poly1 poly2 n

Notionally truncate poly1 and poly2 to length \(n\) and return \(1\) if the truncations are equal, otherwise return \(0\).

nmod_poly_is_zero poly

Returns~`1` if the polynomial poly is the zero polynomial, otherwise returns~`0`.

nmod_poly_is_one poly

Returns~`1` if the polynomial poly is the constant polynomial 1, otherwise returns~`0`.

_nmod_poly_shift_left res poly len k

Sets (res, len + k) to (poly, len) shifted left by k coefficients. Assumes that res has space for len + k coefficients.

nmod_poly_shift_left res poly k

Sets res to poly shifted left by k coefficients, i.e.multiplied by \(x^k\).

_nmod_poly_shift_right res poly len k

Sets (res, len - k) to (poly, len) shifted left by k coefficients. It is assumed that k <= len and that res has space for at least len - k coefficients.

nmod_poly_shift_right res poly k

Sets res to poly shifted right by k coefficients, i.e.divide by \(x^k\) and throws away the remainder. If k is greater than or equal to the length of poly, the result is the zero polynomial.

_nmod_poly_add res poly1 len1 poly2 len2 mod

Sets res to the sum of (poly1, len1) and (poly2, len2). There are no restrictions on the lengths.

nmod_poly_add res poly1 poly2

Sets res to the sum of poly1 and poly2.

nmod_poly_add_series res poly1 poly2 n

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

_nmod_poly_sub res poly1 len1 poly2 len2 mod

Sets res to the difference of (poly1, len1) and (poly2, len2). There are no restrictions on the lengths.

nmod_poly_sub res poly1 poly2

Sets res to the difference of poly1 and poly2.

nmod_poly_sub_series res poly1 poly2 n

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

nmod_poly_neg res poly

Sets res to the negation of poly.

nmod_poly_scalar_mul_nmod res poly c

Sets res to (poly, len) multiplied by~`c`, where~`c` is reduced modulo the modulus of poly.

_nmod_poly_make_monic output input len mod

Sets output to be the scalar multiple of input of length len > 0 that has leading coefficient one, if such a polynomial exists. If the leading coefficient of input is not invertible, output is set to the multiple of input whose leading coefficient is the greatest common divisor of the leading coefficient and the modulus of input.

nmod_poly_make_monic output input

Sets output to be the scalar multiple of input with leading coefficient one, if such a polynomial exists. If input is zero an exception is raised. If the leading coefficient of input is not invertible, output is set to the multiple of input whose leading coefficient is the greatest common divisor of the leading coefficient and the modulus of input.

_nmod_poly_bit_pack res poly len bits

Packs len coefficients of poly into fields of the given number of bits in the large integer res, i.e.evaluates poly at 2^bits and store the result in res. Assumes len > 0 and bits > 0. Also assumes that no coefficient of poly is bigger than bits/2 bits. We also assume bits < 3 * FLINT_BITS.

_nmod_poly_bit_unpack res len mpn bits mod

Unpacks len coefficients stored in the big integer mpn in bit fields of the given number of bits, reduces them modulo the given modulus, then stores them in the polynomial res. We assume len > 0 and 3 * FLINT_BITS > bits > 0. There are no restrictions on the size of the actual coefficients as stored within the bitfields.

nmod_poly_bit_pack f poly bit_size

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

nmod_poly_bit_unpack poly f bit_size

Unpacks the polynomial from fields of size bit_size as represented by the integer f.

_nmod_poly_KS2_pack1 res op n s b k r

Same as _nmod_poly_KS2_pack, but requires b <= FLINT_BITS.

_nmod_poly_KS2_pack res op n s b k r

Bit packing routine used by KS2 and KS4 multiplication.

_nmod_poly_KS2_unpack1 res op n b k

Same as _nmod_poly_KS2_unpack, but requires b <= FLINT_BITS (i.e. writes one word per coefficient).

_nmod_poly_KS2_unpack2 res op n b k

Same as _nmod_poly_KS2_unpack, but requires FLINT_BITS < b <= 2 * FLINT_BITS (i.e. writes two words per coefficient).

_nmod_poly_KS2_unpack3 res op n b k

Same as _nmod_poly_KS2_unpack, but requires 2 * FLINT_BITS < b < 3 * FLINT_BITS (i.e. writes three words per coefficient).

_nmod_poly_KS2_unpack res op n b k

Bit unpacking code used by KS2 and KS4 multiplication.

_nmod_poly_KS2_reduce res s op n w mod

Reduction code used by KS2 and KS4 multiplication.

_nmod_poly_KS2_recover_reduce1 res s op1 op2 n b mod

Same as _nmod_poly_KS2_recover_reduce, but requires 0 < 2 * b <= FLINT_BITS.

_nmod_poly_KS2_recover_reduce2 res s op1 op2 n b mod

Same as _nmod_poly_KS2_recover_reduce, but requires FLINT_BITS < 2 * b < 2*FLINT_BITS.

_nmod_poly_KS2_recover_reduce2b res s op1 op2 n b mod

Same as _nmod_poly_KS2_recover_reduce, but requires b == FLINT_BITS.

_nmod_poly_KS2_recover_reduce3 res s op1 op2 n b mod

Same as _nmod_poly_KS2_recover_reduce, but requires 2 * FLINT_BITS < 2 * b <= 3 * FLINT_BITS.

_nmod_poly_KS2_recover_reduce res s op1 op2 n b mod

Reduction code used by KS4 multiplication.

_nmod_poly_mul_classical res poly1 len1 poly2 len2 mod

Sets (res, len1 + len2 - 1) to the product of (poly1, len1) and (poly2, len2). Assumes len1 >= len2 > 0. Aliasing of inputs and output is not permitted.

nmod_poly_mul_classical res poly1 poly2

Sets res to the product of poly1 and poly2.

_nmod_poly_mullow_classical res poly1 len1 poly2 len2 trunc mod

Sets res to the lower trunc coefficients of the product of (poly1, len1) and (poly2, len2). Assumes that len1 >= len2 > 0 and trunc > 0. Aliasing of inputs and output is not permitted.

nmod_poly_mullow_classical res poly1 poly2 trunc

Sets res to the lower trunc coefficients of the product of poly1 and poly2.

_nmod_poly_mulhigh_classical res poly1 len1 poly2 len2 start mod

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

nmod_poly_mulhigh_classical res poly1 poly2 start

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

_nmod_poly_mul_KS out in1 len1 in2 len2 bits mod

Sets res to the product of in1 and in2 assuming the output coefficients are at most the given number of bits wide. If bits is set to \(0\) an appropriate value is computed automatically. Assumes that len1 >= len2 > 0.

nmod_poly_mul_KS res poly1 poly2 bits

Sets res to the product of poly1 and poly2 assuming the output coefficients are at most the given number of bits wide. If bits is set to \(0\) an appropriate value is computed automatically.

_nmod_poly_mul_KS2 res op1 n1 op2 n2 mod

Sets res to the product of op1 and op2. Assumes that len1 >= len2 > 0.

nmod_poly_mul_KS2 res poly1 poly2

Sets res to the product of poly1 and poly2.

_nmod_poly_mul_KS4 res op1 n1 op2 n2 mod

Sets res to the product of op1 and op2. Assumes that len1 >= len2 > 0.

nmod_poly_mul_KS4 res poly1 poly2

Sets res to the product of poly1 and poly2.

_nmod_poly_mullow_KS out in1 len1 in2 len2 bits n mod

Sets out to the low \(n\) coefficients of in1 of length len1 times in2 of length len2. The output must have space for n coefficients. We assume that len1 >= len2 > 0 and that 0 < n <= len1 + len2 - 1.

nmod_poly_mullow_KS res poly1 poly2 bits n

Set res to the low \(n\) coefficients of in1 of length len1 times in2 of length len2.

_nmod_poly_mul res poly1 len1 poly2 len2 mod

Sets res to the product of poly1 of length len1 and poly2 of length len2. Assumes len1 >= len2 > 0. No aliasing is permitted between the inputs and the output.

nmod_poly_mul res poly poly2

Sets res to the product of poly1 and poly2.

_nmod_poly_mullow res poly1 len1 poly2 len2 n mod

Sets res to the first n coefficients of the product of poly1 of length len1 and poly2 of length len2. It is assumed that 0 < n <= len1 + len2 - 1 and that len1 >= len2 > 0. No aliasing of inputs and output is permitted.

nmod_poly_mullow res poly1 poly2 trunc

Sets res to the first trunc coefficients of the product of poly1 and poly2.

_nmod_poly_mulhigh res poly1 len1 poly2 len2 n mod

Sets all but the low \(n\) coefficients of res to the corresponding coefficients of the product of poly1 of length len1 and poly2 of length len2, the other coefficients being arbitrary. It is assumed that len1 >= len2 > 0 and that 0 < n <= len1 + len2 - 1. Aliasing of inputs and output is not permitted.

nmod_poly_mulhigh res poly1 poly2 n

Sets all but the low \(n\) coefficients of res to the corresponding coefficients of the product of poly1 and poly2, the remaining coefficients being arbitrary.

_nmod_poly_mulmod res poly1 len1 poly2 len2 f lenf mod

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

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

Aliasing of f and res is not permitted.

nmod_poly_mulmod res poly1 poly2 f

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

_nmod_poly_mulmod_preinv res poly1 len1 poly2 len2 f lenf finv lenfinv mod

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

It is required that finv is the inverse of the reverse of f mod x^lenf. It is required that len1 + len2 - lenf > 0, which is equivalent to requiring that the result will actually be reduced. It is required that len1 < lenf and len2 < lenf. Otherwise, simply use _nmod_poly_mul instead.

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

nmod_poly_mulmod_preinv res poly1 poly2 f finv

Sets res to the remainder of the product of poly1 and poly2 upon polynomial division by f. finv is the inverse of the reverse of f. It is required that poly1 and poly2 are reduced modulo f.

_nmod_poly_pow_binexp res poly len e mod

Raises poly of length len to the power e and sets res to the result. We require that res has enough space for (len - 1)*e + 1 coefficients. Assumes that len > 0, e > 1. Aliasing is not permitted. Uses the binary exponentiation method.

nmod_poly_pow_binexp res poly e

Raises poly to the power e and sets res to the result. Uses the binary exponentiation method.

_nmod_poly_pow res poly len e mod

Raises poly of length len to the power e and sets res to the result. We require that res has enough space for (len - 1)*e + 1 coefficients. Assumes that len > 0, e > 1. Aliasing is not permitted.

nmod_poly_pow res poly e

Raises poly to the power e and sets res to the result.

_nmod_poly_pow_trunc_binexp res poly e trunc mod

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

nmod_poly_pow_trunc_binexp res poly e trunc

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

_nmod_poly_pow_trunc res poly e trunc mod

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

nmod_poly_pow_trunc res poly e trunc

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

_nmod_poly_powmod_ui_binexp res poly e f lenf mod

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

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

nmod_poly_powmod_ui_binexp res poly e f

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

_nmod_poly_powmod_mpz_binexp res poly e f lenf mod

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

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

nmod_poly_powmod_mpz_binexp res poly e f

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

_nmod_poly_powmod_fmpz_binexp res poly e f lenf mod

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

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

nmod_poly_powmod_fmpz_binexp res poly e f

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

_nmod_poly_powmod_ui_binexp_preinv res poly e f lenf finv lenfinv mod

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

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

nmod_poly_powmod_ui_binexp_preinv res poly e f finv

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

_nmod_poly_powmod_mpz_binexp_preinv res poly e f lenf finv lenfinv mod

Sets res to poly raised to the power e modulo f, using binary exponentiation. We require e > 0. We require finv to be the inverse of the reverse of f. We require lenf > 1. It is assumed that poly is already reduced modulo f and zero-padded as necessary to have length exactly lenf - 1. The output res must have room for lenf - 1 coefficients.

nmod_poly_powmod_mpz_binexp_preinv res poly e f finv

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

_nmod_poly_powmod_fmpz_binexp_preinv res poly e f lenf finv lenfinv mod

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

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

nmod_poly_powmod_fmpz_binexp_preinv res poly e f finv

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

_nmod_poly_powmod_x_ui_preinv res e f lenf finv lenfinv mod

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

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

nmod_poly_powmod_x_ui_preinv res e f finv

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

_nmod_poly_powmod_x_fmpz_preinv res e f lenf finv lenfinv mod

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

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

nmod_poly_powmod_x_fmpz_preinv res e f finv

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

_nmod_poly_powers_mod_preinv_naive res f flen n g glen ginv ginvlen mod

Compute f^0, f^1, ..., f^(n-1) mod g, where g has length glen and f is reduced mod g and has length flen (possibly zero spaced). Assumes res is an array of n arrays each with space for at least glen - 1 coefficients and that flen > 0. We require that ginv of length ginvlen is set to the power series inverse of the reverse of g.

nmod_poly_powers_mod_naive res f n g

Set the entries of the array res to f^0, f^1, ..., f^(n-1) mod g. No aliasing is permitted between the entries of res and either of the inputs.

_nmod_poly_powers_mod_preinv_threaded_pool res f flen n g glen ginv ginvlen mod threads num_threads

Compute f^0, f^1, ..., f^(n-1) mod g, where g has length glen and f is reduced mod g and has length flen (possibly zero spaced). Assumes res is an array of n arrays each with space for at least glen - 1 coefficients and that flen > 0. We require that ginv of length ginvlen is set to the power series inverse of the reverse of g.

_nmod_poly_powers_mod_preinv_threaded res f flen n g glen ginv ginvlen mod

Compute f^0, f^1, ..., f^(n-1) mod g, where g has length glen and f is reduced mod g and has length flen (possibly zero spaced). Assumes res is an array of n arrays each with space for at least glen - 1 coefficients and that flen > 0. We require that ginv of length ginvlen is set to the power series inverse of the reverse of g.

nmod_poly_powers_mod_bsgs res f n g

Set the entries of the array res to f^0, f^1, ..., f^(n-1) mod g. No aliasing is permitted between the entries of res and either of the inputs.

_nmod_poly_divrem_basecase Q R W A A_len B B_len mod

Finds \(Q\) and \(R\) such that \(A = B Q + R\) with \(\operatorname{len}(R) < \operatorname{len}(B)\). If \(\operatorname{len}(B) = 0\) an exception is raised. We require that W is temporary space of NMOD_DIVREM_BC_ITCH(A_len, B_len, mod) coefficients.

nmod_poly_divrem_basecase Q R A B

Finds \(Q\) and \(R\) such that \(A = B Q + R\) with \(\operatorname{len}(R) < \operatorname{len}(B)\). If \(\operatorname{len}(B) = 0\) an exception is raised.

_nmod_poly_divrem Q R A lenA B lenB mod

Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\operatorname{len}(R)\) less than lenB, where A is of length lenA and B is of length lenB. We require that Q have space for lenA - lenB + 1 coefficients.

nmod_poly_divrem Q R A B

Computes \(Q\) and \(R\) such that \(A = BQ + R\) with \(\operatorname{len}(R) < \operatorname{len}(B)\).

_nmod_poly_div Q A lenA B lenB mod

Notionally computes polynomials \(Q\) and \(R\) such that \(A = BQ + R\) with \(\operatorname{len}(R)\) less than lenB, where A is of length lenA and B is of length lenB, but returns only Q. We require that Q have space for lenA - lenB + 1 coefficients.

nmod_poly_div Q A B

Computes the quotient \(Q\) on polynomial division of \(A\) and \(B\).

_nmod_poly_rem R A lenA B lenB mod

Computes the remainder \(R\) on polynomial division of \(A\) by \(B\).

nmod_poly_rem R A B

Computes the remainder \(R\) on polynomial division of \(A\) by \(B\).

_nmod_poly_inv_series_basecase Qinv Q Qlen n mod

Given Q of length Qlen whose leading coefficient is invertible modulo the given modulus, finds a polynomial Qinv of length n such that the top n coefficients of the product Q * Qinv is \(x^{n - 1}\). Requires that n > 0. This function can be viewed as inverting a power series.

nmod_poly_inv_series_basecase Qinv Q n

Given Q of length at least n find Qinv of length n such that the top n coefficients of the product Q * Qinv is \(x^{n - 1}\). An exception is raised if n = 0 or if the length of Q is less than n. The leading coefficient of Q must be invertible modulo the modulus of Q. This function can be viewed as inverting a power series.

_nmod_poly_inv_series_newton Qinv Q Qlen n mod

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

nmod_poly_inv_series_newton Qinv Q n

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

_nmod_poly_inv_series Qinv Q Qlen n mod

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

nmod_poly_inv_series Qinv Q n

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

_nmod_poly_div_series_basecase Q A Alen B Blen n mod

Given polynomials A and B of length Alen and Blen, finds the polynomial Q of length n such that Q * B = A modulo \(x^n\). We assume n > 0 and that the constant coefficient of B is invertible modulo the given modulus. The polynomial Q must have space for n coefficients.

nmod_poly_div_series_basecase Q A B n

Given polynomials A and B considered modulo n, finds the polynomial Q of length at most n such that Q * B = A modulo \(x^n\). We assume n > 0 and that the constant coefficient of B is invertible modulo the modulus. An exception is raised if n == 0 or the constant coefficient of B is zero.

_nmod_poly_div_series Q A Alen B Blen n mod

Given polynomials A and B of length Alen and Blen, finds the polynomial Q of length n such that Q * B = A modulo \(x^n\). We assume n > 0 and that the constant coefficient of B is invertible modulo the given modulus. The polynomial Q must have space for n coefficients.

nmod_poly_div_series Q A B n

Given polynomials A and B considered modulo n, finds the polynomial Q of length at most n such that Q * B = A modulo \(x^n\). We assume n > 0 and that the constant coefficient of B is invertible modulo the modulus. An exception is raised if n == 0 or the constant coefficient of B is zero.

_nmod_poly_div_newton_n_preinv Q A lenA B lenB Binv lenBinv mod

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

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

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

nmod_poly_div_newton_n_preinv Q A B Binv

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

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

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

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