fq.h

Initialises ctx as a context for \mathbb{F}_{p^d}, d \ge 1, with the generator printed as var, a nonempty null-terminated string. The defining polynomial is the Conway polynomial for (p, d) if it is in FLINT's table, and otherwise a random sparse irreducible polynomial (a trinomial or pentanomial if one is found). p must be prime; this is not checked.

Initialise ctx as a context for \mathbb{F}_{p^d} defined by the Conway polynomial for (p, d). The functions without an underscore throw FLINT_ERROR if the polynomial is not in FLINT's table. The functions with an underscore return 1 on success and 0, leaving ctx uninitialised, if the polynomial is not in the table.

Initialises ctx as a context for \mathbb{F}_p[x]/(f), where f is modulus, an irreducible polynomial of degree d \ge 1 over \mathbb{F}_p, and p is the modulus of ctxp. f need not be monic. The polynomial and ctxp are copied. Irreducibility is not checked.

Initialises ctx as a random field for testing: it creates a random fq_nmod context with fq_nmod_ctx_init_randtest and copies it, so the prime fits in a word and the defining polynomial is a Conway polynomial, possibly multiplied by a random constant (to test non-monic moduli). The type selects the ranges as in _nmod_poly_conway_rand: primes of up to 17 bits for type 0 and 1, of up to 10 bits for 2 and 3, and degrees below 15 for odd type.

Initialises ctx with a random monic modulus that is usually reducible, for testing the functions that also work over \mathbb{F}_p[x]/(f) for reducible f. For type 0 the prime has up to 30 bits and the degree is at most 30, for 1 up to 30 bits and degree 15, for 2 up to 10 bits and degree 30, for 3 up to 10 bits and degree 15.

Frees the memory used by ctx.

Returns a pointer to the defining polynomial f, an fmpz_mod_poly over the context ctx->ctxp.

Returns the degree d = [\mathbb{F}_q : \mathbb{F}_p].

Returns a pointer to the characteristic p.

Sets f to the number of elements q = p^d.

Print p, d and the defining polynomial in the variable X to file, respectively stdout, on three lines. fq_ctx_fprint returns a positive value on success.

Initialise rop and set it to zero. fq_init2 also allocates space for d coefficients.

Frees the memory used by rop.

Sets rop to op.

Swaps op1 and op2 efficiently.

Set rop to 0, respectively 1.

Sets rop to the generator of the field, the class of x, a root of the defining polynomial. For d = 1 this is the root -c_0/c_1 of f = c_1 x + c_0. The generator generates the multiplicative group if and only if f is primitive, which holds for Conway polynomials.

Set rop to the image of the integer x in \mathbb{F}_p \subseteq \mathbb{F}_q.

If b lies in \mathbb{F}_p, sets a to its representative in [0, p) and returns 1; otherwise returns 0 and leaves a unchanged.

Set a to the representative of b of degree less than d, as an integer polynomial with coefficients in [0, p), respectively as a polynomial over \mathbb{F}_p (the fmpz_mod_poly must have been initialised with modulus p).

Set a to the class of the polynomial b in \mathbb{F}_p[x]/(f), reducing the coefficients modulo p and the polynomial modulo f. b may have any length.

Convert between a and the column vector of its coefficients (a_0, \ldots, a_{d-1})^T with respect to the basis 1, x, \ldots, x^{d-1}. col must be a d \times 1 matrix over \mathbb{F}_p with reduced entries.

Returns whether op1 and op2 are equal.

Return whether op is 0, respectively 1.

Returns whether op is invertible, that is, nonzero.

Returns whether op is invertible modulo the defining polynomial, using fq_gcdinv. If it is not, f is set to a nontrivial factor of the modulus (the monic GCD of the representative of op and the modulus); this can only happen if the modulus is reducible. Otherwise f is set to one. If op is zero, the function returns 0 and sets f to zero.

Set rop to \mathit{op1} + \mathit{op2}, respectively \mathit{op1} - \mathit{op2}.

Sets rop to \mathit{op1} - 1.

Sets rop to -\mathit{op1}.

Set rop to \mathit{op1} \cdot \mathit{op2}, respectively \mathit{op}^2. The product of the representatives is computed with fmpz_poly_mul (or fmpz_poly_sqr) and reduced with fq_reduce.

Set rop to op times the image of the integer x in \mathbb{F}_p.

Sets rop to \mathit{op1}^{-1}, computed with the extended Euclidean algorithm in \mathbb{F}_p[x]. Throws FLINT_ERROR if op1 is zero.

Computes the monic GCD g of the representative of op and the defining polynomial f, and sets rop to g and inv to an s with s \cdot \mathit{op} \equiv g \pmod f. In a field g = 1 for nonzero op, and inv is the inverse; a nontrivial g is a factor of a reducible modulus. If op is zero, rop is set to zero and inv is not changed.

Sets rop to \mathit{op1} / \mathit{op2}, computed as \mathit{op1} \cdot \mathit{op2}^{-1}. Throws FLINT_ERROR if op2 is zero.

Set rop to \mathit{op}^e for e \ge 0, with \mathit{op}^0 = 1 for every op. fq_pow throws FLINT_ERROR if e < 0. If e \ge p, the exponent is first reduced modulo q - 1.

Sets (rop, 2d - 1) to (op, len) raised to the power e \ge 0, reduced modulo f: the first d coefficients hold the reduced result and the others are zero. Requires 1 \le \mathit{len} \le d and space for 2d - 1 coefficients in rop. Does not allow aliasing. For e = 0 the result is 1.

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

Returns whether op is a square, by Euler's criterion \mathit{op}^{(q-1)/2} = 1. If p = 2, every element is a square.

Sets rop to the unique p-th root of op1, which is \mathit{op1}^{p^{d-1}}, computed by d - 1 successive p-th powers.

Sets rop to \sigma^e(\mathit{op}) = \mathit{op}^{p^e}. Any e is allowed, including negative values; it is reduced modulo d. The power is computed by binary exponentiation, at the cost of about e \log_2 p squarings for the reduced e.

Sets (rop, 2d - 1) to the image of (op, len) under \sigma^e, with the reduced result in the first d coefficients. Requires 1 \le \mathit{len} \le d, 1 \le e < d, space for 2d - 1 coefficients in rop, and no aliasing.

Set rop to the norm of op, respectively of the nonzero element (op, len) with 1 \le \mathit{len} \le d, as an integer in [0, p). The norm of an element with representative a(x) is computed as the resultant \operatorname{Res}(f, a) / \operatorname{lc}(f)^{\deg a}, or as a_0^d for an element of \mathbb{F}_p.

Set rop to the trace of op, respectively of the nonzero element (op, len) with 1 \le \mathit{len} \le d, as an integer in [0, p). The traces \operatorname{Tr}(x^i) of the basis elements are computed from the coefficients of f by Newton's identities, and the trace of a = \sum a_i x^i is \sum a_i \operatorname{Tr}(x^i).

Computes the order of op in the multiplicative group, which divides q - 1, and stores it in ord unless ord is NULL. Returns 0 if op is zero (and sets the order to 0), 1 if op is a primitive element (its order is q - 1), and -1 otherwise.

Returns whether op generates the multiplicative group \mathbb{F}_q^\times, using fq_multiplicative_order.

Set rop to a uniformly random element, respectively a uniformly random nonzero element.

Set rop to a random element, respectively a random nonzero element, for testing: with probability 1/2 the coefficients are uniform, otherwise most of them are zero.

Sets rop to a random element whose representative has degree exactly d - 1 and leading coefficient 1, for testing.

Print the representative of op to file, respectively stdout, in the format of fmpz_poly_print: the length, two spaces, and the coefficients from the constant term up, separated by spaces. fq_fprint returns a positive value on success.

Print the representative of op as a polynomial in the variable name of the context, such as 3*a^2+1, to file, respectively stdout. Return a positive value on success.

Return the plain, respectively readable, representation of op as a newly allocated string, which the caller must free with flint_free.

Sets f to \sum_i a_i 2^{i \cdot \mathit{bit\_size}}, where the a_i are the coefficients of op. Each coefficient must fit in bit_size bits, that is, p \le 2^{\mathit{bit\_size}}.

Sets rop to the class of the polynomial whose coefficients are the consecutive bit_size-bit fields of the nonnegative integer f, reducing the coefficients modulo p and the polynomial modulo f. This is the inverse of fq_bit_pack and recovers a product from the packed product of two packed operands if the fields are wide enough.

Reduces the integer polynomial rop, with arbitrary integer coefficients, modulo p and modulo the defining polynomial, in place, so that it becomes a valid element. The length of rop must be at most 2d unless the defining polynomial is sparse (see below); products of two elements satisfy this.

Reduce the polynomial (R, lenR), with arbitrary integer coefficients and \mathit{lenR} \le 2d (any length for _fq_sparse_reduce), modulo p and modulo the defining polynomial f in place: the first \min(\mathit{lenR}, d) coefficients receive the reduced value (and are not normalised). _fq_sparse_reduce eliminates the coefficients of degree at least d from the top, using the nonzero terms of the monic version of f, and reduces modulo p at the end; it costs about (\mathit{lenR} - d) \cdot t multiplications for f with t nonzero terms. _fq_dense_reduce reduces modulo p and then divides by f with the precomputed inverse (Newton division, _fmpz_mod_poly_divrem_newton_n_preinv). _fq_reduce calls the first if f has at most five nonzero terms and the second otherwise.

Sets p to the characteristic. Equivalent to fmpz_set(p, fq_ctx_prime(ctx)); kept for compatibility.