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?

Homework Equations

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.[]

 

[andrewkirk]

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?

 

[andrewkirk]

-Why should the $\le$ be a $<$?

Because if they are equal, the element is a generator. The contradiction arises from the fact that we have assumed that the element is not a generator, which entails that $d<p-1$ and we then prove that $d=p-1$, which entails that $d\neq 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?

I mean that the concept of 'discrete log' will be well defined. In (2) that means that the discrete log is well defined. In (1) it makes no sense to say the discrete log. We have to say a discrete log, because in that case 'being a discrete log' is a property that can be held by more than one thing.

 

[fishturtle1]

Because if they are equal, the element is a generator. The contradiction arises from the fact that we have assumed that the element is not a generator, which entails that $d<p-1$ and we then prove that $d=p-1$, which entails that $d\neq p-1$.
I mean that the concept of 'discrete log' will be well defined. In (2) that means that the discrete log is well defined. In (1) it makes no sense to say the discrete log. We have to say a discrete log, because in that case 'being a discrete log' is a property that can be held by more than one thing.

I understand, thank you.