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

Question

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?

Answer 1

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).