Discrete logs and non generators

  • #1
338
45

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:

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,933
1,496
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##.
 
  • #3
338
45
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?
 
  • #4
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,933
1,496
-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.
 
  • #5
338
45
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.
 

Related Threads on Discrete logs and non generators

  • Last Post
Replies
7
Views
804
Replies
11
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
4
Views
4K
Replies
1
Views
2K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
409
Replies
0
Views
2K
Top