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.