fq_zech.h

Initialises ctx as a Zech context for \mathbb{F}_{p^d}, with the generator printed as var, defined by the Conway polynomial if it is in FLINT's table and by a random primitive polynomial otherwise. Requires p^d < 2^{\mathtt{FLINT\_BITS}} (otherwise FLINT_ERROR is thrown); the tables need 2q + p words.

Initialise ctx with the Conway polynomial for (p, d), which is primitive. The first function throws FLINT_ERROR if the polynomial is not in FLINT's table; the second returns 0 in that case and 1 on success.

Initialises ctx with a random monic primitive polynomial of degree d (from nmod_poly_randtest_monic_primitive, with an internal random state).

Initialise ctx with the given defining polynomial, which must be primitive; it is copied into a new fq_nmod context owned by ctx. While the tables are built, primitivity is checked: the powers g^0, \ldots, g^{q-2} must be distinct. fq_zech_ctx_init_modulus throws FLINT_ERROR for a non-primitive polynomial; fq_zech_ctx_init_modulus_check returns 1 on success and 0 if the polynomial is not primitive. After a return value of 0, all memory has already been freed: ctx must not be used, and need not be cleared (clearing it is allowed and has no effect). fq_default_ctx_init_modulus_nmod falls back to fq_nmod for a non-primitive modulus.

Initialise ctx as the Zech representation of the field of the fq_nmod context ctxn, which is referenced, not copied: it must stay alive while ctx is used and is not cleared with ctx. The defining polynomial must be primitive; fq_zech_ctx_init_fq_nmod_ctx throws FLINT_ERROR otherwise, and the _check version returns 0 instead of 1 (after which the memory allocated for ctx has been freed: ctx must not be used, clearing it is allowed and has no effect, and ctxn remains owned by the caller).

Deprecated versions of the _ui functions, taking the prime as an fmpz_t that must fit in a word.

Initialise ctx as a random field for testing, with a random primitive modulus: primes of up to 5 bits for type 0 and 1, of up to 4 bits for 2 and 3, and degree at most 4 for even and 3 for odd type. The reducible version is the same, since a Zech context needs an irreducible (indeed primitive) modulus.

Frees the tables, and the fq_nmod context if ctx owns it.

Return the defining polynomial, the degree d and the characteristic p.

Return, respectively set f to, the number of elements q. fq_zech_ctx_order is deprecated.

Print Zech Representation: followed by the description of the underlying fq_nmod context to file, respectively stdout.

fq_zech_init and fq_zech_init2 set rop to zero; fq_zech_clear does nothing.

Subtracts q from the value of rop if it is at least q. Values in [0, q - 1] are valid elements and are not changed.

Copy, swap, and set to 0 (logarithm q - 1), 1 (logarithm 0) or the generator (logarithm 1).

Set rop to the image of the integer x in \mathbb{F}_p, using the table of logarithms of the prime field.

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

Convert between the Zech representation and the polynomial representation of the underlying fq_nmod context ctx->fq_nmod_ctx. fq_zech_get_fq_nmod reads the coefficients from eval_table; fq_zech_set_fq_nmod sums c_i g^i with d table lookups.

Convert between an element and its representative in \mathbb{F}_p[x]. fq_zech_get_nmod_poly also sets the modulus of a to p. fq_zech_set_nmod_poly accepts a polynomial of any length, using g^{q-1} = 1 to reduce exponents.

Convert between a and the d \times 1 column vector of the coefficients of its polynomial representative.

Return whether the logarithms are equal, whether op is 0, respectively 1.

Return whether op is nonzero. The second version sets rop to one if it is (a Zech context always describes a field).

Set rop to \mathit{op1} \pm \mathit{op2}, with one lookup in the Zech table: g^i + g^j = g^{j + Z(i - j)}, and g^i - g^j = g^i + g^{j + (q-1)/2} for odd p.

Set rop to \mathit{op1} - 1, respectively -\mathit{op1} (adding (q - 1)/2 to the logarithm, or nothing if p = 2).

Set rop to \mathit{op1} \cdot \mathit{op2}, respectively \mathit{op}^2, by adding logarithms modulo q - 1.

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

Set rop to \mathit{op1}^{-1} (logarithm q - 1 - k), respectively \mathit{op1} / \mathit{op2}. Throw FLINT_ERROR on division by zero.

For nonzero op, sets rop to one and inv to the inverse; for zero op, sets rop to zero.

Set rop to \mathit{op1}^e for e \ge 0 (with \mathit{op1}^0 = 1), by multiplying the logarithm by e modulo q - 1. fq_zech_pow throws FLINT_ERROR for e < 0.

For odd p, an element is a square if and only if its logarithm is even, and then half of it is the logarithm of a square root. For p = 2 every element is a square, with square root of logarithm k/2 or (k + q - 1)/2. fq_zech_sqrt returns 1 and sets rop to a square root if op1 is a square, and returns 0 otherwise.

Sets rop to the p-th root of op1, by multiplying the logarithm by p^{d-1} modulo q - 1.

Sets rop to \mathit{op}^{p^e} (any e, taken modulo d), by multiplying the logarithm by p^e \bmod (q - 1).

Sets rop to the norm of \mathit{op} = g^k, which is N(g)^k, where N(g) = (-1)^d f(0) for the monic defining polynomial f is stored in the context (prime_root); one modular exponentiation in \mathbb{F}_p.

Sets rop to the trace of op, computed as the sum of the d conjugates \mathit{op}^{p^i} with Zech additions, and converted from a logarithm l = m (q - 1)/(p - 1) in the prime field to the integer N(g)^m \bmod p.

Multiplicative order (returning 0 for zero, 1 for a primitive element and -1 otherwise) and primitivity test, as fq_multiplicative_order and fq_is_primitive; the order of g^k is (q - 1)/\gcd(k, q - 1), but the generic algorithm, which factors q - 1, is used.

Set rop to a uniformly random element, respectively nonzero element; the randtest versions use a different random generator.

Print, respectively return as a newly allocated string, the logarithm of op as a decimal integer (q - 1 for zero).

Print, respectively return as a newly allocated string, op as a power of the generator, such as a^17, and zero as 0.

Pack the coefficients of the polynomial representative of op into bit_size-bit fields of an integer, and unpack and convert back, via the fq_nmod representation, as fq_bit_pack and fq_bit_unpack.