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.

@misc{flint-doc-algorithms-number-theory-discrete-log-tables,
  author       = {{The FLINT team}},
  title        = {{Discrete logarithm tables}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/number-theory/discrete-log-tables.html},
  note         = {Generated 2026-11-02}
}