Discrete logs and non generators

  • #1
fishturtle1
394
81

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
4,021
1,585
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
fishturtle1
394
81
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
4,021
1,585
-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
fishturtle1
394
81
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.
 

Suggested for: Discrete logs and non generators

  • Last Post
Replies
2
Views
608
Replies
12
Views
432
  • Last Post
Replies
12
Views
336
Replies
5
Views
213
Replies
8
Views
541
Replies
23
Views
622
  • Last Post
Replies
6
Views
653
  • Last Post
Replies
16
Views
789
  • Last Post
Replies
7
Views
691
  • Last Post
Replies
7
Views
983
Top