Discrete logarithm tables

The dlog module computes discrete logarithms in a cyclic group \langle a \rangle \subseteq (\mathbb{Z}/m\mathbb{Z})^\times of order n, for word-size m. Its use case, Dirichlet characters (Dirichlet characters), asks for many logarithms to the same base, typically with m a prime power and a a primitive root. The module therefore separates a precomputation, sized for an expected number k of queries, from the queries themselves. For the general theory see [CraPom2005, §5.2–5.3]; the single-logarithm algorithm of nmod is described in Discrete logarithms modulo a prime (Pohlig–Hellman).

Baby-step giant-step with a balanced table#

Shanks' method [Sha1971] stores the baby steps (j, a^j) for 0 \le j < M, sorted by value, and for a query b computes the giant steps b a^{-iM}, i = 0, 1, \ldots, until one of them is found in the table as a^j; then \log_a b = iM + j.

dlog_bsgs_size(n, k) returns (1 + \lfloor\sqrt n\rfloor)(1 + \lfloor\sqrt k\rfloor) when 2k < n, and n (a complete table, so that every query is one search) otherwise. For groups of order at most 3 no table is needed, and for moduli below 50 a table indexed by the residue replaces the sorted array.

Pohlig–Hellman decomposition#

If n = \prod_i p_i^{e_i}, the logarithm modulo p_i^{e_i} of b is the logarithm of b^{n/p_i^{e_i}} to the base a^{n/p_i^{e_i}}, of order p_i^{e_i}, and the Chinese remainder theorem combines them [PohHel1978]. Within a group of order p^e, write x = \sum_{t < e} x_t p^t; then

so each digit x_t is a logarithm in the subgroup of order p, generated by a^{p^{e-1}}. A logarithm in a group of order n thus costs O(\sum_i e_i (\log n + c(p_i))) multiplications, where c(p) is the cost of a logarithm in a group of order p; the structure is the same as for nmod_discrete_log_pohlig_hellman. In FLINT, dlog_crt_t holds one precomputation per prime power, and dlog_power_t one precomputation of the subgroup of order p, built for e k queries.

Prime power moduli and p-adic logarithms#

For m = p^e with p odd and a a primitive root modulo p^2, the group (\mathbb{Z}/p^e\mathbb{Z})^\times has order (p-1)p^{e-1}, and its p-Sylow part is the subgroup U_1 = \{x \equiv 1 \pmod p\}, cyclic of order p^{e-1} and generated by 1 + p. Logarithms there are cheap:

So \log_{1+p} b is found one base-p digit at a time (dlog_1modpe_1modp), with e - 1 modular powers. The logarithm to the base a is then obtained from two smaller problems.

The logarithm y is \log_{1+p}(b^{p-1}) divided by \log_{1+p}(a^{p-1}) modulo p^{e-1}, which is precomputed (dlog_1modpe_init). For m = 2^e the subgroup of elements \equiv 1 \pmod 4 is generated by 5, and \log_5 is found one bit at a time in the same way (dlog_mod2e_1mod4). The cost of a logarithm modulo p^e is therefore a logarithm modulo p, in a group of order p - 1, plus O(e) modular powers.

Choosing the method#

dlog_precomp_modpe_init, dlog_precomp_n_init, dlog_precomp_pe_init and dlog_precomp_p_init choose the method from what is known about the group, recursively:

Each method returns an estimate of the cost of one logarithm in multiplications (cost), which the sieve below uses to decide whether to look for relations.

Pollard's rho method [Pol1978], which needs O(\sqrt n) time and no memory, is available as dlog_rho but is not used by these precomputations.

The logarithms of all small integers#

To evaluate a Dirichlet character at 0, 1, \ldots, N - 1, one needs \log_a k for all k < N. Two methods are used.

Enumeration (dlog_vec_loop). Running through a^0, a^1, \ldots, a^{n-1} and recording the exponent of every power below N costs n multiplications. It is the method of choice when N is comparable with n (FLINT uses it when 6n < N).

Sieving (dlog_vec_sieve). Logarithms are additive, \log_a(jk) = \log_a j + \log_a k, so it suffices to compute \log_a p for the primes p < N and to fill in the other entries in increasing order, v[pk] = v[k] + v[p]. A prime p costs one precomputed logarithm. For larger primes, a relation with smaller numbers may be cheaper: with c = a^X for a fixed X, compute for i = 1, 2, \ldots a partial extended Euclidean algorithm on (m, p c^i \bmod m), stopped when the remainder r and the cofactor u are both about \sqrt m, so that

If r and u factor into primes below p, whose logarithms are already known, then \log_a p = \log_a r - \log_a u - iX \pm \log_a(-1). The probability that two numbers of size \sqrt m are p-smooth is about \rho(s)^2 with s = \log \sqrt m / \log p, which FLINT estimates crudely by s^{-s} with s = \log m/\log p; it searches for relations only when this predicts fewer multiplications than a precomputed logarithm. This is a small instance of the index calculus method [CraPom2005, §6.4], without the linear algebra.

Use in FLINT#

• dlog_precomp_t and its initialisation functions implement the strategy table above with dlog_table_t, dlog_bsgs_t, dlog_crt_t, dlog_power_t, dlog_modpe_t and dlog_order23_t; dlog_once enumerates for orders below 50 and otherwise uses a precomputation for one query.
• dlog_vec and dlog_vec_add choose between dlog_vec_loop and dlog_vec_sieve; dlog_vec_add_precomp reuses an existing precomputation. dlog_vec_eratos computes the logarithm of every prime directly.
• dirichlet_group_dlog_precompute builds dlog_precomp_modpe_init tables for each prime power component; dirichlet_char_log and dirichlet_chi_vec use them, or dlog_once and dlog_vec_add when no tables were requested.