- #1

fishturtle1

- 394

- 82

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

Last edited: