2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Algeboy Apr 5 '18 at 22:32
  • $\begingroup$ @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. $\endgroup$ – tparker Apr 6 '18 at 0:13
  • $\begingroup$ 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. $\endgroup$ – Algeboy Apr 6 '18 at 15:31
  • $\begingroup$ 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. $\endgroup$ – Algeboy Apr 6 '18 at 15:33
1
+50
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – tparker Apr 7 '18 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.