Discrete logs and non generators

fishturtle1

Homework Statement

This is just a question that i can't seem to answer while reviewing...

Is discrete log well defined when the base is not a generator?

The Attempt at a Solution

For example, ##2^3 \equiv 2^6 (\operatorname{mod} 7)##. Taking the discrete log of both sides, ##3 \equiv 0 (\operatorname{mod} 6)##...

So is the discrete log not well defined if the base is not a generator?Sorry if this is obvious, I've just never noticed this..

Edit 1: I wrote a proof, Please critique it.

Proof: We look to show the discrete log is not well defined if our base is not a generator.

Suppose ##a \epsilon \mathbb{Z}_p^*## and ##a## is not a generator. Let ##a^x \equiv h (\operatorname{mod} p)## where ##x \epsilon \mathbb{Z}_{p-1}##. Since ##a## is not a generator is has order ##d## where ##0 < d \le \frac{p-1}{2}##. So ##a^xa^d \equiv h (\operatorname{mod} p)##. So ##a^{x+d} \equiv h(\operatorname{mod} p)##.

So ##log_a(h) = x = x + d##. So ##x \equiv x + d (\operatorname{mod} p - 1)##. So ##0 \equiv d (\operatorname{mod} p - 1)##. So ##(p-1) \vert d##. By Lagrange's theorem, ##d \vert (p-1)##. So ##d = p - 1##, a contradiction.

We can conclude discrete log function is not well defined for a base that is not a generator.[]

Last edited:

Homework Helper
Gold Member
The proof looks sound, but there's a correction needed. In this bit
Since ##a## is not a generator is has order ##d## where ##0 < d \le \frac{p-1}{2}##.
the ##\le## should be ##<##, otherwise we can't get the final contradiction.

Two alternative responses to the contradiction are:

1. We could define 'a discrete logarithm' in ##Z_p##, for ##p## prime, of ##a## base ##b## as any ##k\in\mathbb Z_{p-1}## such that ##b^k=a\mod p##. That way, there is a set of one or more discrete logarithms for any given case.

OR

2. We could define 'the discrete logarithm' in ##Z_p##, for ##p## prime, of ##a## base ##b## as the smallest ##k\in\mathbb Z_{p-1}## such that ##b^k=a\mod p##.

fishturtle1
The proof looks sound, but there's a correction needed. In this bit

the ##\le## should be ##<##, otherwise we can't get the final contradiction.

Two alternative responses to the contradiction are:

1. We could define 'a discrete logarithm' in ##Z_p##, for ##p## prime, of ##a## base ##b## as any ##k\in\mathbb Z_{p-1}## such that ##b^k=a\mod p##. That way, there is a set of one or more discrete logarithms for any given case.

OR

2. We could define 'the discrete logarithm' in ##Z_p##, for ##p## prime, of ##a## base ##b## as the smallest ##k\in\mathbb Z_{p-1}## such that ##b^k=a\mod p##.
Thanks for the response!

A couple questions:
-Why should the ##\le## be a ##<##? Even if ##d = \frac{p-1}{2}##, doesn't the contradiction rely on ##d = p-1##?

-By alternative responses to the contradiction, do you mean if we define the discrete log as 1) or 2), then the discrete log is well defined for non generators?