dirichlet.h

Initialises $G$ as the group of characters modulo $q \ge 1$, computing the factorisation of $q$, the Conrey generators and the exponent. No discrete logarithm tables are computed, so this is cheap even for large $q$. Returns 1 on success, and 0 (without allocating) if a prime factor of $q$ exceeds $10^{16}$, for which the generator is not implemented.

Initialises $H$ as the group modulo $h$, for $h \mid q$, sharing the components of $G$ (in particular its discrete logarithm tables, which must not be cleared while $H$ is in use).

Frees the memory used by $G$, but not its discrete logarithm tables, which may be shared with subgroups; free them first with dirichlet_group_dlog_clear.

Returns the number $\varphi(q)$ of elements of $G$, which is also the number of characters modulo $q$.

Returns the number of primitive characters modulo $q$: 0 if $q \equiv 2 \pmod 4$, and otherwise the product over the components of $p - 2$ for $p^1 \| q$ ($p$ odd), $(p-1)^2 p^{e-2}$ for $p^e \| q$ ($e \ge 2$), 1 for $4 \| q$ and $2^{e-2}$ for $2^e \| q$, $e \ge 3$.

Precomputes discrete logarithm tables in every component for about num subsequent logarithms, with dlog_precomp_modpe_init. This speeds up dirichlet_char_log, dirichlet_chi and dirichlet_pairing when they are called many times. For very large num the whole group may be tabulated.

Frees the discrete logarithm tables of $G$. Subgroups sharing them must be cleared first.

Initialises $x$ as an element of $G$ and sets it to the principal character ($m = 1$).

Frees the memory used by $x$.

Prints the log of $x$ as a list [a_0, a_1, ...].

Sets $x$ to a copy of $y$.

Return 1 if $x$ and $y$ are equal, otherwise 0. The first function compares the numbers only; the second also compares the logs and is meant for testing the consistency of the two representations.

Sets $x$ to the character of number $m$, which must be coprime to $q$ and reduced modulo $q$, computing its log by discrete logarithms in each component (with the tables of $G$ if present).

Return the number of $x$. The first function reads the stored number; the second recomputes it from the log, stores it in $x$ and returns it.

Sets $x$ to the principal character, with log $[0, \ldots, 0]$ and number 1.

Sets $x$ to the first primitive character in the order of dirichlet_char_next_primitive, with log $[1, \ldots, 1]$, or $[0, 1, \ldots, 1]$ if $8 \mid q$. Throws if $q \equiv 2 \pmod 4$, where no primitive character exists.

Sets $x$ to the next element of $G$ in the lexicographic order of the logs (the last component varying fastest), updating the number with one multiplication. Returns the index of the most significant component that changed, or $-1$ after the last element (when $x$ wraps around to the principal character).

As dirichlet_char_next, but skips to the next primitive character, in the same order. Start from dirichlet_char_first_primitive.

Convert between an element and its index $j \in [0, \varphi(q))$ in the lexicographic order of the logs, the mixed-radix number with digits $\mathit{log}[k]$ in base $\varphi_k$.

Returns 1 if $\chi$ is the principal character ($m = 1$).

Return the conductor of $\chi_q(a, \cdot)$, the smallest $f \mid q$ such that the character is induced by a character modulo $f$.

Return the parity $\lambda \in \{0, 1\}$ of $\chi_q(a, \cdot)$, defined by $\chi(-1) = (-1)^\lambda$: 0 for even and 1 for odd characters.

Return the order of $\chi_q(a, \cdot)$ in the character group, which is the multiplicative order of $a$ modulo $q$.

Returns 1 if $\chi$ is real, that is, has order at most 2 (its number satisfies $m^2 \equiv 1 \pmod q$).

Returns 1 if $\chi$ is primitive, that is, its conductor is $q$.

Return the exponent of $\chi_q(m, n)$ modulo G->expo, or DIRICHLET_CHI_NULL if $m$ or $n$ is not coprime to $q$. The pairing is symmetric: $\chi_q(m, n) = \chi_q(n, m)$. The _char version takes both arguments as elements with their logs and needs no discrete logarithm; the other computes two.

Returns the exponent of $\chi(n)$ modulo G->expo, or DIRICHLET_CHI_NULL if $\gcd(n, q) > 1$. Costs one discrete logarithm per component of $G$.

Set $v[k]$ to the exponent of $\chi(k)$ for $0 \le k < \mathit{nv}$, modulo G->expo or modulo order, which must be a multiple of the order of $\chi$; entries with $\gcd(k, q) > 1$ are set to DIRICHLET_CHI_NULL. The functions call the loop versions if $2\,\mathit{nv} > \varphi(q)$ and the primeloop versions otherwise. $v[0]$ is DIRICHLET_CHI_NULL for $q > 1$, and for $q = 1$, where the trivial character is 1 everywhere, every entry is 0.

As dirichlet_chi_vec, by enumerating the whole group with dirichlet_char_next and updating the value by one addition per step; entries $k \ge q$ are copied by periodicity. Costs $O(\varphi(q) + \mathit{nv})$ and needs no discrete logarithm. Requires $\mathit{nv} \ge 2$: the function writes $v[1]$.

As dirichlet_chi_vec, by adding the contributions of the components: the 2-part directly, and each odd prime power with dlog_vec_add, which computes the discrete logarithms of all $k < \mathit{nv}$ by sieving (using the tables of $G$ if present). See the warning about $v[0]$ at dirichlet_chi_vec.

Sets $v[k]$ to DIRICHLET_CHI_NULL for $0 < k < \mathit{nv}$ divisible by a prime factor of $q$ (except $v[0]$, which is not changed).

Sets $c$ to the product $ab$: the logs are added and the numbers multiplied.

Sets $c$ to $a^n$.

Given a character $\chi_H$ modulo $h \mid q$ (with $H$ a subgroup of $G$ created by dirichlet_subgroup_init), sets $\chi_G$ to the character modulo $q$ that it induces. Throws if $h \nmid q$.

Given a character $\chi_G$ modulo $q$ whose conductor divides $h$, with $h \mid q$ the modulus of $H$, sets $\chi_H$ to the character modulo $h$ that induces it. Throws if $h \nmid q$ or the conductor does not divide $h$.