Use DirichletGroup in f.

Apply f to new DirichletGroup.

dirichlet_group_init G q

Initializes G to the group of Dirichlet characters mod q.

This method computes a canonical decomposition of G in terms of cyclic groups, which are the mod \(p^e\) subgroups for \(p^e\|q\), plus the specific generator described by Conrey for each subgroup.

In particular G contains:

• the number num of components
• the generators
• the exponent expo of the group

It does not automatically precompute lookup tables of discrete logarithms or numerical roots of unity, and can therefore safely be called even with large q.

For implementation reasons, the largest prime factor of q must not exceed \(10^{16}\). This restriction could be removed in the future. The function returns 1 on success and 0 if a factor is too large.

dirichlet_subgroup_init H G h

Given an already computed group G mod \(q\), initialize its subgroup H defined mod \(h\mid q\). Precomputed discrete log tables are inherited.

dirichlet_group_clear G

Clears G. Remark this function does not clear the discrete logarithm tables stored in G (which may be shared with another group).

dirichlet_group_size G

Returns the number of elements in G, i.e. \(\varphi(q)\).

dirichlet_group_num_primitive G

Returns the number of primitive elements in G.

dirichlet_group_dlog_precompute G num

Precompute decomposition and tables for discrete log computations in G, so as to minimize the complexity of num calls to discrete logarithms.

If num gets very large, the entire group may be indexed.

dirichlet_group_dlog_clear G num

Clear discrete logarithm tables in G. When discrete logarithm tables are shared with subgroups, those subgroups must be cleared before clearing the tables.

Use DirichletChar in f.

Apply f to new DirichletChar.

dirichlet_char_init chi G

Initializes chi to an element of the group G and sets its value to the principal character.

dirichlet_char_clear chi

Clears chi.

dirichlet_char_print G chi

Prints the array of exponents representing this character.

dirichlet_char_log x G m

Sets x to the character of number m, computing its log using discrete logarithm in G.

dirichlet_char_exp G x

Returns the number m corresponding to exponents in x.

_dirichlet_char_exp x G

Computes and returns the number m corresponding to exponents in x. This function is for internal use.

dirichlet_char_one x G

Sets x to the principal character in G, having log \([0,\dots 0]\).

dirichlet_char_first_primitive x G

Sets x to the first primitive character of G, having log \([1,\dots 1]\), or \([0, 1, \dots 1]\) if \(8\mid q\).

dirichlet_char_set x G y

Sets x to the element y.

dirichlet_char_next x G

Sets x to the next character in G according to lexicographic ordering of log.

The return value is the index of the last updated exponent of x, or -1 if the last element has been reached.

This function allows to iterate on all elements of G looping on their log. Note that it produces elements in seemingly random number order.

The following template can be used for such a loop:

dirichlet_char_one(chi, G);
do {
    /* use character chi */
} while (dirichlet_char_next(chi, G) >= 0);

dirichlet_char_next_primitive x G

Same as dirichlet_char_next, but jumps to the next primitive character of G.

dirichlet_index_char G x

Returns the lexicographic index of the log of x as an integer in \(0\dots \varphi(q)\).

dirichlet_char_index x G j

Sets x to the character whose log has lexicographic index j.

dirichlet_char_eq_deep G x y

Return 1 if x equals y.

The second version checks every byte of the representation and is intended for testing only.

dirichlet_char_is_principal G chi

Returns 1 if chi is the principal character mod q.

dirichlet_conductor_char G x

Returns the conductor of \(\chi_q(a,\cdot)\), that is the smallest \(r\) dividing \(q\) such \(\chi_q(a,\cdot)\) can be obtained as a character mod \(r\).

dirichlet_parity_char G x

Returns the parity \(\lambda\) in \(\{0,1\}\) of \(\chi_q(a,\cdot)\), such that \(\chi_q(a,-1)=(-1)^\lambda\).

dirichlet_order_char G x

Returns the order of \(\chi_q(a,\cdot)\) which is the order of \(a\bmod q\).

dirichlet_char_is_real G chi

Returns 1 if chi is a real character (iff it has order \(\leq 2\)).

dirichlet_char_is_primitive G chi

Returns 1 if chi is primitive (iff its conductor is exactly q).

dirichlet_pairing_char G chi psi

Compute the value of the Dirichlet pairing on numbers m and n, as exponent modulo G->expo.

The char variant takes as input two characters, so that no discrete logarithm is computed.

The returned value is the numerator of the actual value exponent mod the group exponent G->expo.

dirichlet_chi G chi n

Compute the value \(\chi(n)\) as the exponent modulo G->expo.

dirichlet_chi_vec v G chi nv

Compute the list of exponent values v[k] for \(0\leq k < nv\), as exponents modulo G->expo.

dirichlet_chi_vec_order v G chi order nv

Compute the list of exponent values v[k] for \(0\leq k < nv\), as exponents modulo order, which is assumed to be a multiple of the order of chi.

dirichlet_char_mul chi12 G chi1 chi2

Multiply two characters of the same group G.

dirichlet_char_pow c G a n

Take the power of a character.

dirichlet_char_lift chi_G G chi_H H

If H is a subgroup of G, computes the character in G corresponding to chi_H in H.

dirichlet_char_lower chi_H H chi_G G

If chi_G is a character of G which factors through H, sets chi_H to the corresponding restriction in H.

This requires \(c(\chi_G)\mid q_H\mid q_G\), where \(c(\chi_G)\) is the conductor of \(\chi_G\) and \(q_G, q_H\) are the moduli of G and H.