Arithmetic in number fields

A number field $K = \mathbf{Q}(\theta)$ of degree $d$ is represented as $\mathbf{Q}[x]/(f)$ for the minimal polynomial $f \in \mathbf{Q}[x]$ of $\theta$, and its elements as polynomials of degree less than $d$. The modules nf and nf_elem originate in the ANTIC library [Har2015]; the standard reference for the mathematics and the general algorithms is [Coh1996, Ch. 4].

Representation#

An element $\alpha = (a_0 + a_1\theta + \cdots + a_{d-1}\theta^{d-1})/q$ is stored as an integer numerator polynomial and one positive denominator $q$, in lowest terms (an fmpq_poly_t). A single denominator keeps additions and multiplications in $\mathbb{Z}[x]$, where FLINT's fast polynomial arithmetic applies, at the cost of a content computation for canonicalisation.

Small degrees get special representations, selected by nf_init:

• for $d = 1$ the element is a rational number, a numerator and a denominator (lnf_elem_t);
• for $d = 2$ the numerator is a fixed array of three integers (qnf_elem_t), so that no memory management is needed and a product $(a_0 + a_1\theta)(b_0 + b_1\theta)$ can be stored before reduction;
• for $f = x^2 + 1$ ($K = \mathbf{Q}(i)$) a dedicated multiplication is used.

Multiplication and reduction#

To multiply $\alpha = A(\theta)/q$ and $\beta = B(\theta)/r$, nf_elem_mul computes $C = AB \in \mathbb{Z}[x]$ of degree at most $2d - 2$ with _fmpz_poly_mul, the denominator $qr$, and then reduces $C$ modulo $f$ and removes the common content of numerator and denominator.

For $3 \le d < 30$ the reduction uses the precomputed remainders $P_k = x^k \bmod f$ for $d \le k \le 2d - 2$, stored in the nf_t.

The algorithm is correct since $C \equiv \sum_{k < d} c_k x^k + \sum_{k \ge d} c_k P_k \pmod f$. It costs $(d - 1)^2$ multiplications of coefficients, like division with remainder, but has no dependency between the steps: the remainders do not depend on $C$. If $f$ is monic with integer coefficients, the $P_k$ are integral and the reduction stays in $\mathbb{Z}[x]$ (_fmpz_poly_rem_powers_precomp); otherwise the $P_k$ have denominators that are powers of the leading coefficient of $f$ and the rational version _fmpq_poly_rem_powers_precomp is used. For $d \ge 30$ the product is reduced by division with remainder, _fmpz_poly_divrem for monic integral $f$ and _fmpq_poly_rem with a precomputed inverse of the leading coefficient otherwise.

For $d = 2$, a single step suffices: with $f = f_2x^2 + f_1x + f_0$, $c_2\theta^2 = -c_2(f_1\theta + f_0)/f_2$, and for monic $f$ this is two multiply-subtracts. For $\mathbf{Q}(i)$ the product $(a + bi)(c + di) = (ac - bd) + (ad + bc)i$ is formed with two fused multiply-add operations (fmpz_fmms, fmpz_fmma), and the denominator is reduced by a three-term GCD.

nf_elem_mul_red with red $= 0$ skips the reduction, so that a sum $\sum_j \alpha_j\beta_j$ can be accumulated in unreduced form and reduced once at the end, which saves $d - 1$ reductions per term.

Inversion and division#

Since $f$ is irreducible, any nonzero $A$ of degree less than $d$ is coprime to $f$, and the extended Euclidean algorithm gives $S, T \in \mathbf{Q}[x]$ with $SA + Tf = 1$, so $A(\theta)^{-1} = S(\theta)$. nf_elem_inv uses fmpq_poly_xgcd (and _fmpq_poly_xgcd for $d = 2$), which takes out contents and denominators and calls the multimodular _fmpz_poly_xgcd_modular; for coprime integer polynomials that function returns the resultant $r$ and integer cofactors with $sA + tf = r$ (GCDs of polynomials over Z). For $d = 1$ the inverse is the reciprocal of a rational number. Division is multiplication by the inverse. If $f$ is reducible, which nf_init does not exclude, an element sharing a factor with $f$ has no inverse.

Norm#

_nf_elem_norm computes the resultant of the integer numerator of $f$ and the numerator of $\alpha$ with _fmpq_poly_resultant, which takes out the contents and denominators and calls _fmpz_poly_resultant (multimodular for large inputs), and divides by $c^m$ for the leading coefficient $c$ of the numerator of $f$; the denominator of $f$ does not change the roots. _nf_elem_norm_div divides the resultant by a known factor during the multimodular computation, so that only enough primes for the quotient (with a given bound on its bit size) are needed; this is useful when the norm is known to be divisible by a large number, as in ideal arithmetic.

Trace#

The trace of $\alpha = \sum_k a_k\theta^k / q$ is $\sum_k a_k S_k / q$, where $S_k = \sum_j \theta_j^k$ are the power sums of the roots of $f$. nf_init computes $S_0 = d, S_1, \ldots, S_{d-1}$ once, by Newton's identities

for $f = \sum_k c_k x^k$ [Coh1996, p. 163]. Since $S_k$ has denominator dividing $c_d^k$, the values are stored with the common denominator $c_d^{d-1}$. A trace then costs $d$ multiplications.

Representation matrices and modular reduction#

The matrix of multiplication by $\alpha$ in the basis $1, \theta, \ldots, \theta^{d-1}$ has as row $j$ the coordinates of $\theta^j\alpha$; nf_elem_rep_mat computes the rows with nf_elem_mul_gen, one shift and one reduction step each. Its characteristic polynomial is the characteristic polynomial of $\alpha$, whose constant term and second coefficient give the norm and trace again.

The functions nf_elem_mod_fmpz, nf_elem_smod_fmpz and nf_elem_coprime_den replace an element by one congruent to it modulo an integer $m$ with reduced coefficients, as needed in multimodular and $p$-adic algorithms over $K$. For nf_elem_coprime_den, write the denominator as $q = q_1q_2$ where $q_1$ contains exactly the primes dividing $m$; then $q_2$ is invertible modulo $mq_1$, and replacing the numerator $A$ by $A q_2^{-1} \bmod mq_1$ and the denominator by $q_1$ changes $\alpha$ by an element whose denominator divides $q_2$ and whose numerator is divisible by $m$.

Use in FLINT#

• Representation and precomputation: nf_init, nf_elem_init, nf_elem_canonicalise.
• Multiplication and reduction: nf_elem_mul, nf_elem_mul_red, _nf_elem_mul_red, nf_elem_reduce, _nf_elem_reduce, nf_elem_mul_gen, nf_elem_pow.
• Inverse and division: nf_elem_inv, nf_elem_div.
• Norm and trace: nf_elem_norm, nf_elem_norm_div, nf_elem_trace.
• Matrices and modular reduction: nf_elem_rep_mat, nf_elem_rep_mat_fmpz_mat_den, nf_elem_mod_fmpz, nf_elem_smod_fmpz, nf_elem_coprime_den.
• The generic ring gr_ctx_init_nf uses these functions; qqbar and ca use nf_elem for elements of number fields.