fq_default_poly.h

Initialise poly as the zero polynomial; fq_default_poly_init2 allocates space for alloc coefficients.

Change the allocation to alloc coefficients (truncating if needed), respectively ensure room for at least len coefficients.

Frees the memory used by poly.

Sets the length of poly to len without normalising, as _fq_poly_set_length; for internal use.

Truncate poly to length len, respectively set poly1 to poly2 truncated to length len.

Return the length, respectively the degree (-1 for zero).

Returns the number of nonzero coefficients.

Return whether the polynomials are equal, equal modulo x^n, respectively whether poly is the constant c.

Return whether the polynomial is 0, 1, x, respectively a nonzero constant.

Copy, respectively swap, polynomials.

Set the polynomial to 0, 1, x, respectively the constant c.

Set rop to the image of a polynomial over \mathbb{F}_p (whose modulus must be p), respectively over \mathbb{Z} (with coefficients reduced modulo p), in \mathbb{F}_q[x].

Sets rop to op divided by its leading coefficient (zero stays zero).

Sets res to the reversal of poly as a polynomial of length n, x^{n-1} f(1/x) for f = poly truncated to length n.

Return the largest k such that input is a polynomial in x^k, write f(x^k) as g(x), respectively compute f(x^k), as for fq_poly.

Sets x to the coefficient of x^n (zero beyond the length).

Set the coefficient of x^n to the element x, respectively to the image of the integer x in \mathbb{F}_p.

Random polynomials of length at most len (nonzero for the second function, which requires len > 0), random monic polynomials of length len, and random monic irreducible polynomials of length len, for testing.

Set rop to the sum, the difference, respectively the negation.

Sets rop to \mathit{op1} + c, with c mapped to \mathbb{F}_p.

Set rop to the sum, respectively difference, truncated to length n.

Set rop to x \cdot \mathit{op}, \mathit{op} / x (for x \ne 0), respectively add x \cdot \mathit{op} to or subtract it from rop.

Set rop to \mathit{op1} \cdot \mathit{op2}, respectively \mathit{op}^2; see Multiplying polynomials over finite fields for the algorithms over extension fields.

Sets rop to the product truncated to length n.

Sets rop to a polynomial whose coefficients of index at least start are those of the product \mathit{op1} \cdot \mathit{op2}; the lower coefficients are zero for the extension field representations and unspecified (zero or those of the product) for prime fields.

Sets res to \mathit{poly1} \cdot \mathit{poly2} \bmod f for f \ne 0.

Set the output to \mathit{op}^e, respectively \mathit{poly}^e \bmod x^{\mathit{trunc}}, with \mathit{op}^0 = 1.

Set res to \mathit{poly}^e \bmod f for e \ge 0 and f \ne 0, by binary exponentiation.

Set rop to x^n \cdot \mathit{op}, respectively \lfloor \mathit{op} / x^n \rfloor.

Sets rop to the formal derivative of op.

Compute the quotient Q and the remainder R of the division of A by B \ne 0, with A = BQ + R and \deg R < \deg B, respectively only the remainder. Q and R must be distinct.

Returns 1 and sets Q = A/B if B divides A, and returns 0 otherwise. B must be nonzero.

Removes the highest power of g (of degree at least 1) dividing f and returns its exponent.

Sets rop to the monic GCD of the two polynomials (zero if both are zero).

Computes the monic GCD G of A and B and cofactors with SA + TB = G, as fq_poly_xgcd. G, S and T must be distinct.

Set the output to 1/Q \bmod x^n, respectively A/B \bmod x^n, for a power series with nonzero constant term.

Set rop to \sqrt{\mathit{op}}, respectively 1/\sqrt{\mathit{op}}, modulo x^n, for a power series with constant term 1, in odd characteristic.

If op is the square of a polynomial, sets rop to a square root and returns 1; otherwise returns 0.

Sets res to f(a).

Sets rop to g(h(x)) for g = op1 and h = op2.

Sets res to f(g) \bmod h for f = poly1, g = poly2 and h = poly3 \ne 0 (Composition and modular composition).

Set p to the characteristic polynomial \det(xI - M), respectively the minimal polynomial, of a square matrix over the field (see fq_mat_charpoly and fq_mat_minpoly).

Print the polynomial, or return it as a newly allocated string, in the plain format of the representation.

Print the polynomial in the variable x, or return it as a newly allocated string, with coefficients in parentheses in the readable format of the field (for example x^2+(a+1)*x+(a)).