# Characterizations of the discrete logarithms for algebraic structures more general than groups

For an arbitrary group with elements $a$ and $b$, the discrete logarithm $\log_b a$ is defined as an integer $x$ that solves the equation $b^x = a$. It's straightforward to show that the set of discrete logarithms $\log_b a$ is either empty or forms a congruence class modulo the order $n$ of the element $b$ in the group: in one direction, we have $$b^{x_1} = b^{x_2} = a \implies b^{x_1 - x_2} = b^0 = e \implies x_1 - x_2 = mn \text{ for some integer } m \implies x_1 \equiv x_2 \text{ mod } n.$$ In the other direction, we have $$b^x = a \implies b^{x + mn} = b^x \left(b^n\right)^m = a e^m = a.$$ The security of several widely used encryption systems hinges on the difficulty of calculating discrete logarithms for modular multiplicative groups.

But we don't need nearly the full algebraic structure of a group for the definition of the discrete logarithm to make sense; we can easily generalize it to any set with a power-associative partial binary operation. (Although in this generalized setting, discrete logarithms can only be positive integers.) For example, consider the commutative modular multiplicative monoid of all congruence classes mod $n$ under multiplication (not just those relatively prime to $n$, as required for invertibility). Since the congruence classes that aren't relatively prime with $n$ don't have a modular multiplicative inverse, we can't raise them to negative integer powers, and the proof above doesn't work (morever, these elements don't even have a finite order).

Are there any general results characterizing the set of discrete logarithms $\log_b a$ for algebraic structures more general than groups?

• Well there are Deffie-Helman style key exchanges in elliptic curves and free groups etc. so it is more general already. But calculating $a^x mod n$ is extremely fast and thus allows fast encryption leaving behind a potentially hard decryption -- most other algebras wont have such fast operations making them less useful. But more important, a cyclic monoid just adds a run up before it enters a cycle, how is that any harder than the group model? – Algeboy Apr 5 '18 at 22:32
• @Algeboy My understanding is that Diffie-Hellman doesn't use the modular multiplicative group, but it does use other groups (e.g. free group or, in the case of elliptic-curve, the direct product of either one or two cyclic groups). I'm wondering about the generalization of the discrete log to algebraic structures that aren't a group at all. I'm not really concerned with crypto applications specific, just the general mathematical structure. But you may be right that cyclic monoids are too trivial of a generalization to be interesting. – tparker Apr 6 '18 at 0:13
• Ok, so ignoring the application, I still wonder how a group is avoided. To ask if a^n=b in a power associative setting would be to study the substructure generated by a, call it <a> = {a^i: in in N}. If its finite then a^i = a^j at some point, you are then in a cycle. If you just start with <a^i> then you have a cyclic group. I don't see how you avoid the group context. – Algeboy Apr 6 '18 at 15:31
• Actually perhaps your could ask this as a membership test, then there are lots of examples of this. I.e. you have an algebraic system A and a substructure $B$. Given an $a\in A$, ask if $a\in B$. The constructive membership question would be to further write $a$ in the generators for $B$. Those problems are very general and in some spirit like discrete logs. – Algeboy Apr 6 '18 at 15:33

## 1 Answer

Let's wlog restrict to monoids instead of power-associative semigroups (otherwise consider the monoid generated by $a$).

Then there are only three cases:

1. $a$ is invertible. That case you already know how to handle.
2. $a$ is non-invertible, but there are repetitions in the sequence $1,a,a^2,a^3,\ldots$
3. $a$ is non-invertible and there are no repitions.

In the second case, there are $n\in\mathbb{N}, p\in\mathbb{N}_{>0}$ such that $\forall k\in\mathbb{N}: a^{n+kp} = a^n$. Wlog we choose $n$ and $p$ minimal w.r.t. this property. In this case, the set of discrete logarithms $Log_a(b)$ is either empty if $b\notin a^\mathbb{N}$, a single number if $b$ is in the pre-period $\{1,a^0,\ldots,a^{n-1}\}$, or the logarithms form "one half" of a congruence class modulo the period length $p$, namely a set of the form $n+x+p\mathbb{N}$ for some unique $0\leq x<p-1$.

In the third case, all logarithms are unique (if they exist at all).

• Great, thanks. So to summarize, there are four possible structures for the set of integers $\log_b a$: it can be (a) empty, (b) a single integer, (c) a "half congruence class" as you define in your answer, or (d) a congruence class. – tparker Apr 7 '18 at 22:55