dlog.h

Returns $x$ with $a^x \equiv b$ modulo mod.n, where $a$ has order $n$: by enumerating the powers of $a$ for $n < 50$ (throwing if $b$ is not found), and otherwise with a precomputation for one query (dlog_precomp_n_init with num $= 1$), which is cleared afterwards.

Initialises pre for about num logarithms to the base $a$ of order $n$ modulo mod, with no further information on $n$. If $n$ is an odd prime the function calls dlog_precomp_p_init; otherwise it uses a complete table for $n < 50$, baby-step giant-step for $n < 500$, and the Pohlig–Hellman decomposition (dlog_crt_init) above.

As dlog_precomp_n_init for a base of prime order $p$: a complete table for $p < 50$, otherwise baby-step giant-step with a table of dlog_bsgs_size(p, num) powers.

As dlog_precomp_n_init for a base of prime power order $\mathit{pe} = p^e$: a complete table for $p^e < 50$, dlog_precomp_p_init for $e = 1$, and otherwise the base-$p$ digit decomposition (dlog_power_init).

Initialises pre for logarithms to the base $a$ modulo $\mathit{pe} = p^e$, where $a$ generates $(\mathbb{Z}/p^e\mathbb{Z})^\times$ (for odd $p$), or, for $p = 2$ and $e \ge 3$, $a = 5$ generates the subgroup of elements congruent to 1 modulo 4. Uses a complete table for $p^e < 50$, the reduction to a logarithm modulo $p$ and a $p$-adic logarithm (dlog_modpe_init) for $e \ge 2$, and dlog_precomp_n_init modulo $p$ for $e = 1$.

Initialises pre for a group of small order $n$: the trivial method for $n \le 3$, a complete table indexed by the residues if $\mathit{mod} < 50$, and otherwise a baby-step giant-step table containing all $n$ powers (so that a logarithm is one binary search).

Returns the logarithm of $b$ (reduced modulo the modulus) to the base of pre.

Frees the memory used by pre. Does nothing if pre is NULL.

Set $v[k]$ to $v_a \log_a(k) \bmod \mathit{order}$, or (the add version) add it to $v[k]$ modulo order for every $k$ with $v[k] \ne$ DLOG_NONE. They do nothing if $v_a = 0$. Both use loop if $6 n_a < \mathit{nv}$ and sieve otherwise.

As dlog_vec and dlog_vec_add, by enumerating the $n_a$ powers of $a$ and copying the values to the entries $k \ge m$ by periodicity. Costs $O(n_a + \mathit{nv})$ and needs no discrete logarithm.

As dlog_vec and dlog_vec_add, by computing the logarithms of the primes $p < \min(\mathit{nv}, m)$ and extending them to all $k$ by complete multiplicativity. The logarithms of the primes are computed with a precomputation for 50 queries, except that for primes large enough a relation with smaller numbers is searched first (dlog_vec_pindex_factorgcd). The full index calculus method is not implemented.

As dlog_vec_sieve, dlog_vec_sieve_add and dlog_vec_add, with the logarithms of the primes taken from an existing precomputation pre for the base $a$.

As dlog_vec and dlog_vec_add, by computing the logarithm of every prime below $\min(\mathit{nv}, m)$ with a precomputation and adding it to all multiples of its powers, as in the sieve of Eratosthenes. The add version assumes that the entries not coprime to $m$ are already DLOG_NONE.

Sets $v[k] = x$ for $0 \le k < \mathit{nv}$.

Sets $v[k]$ to DLOG_NONE for the $0 < k < \mathit{nv}$ divisible by a prime factor of the modulus.

Tries to find the logarithm of the prime $p$ from the logarithms already stored in $v$: for $i = 1, 2, \ldots$ up to maxtry, writes $p a^i \equiv \pm r/u \pmod m$ with $r, u$ about $\sqrt m$ by a partial extended Euclidean algorithm, and if $r$ and $u$ factor over the entries of $v$ already known (after removing primes below $p/4$), returns $\log r - \log u - i \log a$ (adjusted by logm1, the logarithm of $-1$). Here loga is the value to use for $\log a$. Returns DLOG_NOT_FOUND if no relation is found.

Build the table of the logarithms of the powers of $a$ modulo mod (an array of mod words; $a$ must be invertible, which is not checked), free it, and look up $\log_a(b)$. The cost estimate is 1.

Store $a$, do nothing, and return 0 if $b = 1$, 1 if $b = a$, and 2 otherwise. The cost estimate is 0.

Initialises $t$ with the $m$ baby steps $a^0, \ldots, a^{m-1}$ (or $n$ if $m > n$), sorted by value, for a base of order $n$. Returns the number of giant steps $\lfloor n/m \rfloor + 1$, the worst-case cost of one logarithm. For $k$ logarithms, $m \approx \sqrt{kn}$ minimises the total cost.

Returns the table size used for num logarithms in a group of order $n$: $(1 + \lfloor\sqrt n\rfloor)(1 + \lfloor\sqrt{\mathit{num}}\rfloor)$ if $2\,\mathit{num} < n$, and $n$ otherwise.

Free the table, and return $\log_a(b)$ by multiplying $b$ by $a^{-m}$ until the product is found in the table (by binary search). Throws if $b$ is not a power of $a$.

Comparison function of the pairs $(k, a^k)$ by the value $a^k$, for qsort and bsearch.

Initialise $t$ for num logarithms to the base $a$ of order $n$ modulo mod, by factoring $n$ and initialising dlog_precomp_pe_init for $a^{n/p^e}$ in each subgroup of prime power order (the returned cost is the sum of their costs); free it; and return $\log_a(b)$, combining the logarithms of $b^{n/p^e}$ by the Chinese remainder theorem.

Initialise $t$ for num logarithms to the base $a$ of order $p^e$ (the subgroup precomputation is made for $e \cdot \mathit{num}$ logarithms and the cost is $e$ times its cost); free it; and return $\log_a(b)$, found one base-$p$ digit at a time, each digit a logarithm in the subgroup of order $p$.

Initialise $t$ for num logarithms to the base $a$ modulo $\mathit{pe} = p^e$; free it; and return $\log_a(b)$, combining the logarithm of $b \bmod p$ modulo $p - 1$ with the logarithm of $b^{p-1}$ in $1 + p\mathbb{Z}$, which determines $\log_a(b)$ modulo $p^{e-1}$. For $p = 2$ the base must be 5 (or a generator of the elements congruent to 1 modulo 4) and $b \equiv 1 \pmod 4$; this case uses dlog_mod2e.

For odd $p$ and $a_1 \equiv 1 \pmod p$ generating $1 + p\mathbb{Z}$ modulo $p^e$, precompute the inverse of the logarithm of $a_1$ to the base $1 + p$ (throws if $a_1 = 1$ and $e > 1$), and return the logarithm of $b_1 \equiv 1 \pmod p$ to the base $a_1$, modulo $p^{e-1}$.

Returns the logarithm $x \in [0, p^{e-1})$ of $b_1 \equiv 1 \pmod p$ to the base $1 + p$ modulo $p^e$, given inv1p $= (1 + p)^{-1} \bmod p^e$, determining one base-$p$ digit per step. Throws if $b_1 \not\equiv 1 \pmod p$.

Return the logarithm of $b_1 \equiv 1 \pmod 4$ to the base 5 modulo $2^e$, given inv5 $= 5^{-1} \bmod 2^e$, determining one bit per step (throws if $b_1 \not\equiv 1 \pmod 4$); and the logarithm for a dlog_modpe_t with $p = 2$ (for $e = 2$, whether $b \equiv 3 \pmod 4$).

Initialise $t$ for the base $a$ of order $n$ modulo mod; do nothing; and return $\log_a(b)$ with Pollard's rho method [Pol1978], using a random walk with 20 steps and Floyd's cycle detection, in expected time $O(\sqrt n)$ and constant memory. For composite $n$ a relation that does not determine the logarithm is completed recursively. This method is not used by dlog_precomp_t.

Regroups the prime power factors in fac into products not exceeding bound, marking them DLOG_G_SMALL, and multiplies the remaining factors into one marked DLOG_G_BIG. Not used by the library.