Discrete logs and non generators

In summary: Your alternative responses to the contradiction are very insightful.In summary, the conversation discusses the well-definition of discrete logarithm when the base is not a generator. A proof is provided, but a correction is needed in the initial assumption. Two alternative responses to the contradiction are also presented, highlighting different ways of defining the discrete logarithm in such cases.
  • #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:
Physics news on Phys.org
  • #2
The proof looks sound, but there's a correction needed. In this bit
fishturtle1 said:
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
andrewkirk said:
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
fishturtle1 said:
-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
andrewkirk said:
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.
 

1. What is a discrete log?

A discrete log is a mathematical operation used in cryptography that involves finding the exponent used to raise a base number to a given power, within a finite group. It is denoted as logg(x) and is the inverse of exponentiation.

2. What is the significance of discrete logs in cryptography?

Discrete logs are used in many cryptographic algorithms, such as Diffie-Hellman key exchange and the ElGamal encryption scheme. They provide a way to securely share secret information between parties, without revealing the actual values being exchanged.

3. What is a non-generator in discrete logs?

A non-generator, also known as a weak key, is an element in a finite group that does not generate the entire group when raised to different powers. This means that the discrete log of this element cannot be computed efficiently, making it less secure for use in cryptographic algorithms.

4. How are discrete logs and non-generators related in cryptography?

In cryptography, the use of non-generators in place of generators can lead to security vulnerabilities. This is because the discrete log of these weak keys can be computed using a brute force approach, making it easier for an attacker to break the encryption and gain access to the secret information being exchanged.

5. How can discrete logs and non-generators be used to improve security?

By carefully selecting generators and avoiding the use of non-generators, it is possible to strengthen the security of cryptographic algorithms that rely on discrete logs. Additionally, using larger prime numbers and groups can also make it more difficult for an attacker to compute discrete logs and break the encryption.

Similar threads

  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
945
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
Back
Top