2
$\begingroup$

This question is not a question about the discrete log problem, the generalized discrete log problem, or an additive group.

The confusion is whether any integer can be considered a discrete log or whether a discrete log has as a precondition, that it be part of a multiplicative group. This wikipedia would seem to indicate that the answer is yes.

For example 0 doesn't have a multiplicative inverse and is therefore not part of a multiplicative group.

Improve this question
$\endgroup$
16
  • $\begingroup$ @kelalaka Would you mind expanding upon "The discrete log is defined according to a base as the logarithm." $\endgroup$
    – JohnGalt
    Commented Apr 17, 2019 at 18:28
  • $\begingroup$ @kelalaka also if "0 is not a part of the multiplicative group" does that mean that not all integers are part of a discrete log? $\endgroup$
    – JohnGalt
    Commented Apr 17, 2019 at 18:29
  • 1
    $\begingroup$ @JohnGalt In the statement you quoted, the context is discrete logs in $\mathbb Z/n\mathbb Z$ for some $n$. It means: For any integer $x$, there exists some $n$ and some $g, h \in \mathbb Z/n\mathbb Z$ such that $x = \log_g h$, i.e. $h = g^x$. To interpret that sentence, there is no need to extend the term ‘discrete log’ to the ring of all integers, or to extend the term to apply outside the context of any particular group, because the term is only ever being used within some particular group $\mathbb Z/n\mathbb Z$. $\endgroup$
    – Squeamish Ossifrage
    Commented Apr 18, 2019 at 1:47
  • 1
    $\begingroup$ By the way, the statement you quoted is indeed not true for $0$, in the context of groups of the form $(\mathbf Z/n\mathbf Z)^*$. $0$ is indeed not part of any such group (or it is part of exactly one such group, if you allow the degenerate case $n=1$), and it is a discrete log of exactly one element of any such group (the identity element), not infinitely many. It is however a discrete log of an element, so it is a discrete log indeed. $\endgroup$
    – fkraiem
    Commented Apr 18, 2019 at 2:59
  • 1
    $\begingroup$ All integers between $1$ and $k−1$ will be results of some $log_b a$, where $b$, $a$ are in $Z/nZ$ and (this is the important part) $k$ is the order of the highest-order element of the multiplicative group, $(Z/nZ)^{\times}$, of units of $Z/nZ$. So, for example (mod 9), 5 is a discrete log bc $4^5=7$(mod 9), but 7 is not a discrete log (mod 9) because $(Z/9Z)^{\times}$ has only 6 elements. So no element of $(Z/9Z)^{\times}$ can have order 7. $\endgroup$
    – grovkin
    Commented Apr 18, 2019 at 6:09

2 Answers 2

Reset to default
5
$\begingroup$

The discrete logarithm $\log_b a$ is an integer $x$ such that $b^x = a$. Similarly to the logarithms, we need a base, here $b$.

If the base is a generator of the group $g$ then any element of the group can be written as a power of the $g$ for some $k$, $y = g^k$. Therefore, the discrete log of $y$ according to base $g$ is $k$.

Take a generator $g$ of a multiplicative group $G$ with order $n$, and then take $g'=g^k$ where $\gcd(k,n) \neq 1$. Now the $g'$ will generate a subgroup $G'\leqslant G$, not the full group. Then any element of the full group $ a \in G$ and $a \not\in G'$ has not discrete logarithm according to base $g'$, even it is not a member of the subgroup.

When we consider the non-zero elements of a field $F\backslash\{0\}$ they are forming a cyclic group under multiplication. For a proof see the Theorem 1.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It is very possible for $g^2$ to be a generator of $G$; in fact it will be one if and only if the order of $G$ is odd. $\endgroup$
    – fkraiem
    Commented Apr 17, 2019 at 20:05
  • $\begingroup$ @fkraiem updated to guarantee that $g^k$ is generates a subgroup. $\endgroup$
    – kelalaka
    Commented Apr 17, 2019 at 20:19
3
$\begingroup$

Of course any integer can be a discrete logarithm: in a group $G$ with generator $g$, any integer $x$ is a discrete logarithm of the group element $g^x$.

Another convenient way to consider the set of discrete logarithms is as the ring $\mathbf Z/n\mathbf Z$, where $n$ is the order of $G$, which makes sense because $g^x = g^{x \bmod n}$ for all $x$. This is especially convenient when $n$ is prime because then the discrete logarithms form a field.

Either way (unless the group is trivial) the discrete logarithms form a non-trivial ring with unity, which is not a group for multiplication.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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