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.