nf_elem.h

Initialise $a$ to zero in nf, respectively clear it.

Swaps $a$ and $b$ in constant time.

Set $a$ to a random canonical element, respectively a random nonzero one, whose numerator coefficients and denominator have at most bits bits.

Removes the common content of numerator and denominator and makes the denominator positive (1 for zero). Does not reduce modulo $f$.

Reduces the numerator of $a$ modulo the defining polynomial, without canonicalising. Used after products with delayed reduction (nf_elem_mul_red with red $= 0$).

Reduces $a$ modulo the defining polynomial and canonicalises it.

Returns whether $a$ is invertible modulo the defining polynomial, that is, whether $\gcd(a, f) = 1$ in $\mathbf{Q}[x]$. This matters only when $f$ is reducible, which is not excluded by nf_init; the function is meant for test code.

Set $a$ to 0, respectively 1.

Sets $a$ to the generator $\theta$, the class of $x$. In a field of degree 1 this is the root $-f_0/f_1$ of $f = f_1 x + f_0$.

Sets $a$ to $b$.

Set $a$ to the rational number $c$.

Sets $a$ to the image of the canonical polynomial pol in $K$, reducing it modulo $f$ if its degree is at least $d$.

Sets pol to the polynomial in $x$ representing the reduced element $a$.

Sets $b$ to the element whose numerator coefficients are the entries of row $i$ of $M$ (column 0 holding the constant coefficient) and whose denominator is den, and canonicalises it.

Sets row $i$ of $M$, which must have $d$ columns, to the numerator coefficients of $b$ (column 0 holding the constant coefficient) and den to its denominator.

Sets pol to the numerator of $a$ reduced modulo the modulus of pol, ignoring the denominator.

Set pol to the reduction of the numerator of $a$ modulo the modulus $n$ of pol; if den is nonzero (always for nf_elem_get_nmod_poly), multiply it by the inverse of the denominator modulo $n$, which must exist.

Versions of the three functions above for a multiword modulus given by ctx.

Get and set the denominator of $b$. nf_elem_set_den requires $d > 0$ and does not canonicalise.

Returns whether the denominator of $a$ is 1, that is, whether the canonical $a$ lies in $\mathbb{Z}[\theta]$.

Sets $a$ to the coefficient of $\theta^i$ in $b$, a rational number.

Sets $a$ to the coefficient of $\theta^i$ in the numerator of $b$, ignoring the denominator.

Sets the coefficient of $\theta^i$ in the numerator of $a$ to $b$, keeping the denominator, and canonicalises. Allows $i$ up to $2(d - 1)$, so that the result may be unreduced; throws for larger $i$.

Returns whether $a = b$ for reduced but not necessarily canonical $a$ and $b$, by cross-multiplication, with a cheap test of the bit sizes first.

Returns whether $a = b$ for canonical $a$ and $b$, by comparing the representations.

Return whether the canonical element $a$ equals the rational number $b$.

Return whether $a$ is 0, respectively 1.

Returns whether $a$ equals the generator $\theta$. In a field of degree 1 with defining polynomial $f = f_1 x + f_0$, the generator is the rational number $-f_0/f_1$.

Return whether the canonical element $a$ lies in $\mathbb{Z}$, respectively in $\mathbf{Q}$.

Prints $a$ to stdout as a polynomial in the variable var, a nonempty string.

Returns the string printed by nf_elem_print_pretty, allocated with flint_malloc.

Sets $a$ to $-b$.

Set $a$ to $b + c$, respectively $b - c$, without canonicalising.

Set $a$ to $b + c$, respectively $b - c$.

Set $a$ to $b + c$, $b - c$, respectively $c - b$, for a rational number $c$.

Set $a$ to $cb$.

Set $a$ to $b/c$ for $c \ne 0$.

Sets $a$ to $\theta b$, by a shift of the coefficients followed by one reduction step.

Set $a$ to $bc$ without canonicalising, reducing modulo $f$ only if red is nonzero (always for _nf_elem_mul). The inputs must be reduced, and $a$ must not be aliased with $b$ or $c$.

Set $a$ to $bc$, canonicalised. With red $= 0$ the product is not reduced modulo $f$, which allows sums of products to be reduced once with nf_elem_reduce. The inputs must be reduced.

Set $a$ to $b^{-1}$ for $b \ne 0$, by the extended Euclidean algorithm for $b$ and $f$ over $\mathbf{Q}$. _nf_elem_inv does not allow aliasing. The result is undefined for $b = 0$.

Set $a$ to $b/c$ for $c \ne 0$, as $b \cdot c^{-1}$. _nf_elem_div does not canonicalise and does not allow $a$ to be aliased with $b$.

Sets res to $a^e$ by left-to-right binary exponentiation [Knu1997, §4.6.3], for $a \ne 0$ and $e \ge 2$. Does not allow aliasing.

Sets res to $a^e$, with $a^0 = 1$ for all $a$ including zero.

Set the rational number rnum/rden, respectively res, to the absolute norm $N_{K/\mathbf{Q}}(a)$, the product of the conjugates of $a$. It is computed as $\operatorname{Res}(f, a)$ divided by the appropriate power of the leading coefficient of $f$; the resultant of the primitive parts is computed by _fmpz_poly_resultant, which uses the multimodular algorithm for large inputs and a pseudo-remainder (subresultant-type) Euclidean algorithm otherwise (Norm).

Set the result to $N_{K/\mathbf{Q}}(a)/\mathtt{divisor}$, assuming that the quotient of the resultant by divisor is an integer of at most nbits bits; the multimodular resultant (_fmpz_poly_resultant_modular_div) then needs only enough primes for the quotient. For divisor $= 0$ the result is 0.

Set the result to the absolute trace $\operatorname{Tr}_{K/\mathbf{Q}}(a)$, computed as $\sum_i a_i S_i$ from the coefficients $a_i$ of $a$ and the power sums $S_i$ of the roots of $f$ stored in the nf_t.

Sets the $d \times d$ matrix res to the matrix of multiplication by $a$ with respect to the basis $1, \theta, \ldots, \theta^{d-1}$, in the row convention: row $j$ holds the coordinates of $\theta^j a$.

Sets res and den so that res/den is the matrix of nf_elem_rep_mat, with res primitive, that is, with content 1.

Sets res to the integral element whose coefficients are those of the numerator of $a$ reduced modulo $m$ = mod, ignoring the denominator, in $[0, m)$ if sign is zero and in the symmetric range otherwise.

If den is zero, set res to the integral element with the coefficients of $qa$ reduced modulo $m$. If den is nonzero, set res to $z/q$, where $z$ is the numerator of $a$ reduced modulo $mq$, so that $a - \mathtt{res}$ is integral with coefficients divisible by $m$. The mod versions use the residues in $[0, m)$ (or $[0, mq)$), the smod versions the symmetric residues.

The case den $= 1$ of the functions above.

Set res to an element congruent to $a$ modulo $m$ whose denominator divides $m^\infty$: writing $q = q_1 q_2$ with $q_1$ composed of the primes dividing $m$ and $q_2$ coprime to $m$, the numerator of $a$ is multiplied by $q_2^{-1}$ modulo $m q_1$, reduced into $[0, m q_1)$ (or the symmetric range for the signed version) and divided by $q_1$. Then $a - \mathtt{res}$ has denominator coprime to $m$ and numerator coefficients divisible by $m$.

Addition and subtraction in a field of degree 1, canonicalising the result if can is nonzero.

Addition and subtraction in a field of degree 2, on all three numerator coefficients (so that unreduced elements can be added), canonicalising the result if can is nonzero (always for the versions without underscore). The underscore versions do not allow $a$ to be aliased with $c$.