Can Discrete Logarithms Be Added in Modular Arithmetic?

In summary, the given problem involves proving that for all ##h_1, h_2 \epsilon \mathbb{Z}/p\mathbb{Z}##, the discrete logarithm of the product of ##h_1## and ##h_2## is equal to the sum of the discrete logarithms of ##h_1## and ##h_2##, given that ##g## is a primitive root for ##\mathbb{
  • #1
fishturtle1
394
82

Homework Statement


Let g be a primitive root for ##\mathbb{Z}/p\mathbb{Z}## where p is a prime number.

b) Prove that ##\log_g(h_1h_2) = \log_g(h_1) + \log_g(h_2)## for all ##h_1, h_2 \epsilon \mathbb{Z}/p\mathbb{Z}##.

Homework Equations


Let x, denoted ##\log_g(h)##, be the discrete logarithm of g to the base g. Then ##g^x \equiv h## (mod p).

In part a) I showed : Suppose that ##x = a## and ##x = b## are both integer solutions to the congruence ##g^x \equiv h## (mod p). Prove that ##a \equiv b## (mod p - 1).

The Attempt at a Solution


Attempted proof:
We have ##g^{\log_g(h_1)}g^{\log_g(h_2)} \equiv h_1h_2## (mod p). So
##g^{\log_g(h_1) + \log_g(h_2)} \equiv h_1h_2## (mod p).

We know ##\log_g(h_1h_2) \le p - 1## must be true. But ##\log_g(h1) + \log_g(h_2)## could be greater than p - 1. So, even though they are congruent modulo p - 1, they might not be equal. Let ##\log_g(h_1) + \log_g(h_2) = (p - 1)q + r## where ##q, r \epsilon \mathbb{Z}## and ##0 \le r < p -1##. Using Fermat's Little Theorem, we have

##g^{\log_g(h_1) + \log_g(h_2)}g^{q(p - 1)} \equiv h_1h_2(1)^q## (mod p).
##g^{\log_g(h_1) + \log_g(h_2) + q(p - 1)} \equiv h_1h_2## (mod p).
Taking the log of both sides, we get
##r \equiv \log_g(h_1h_2)## (mod p).
and since ##r < p - 1## and ##\log_g(h_1h_2) < p - 1## we can conclude
##r \equiv \log_g(h_1h_2)## (mod p - 1).
But ##r## and ##\log_g(h_1) + \log_g(h_2)## are just elements of the equivalence class ##[r]## in ##\mathbb{Z}/p\mathbb{Z}##. So we can conclude by transitivity ##\log_g(h_1) + \log_g(h_2) \equiv \log_g(h_1h_2)## (mod p - 1). []

edit: sorry, I keep reading this question wrong, but this is the same stuck point I've gotten a few different ways... I'm not sure how to go from here, to the ##\log_g(h_1h_2) = \log_g(h1) + \log_g(h2)## for all ##h_1, h_2 \epsilon \mathbb{Z}/p\mathbb{Z}##.
 
Physics news on Phys.org
  • #2
I think this is far too complicated. Why don't you set ##h_1 = g^x\; , \;h_2 = g^y \; , \; (h_1h_2)=g^z## (do they exist?), and show ##x+y \equiv z \operatorname{mod} p## ?
 
  • #3
fresh_42 said:
I think this is far too complicated. Why don't you set ##h_1 = g^x\; , \;h_2 = g^y \; , \; (h_1h_2)=g^z## (do they exist?), and show ##x+y \equiv z \operatorname{mod} p## ?
Thanks for the reply.

So we can have ##h_1 = g^x\; , \;h_2 = g^y \; , \; (h_1h_2)=g^z##. These numbers definitely exist because ##g## is a primitive root of Z/pZ, so it generates Z/pZ. Also, ##x , y, z < p##. So, ##g^xg^y = g^{x + y} = g^z##. Using the discrete logarithm, we have ##\log_g(g^{x + y}) = \log_g(g^z)##, which simplifies to ##x + y \equiv z## (mod p).

I think from "So, ##g^xg^y = g^{x + y} = g^z##." I could conclude that x + y = z and i'd be done. But doing that I wouldn't use the discrete log and I'm pretty sure i need to use it.
 
  • #4
You don't use it, since you want to prove it. But ##g^xg^y=g^{x+y}=g^z## gives you ##g^{x+y-z}=e## and thus ##x+y-z \equiv 0 \operatorname{mod} p##. This way the logarithm is only needed to define ##x,y,z##.
 
  • #5
fresh_42 said:
You don't use it, since you want to prove it. But ##g^xg^y=g^{x+y}=g^z## gives you ##g^{x+y-z}=e## and thus ##x+y-z \equiv 0 \operatorname{mod} p##. This way the logarithm is only needed to define ##x,y,z##.
Thank you, I didn't think of that.

Let ##h_1 = g^x, h_2 = g^y## and ##h_1h_2 = g^z##. So we have ##g^xg^y = g^{x+y} = g^z##. Multiplying by ##g^{-z}## we get ##g^{x+y-z} = e##, where e is the identity. Taking the discrete log of both sides, we get ##x + y - z \equiv 0## (mod p). Adding ##z## we get ##x + y \equiv z## (mod p). By definition of the discrete log function, ##0 < x + y - z \le p - 1##. That is, ##x + y = (x + y - z) + m(p - 1)## for some integer m and ##z = (x + y - z) + n(p - 1)## for some integer n.

Am I not understanding something? It seems like the ##\log_g(h_1) + \log_g(h_2) = \log_g(h_1h_2)## isn't always equal for any ##h_1, h_2 \epsilon \mathbb{Z}/p\mathbb{Z}## since it isn't clear that ##m = n##.
 
  • #6
fishturtle1 said:
Let ##h_1 = g^x, h_2 = g^y## and ##h_1h_2 = g^z##. So we have ##g^xg^y = g^{x+y} = g^z##. Multiplying by ##g^{-z}## we get ##g^{x+y-z} = e##, where e is the identity. Taking the discrete log of both sides, we get ##x + y - z \equiv 0## (mod p).
Why do you take the logarithm? Any equation ##a^n=e## in ##\mathbb{Z}/p\mathbb{Z}## means ##n \equiv 0 \operatorname{mod} p##. Therefore ##x+y\equiv z \operatorname{mod} p##. Now all we have to do is to re-substitute what ##x,y,z## mean: ##x=\log_gh_1 \ldots##
 
  • #7
fresh_42 said:
Why do you take the logarithm? Any equation ##a^n=e## in ##\mathbb{Z}/p\mathbb{Z}## means ##n \equiv 0 \operatorname{mod} p##. Therefore ##x+y\equiv z \operatorname{mod} p##. Now all we have to do is to re-substitute what ##x,y,z## mean: ##x=\log_gh_1 \ldots##
If i follow you, you are saying once we have ##x + y \equiv z \operatorname{mod} p##, we just use our variables from before and say ##\log_g(h_1) + \log_g(h_2) \equiv \log_g(h_1h_2) \operatorname{mod} p##?

edit: sorry if your point is going over my head, but i don't see how this would prove the original statement.
Like what if ##\log_g(h_1) + \log_g(h_2) > p - 2##, then ##\log_g(h_1) + \log_g(h_2) \neq \log_g(h_1h_2)##
 
Last edited:
  • #8
fishturtle1 said:
If i follow you, you are saying once we have ##x + y \equiv z \operatorname{mod} p##, we just use our variables from before and say ##\log_g(h_1) + \log_g(h_2) \equiv \log_g(h_1h_2) \operatorname{mod} p##?
Yes.
I don't think that you can lift the equation from ##\mathbb{Z}_p## to ##\mathbb{Z}## other than deliberately choosing the smallest representative, so the equation in ##\mathbb{Z}_p## is all you can get. E.g. if ##\log_g h_i = p-1## what will you do? ##\log_g(h_1)+\log_g(h_2)=2p-2 > p## but according to your definition ##\log_g (h_1h_2) < p##.
edit: sorry if your point is going over my head, but i don't see how this would prove the original statement.
Like what if ##\log_g(h_1) + \log_g(h_2) > p - 2##, then ##\log_g(h_1) + \log_g(h_2) \neq \log_g(h_1h_2)##
 
  • #9
fresh_42 said:
Yes.
I don't think that you can lift the equation from ##\mathbb{Z}_p## to ##\mathbb{Z}## other than deliberately choosing the smallest representative, so the equation in ##\mathbb{Z}_p## is all you can get. E.g. if ##\log_g h_i = p-1## what will you do? ##\log_g(h_1)+\log_g(h_2)=2p-2 > p## but according to your definition ##\log_g (h_1h_2) < p##.
When I wrote ##\mathbb{Z}/p\mathbb{Z}##, I really meant ##\mathbb{F}_p^*##, where ##\mathbb{F}_p^*## = ##\mathbb{Z}/p\mathbb{Z} - \lbrace 0 \rbrace##, my mistake. Also, discrete log is defined as ##\log_g : \mathbb{F}_p^* \rightarrow \mathbb{Z}/(p - 1)\mathbb{Z}##.

it seems we can disprove the statement with a counterexample.

Let ##p = 17##, ##g = 3## where ##g## is a primitive root of ##\mathbb{F}_{17}^*##. We know in this field, ##3^7 = 11, 3^{13} = 12##. Thus ##\log_3(11) + \log_3(12) = 7 + 13 = 20##. Also, ##11 * 12 \equiv 13 \operatorname {mod} 17##. So ##\log_3(132) = \log_3(13) = 4##.
Since ##20 \neq 4##, we can conclude ##\log_g(a) + \log_g(b) \neq \log_g(ab)## for some ##a,b \epsilon \mathbb{F}_p^*##. []
 
  • #10
fishturtle1 said:
When I wrote ##\mathbb{Z}/p\mathbb{Z}##, I really meant ##\mathbb{F}_p^*##, where ##\mathbb{F}_p^*## = ##\mathbb{Z}/p\mathbb{Z} - \lbrace 0 \rbrace##, my mistake. Also, discrete log is defined as ##\log_g : \mathbb{F}_p^* \rightarrow \mathbb{Z}/(p - 1)\mathbb{Z}##.

it seems we can disprove the statement with a counterexample.

Let ##p = 17##, ##g = 3## where ##g## is a primitive root of ##\mathbb{F}_{17}^*##. We know in this field, ##3^7 = 11, 3^{13} = 12##. Thus ##\log_3(11) + \log_3(12) = 7 + 13 = 20##. Also, ##11 * 12 \equiv 13 \operatorname {mod} 17##. So ##\log_3(132) = \log_3(13) = 4##.
Since ##20 \neq 4##, we can conclude ##\log_g(a) + \log_g(b) \neq \log_g(ab)## for some ##a,b \epsilon \mathbb{F}_p^*##. []
Your are right, I missed the zero. From ##g^x\cdot g^y = g^z \,(p)## we must conclude ##x+y=z \,(p-1)## because we have one element less. Now we get ##\log_g (h_1 \cdot h_2) = \log_g (h_1) + \log_g(h_2) \operatorname{mod} p-1##. ##g## generates ##\mathbb{F}^*_p## which has ##p-1## elements.

In your example this is ##7+13 = 4 \,(16)\,##, because ##\log_g e = 16 = 0##.
 
  • #11
fresh_42 said:
Your are right, I missed the zero. From ##g^x\cdot g^y = g^z \,(p)## we must conclude ##x+y=z \,(p-1)## because we have one element less. Now we get ##\log_g (h_1 \cdot h_2) = \log_g (h_1) + \log_g(h_2) \operatorname{mod} p-1##. ##g## generates ##\mathbb{F}^*_p## which has ##p-1## elements.

In your example this is ##7+13 = 4 \,(16)\,##, because ##\log_g e = 16 = 0##.

Thank you for your response.

When you say ##g^x\cdot g^y = g^z \,(p)##, why is there a ##(p)##?

What does ##\log_g (h_1 \cdot h_2) = \log_g (h_1) + \log_g(h_2) \operatorname{mod} p-1## mean? I thought if we are comparing two quantities with "mod p - 1", then we can only say they are congruent, not equal.

I don't understand how ##7 + 13 = 4(16)##. I kind of see that ##\log_g(e) = 16 = 0## but Fermat's Little Theorem tells us ##a^{p - 1} \equiv 1 \operatorname {mod} p## but not that ##a^{p - 1} = 1##. So shouldn't all these ##=##s be ##\equiv##'s?

Another question: ##\max\lbrace \log_g(h_1) + \log_g(h_2)\rbrace = p - 1 + p - 1 = 2p - 2##. And ##\max\lbrace \log_g(h_1h_2)\rbrace = p - 1.## Therefore, we could have the case where ##\log_g(h_1) + \log_g(h_2) = 2p-2 \equiv p - 1 \operatorname (\mod p - 1) = \log_g(h_1h_2)## since ##2p-2 = (p - 1) + 1(p - 1) \rightarrow 2p-2 = (p - 1) \operatorname (\mod p - 1)##.
 
  • #12
##\mathbb{F}_p^* = \langle g \rangle## is a cyclic group with ##p-1## elements, and ##g## generates it. Thus we can write ##h_1=g^x## and ##h_2=g^y## for some ##x,y## with ##0 \leq x,y < p##. Now ##h_1h_2=g^{x+y}=g^z## with a ##0\leq z < p##. This means ##g^{x+y-z}=e## or ##(p-1)\,\vert \,(x+y-z)\,##, which can be written as ##\log_g(h_1h_2)=z=x+y=\log_g(h_1)+\log_g(h_2) \,\operatorname{mod} (p-1)##.

The equation ##g^{x+y}=g^z## is an equation of elements of ##\mathbb{F}_p\,##, which means it holds modulo ##p##.

So for your example:
##11 \cdot 12 = 3^7 \cdot 3^{13} = 132 = 3^4 = 13 \,\operatorname{mod} (17)##
and
##\log_3(11 \cdot 12) = 4 = 20 = 7+13 = \log_3(11) + \log_3(12) \,\operatorname{mod}(16)##
 
Last edited:
  • #13
I think I understand what you mean, here's a proof in based on what you've said in my own words:

Proof: Let ##x = \log_g(h_1), y = \log_g(h_2), z = \log_g(h_1h_2)##. Since ##g## is a primitive root of ##F_p^*##, g must be a generator of ##F_p^*##. Thus ##0 < x, y, z < p##. We have ##g^xg^y = g^{x + y} = g^z##. Multiplying by ##g^{-z}##, we get ##g^{x+y-z} = e## where ##e## is the identity element of ##F_p^*##. But ##e = 1##. So by Fermat's Little Theorem, it follows ##(p - 1) | (x + y - z)##. So ##x + y = z + (p - 1)k## for some integer k. Therefore ##x + y \equiv z (\operatorname {mod} p - 1)##. Since ##x, y, z \epsilon F_p^*##, it follows x + y = z, that is, ##\log_g(h_1) + \log_g(h_2) = \log_g(h_1h_2)##. []
 
  • #14
fishturtle1 said:
I think I understand what you mean, here's a proof in based on what you've said in my own words:

Proof: Let ##x = \log_g(h_1), y = \log_g(h_2), z = \log_g(h_1h_2)##. Since ##g## is a primitive root of ##F_p^*##, g must be a generator of ##F_p^*##. Thus ##0 < x, y, z < p##.
##0 \leq x, y, z## since ##h_i=e## isn't ruled out and ##\log_g e = 0##.
We have ##g^xg^y = g^{x + y} = g^z##. Multiplying by ##g^{-z}##, we get ##g^{x+y-z} = e## where ##e## is the identity element of ##F_p^*##. But ##e = 1##. So by Fermat's Little Theorem, it follows ##(p - 1) | (x + y - z)##. So ##x + y = z + (p - 1)k## for some integer k. Therefore ##x + y \equiv z (\operatorname {mod} p - 1)##. Since ##x, y, z \epsilon F_p^*##, it follows x + y = z, that is, ##\log_g(h_1) + \log_g(h_2) = \log_g(h_1h_2)##. []
The last equations ##x + y = z##, resp. ##\log_g(h_1) + \log_g(h_2) = \log_g(h_1h_2)## are only true modulo the number of elements in the group generated by ##g##, which is ##p-1##. E.g. in your example you have ##7+13=20## but ##\log_3(132)=4##. You cannot lift the equation back into the integers, because in ##\mathbb{Z}## is ##20 \neq 4## whereas in ##\langle 3 \rangle = \mathbb{F}^*_{17}## we have ##20 = 4##.
 
  • #15
fresh_42 said:
##0 \leq x, y, z## since ##h_i=e## isn't ruled out and ##\log_g e = 0##.

The last equations ##x + y = z##, resp. ##\log_g(h_1) + \log_g(h_2) = \log_g(h_1h_2)## are only true modulo the number of elements in the group generated by ##g##, which is ##p-1##. E.g. in your example you have ##7+13=20## but ##\log_3(132)=4##. You cannot lift the equation back into the integers, because in ##\mathbb{Z}## is ##20 \neq 4## whereas in ##\langle 3 \rangle = \mathbb{F}^*_{17}## we have ##20 = 4##.
My confusion has been with the original statement ##\log_g(a) + \log_g(b) = \log_g(ab)## where ##a, b \epsilon \mathbb{F}_p^*##. Since ##a,b \epsilon \mathbb{F}_p^*##, we need to show ##\log_g(a) + \log_g(b) = \log_g(ab) \operatorname {mod} (p - 1)##, like you said.

I"ve been doing this problem as if ##\log_g(a), \log_g(b) \epsilon \mathbb{Z}## and could be outside of ##\mathbb{F}_p^*##. I think that's where my confusion has been..

so my proof would be:
Proof: Let ##x = \log_g(h_1), y = \log_g(h_2), z = \log_g(h_1h_2)##. Since ##g## is a primitive root of ##F_p^*##, g must be a generator of ##F_p^*##. Thus ##0 \le x, y, z < p##. We have ##g^xg^y = g^{x + y} = g^z##. Multiplying by ##g^{-z}##, we get ##g^{x+y-z} = e## where ##e## is the identity element of ##F_p^*##. But ##e = 1##. So by Fermat's Little Theorem, it follows ##(p - 1) | (x + y - z)##. So ##x + y = z + (p - 1)k## for some integer k. Therefore ##x + y \equiv z (\operatorname {mod} p - 1)##. By substitution, ##\log_g(h_1) + \log_g(h_2) \equiv \log_g(h_1h_2) \operatorname {mod} (p - 1)##. So, ##\log_g(h_1) + \log_g(h_2) = \log_g(h_1h_2)## where ##h_1, h_2 \epsilon F_p^*##.[]
 
  • #16
fishturtle1 said:
My confusion has been with the original statement ##\log_g(a) + \log_g(b) = \log_g(ab)## where ##a, b \epsilon \mathbb{F}_p^*##. Since ##a,b \epsilon \mathbb{F}_p^*##, we need to show ##\log_g(a) + \log_g(b) = \log_g(ab) \operatorname {mod} (p - 1)##, like you said.

I"ve been doing this problem as if ##\log_g(a), \log_g(b) \epsilon \mathbb{Z}## and could be outside of ##\mathbb{F}_p^*##. I think that's where my confusion has been..

so my proof would be:
Proof: Let ##x = \log_g(h_1), y = \log_g(h_2), z = \log_g(h_1h_2)##. Since ##g## is a primitive root of ##F_p^*##, g must be a generator of ##F_p^*##. Thus ##0 \le x, y, z < p##. We have ##g^xg^y = g^{x + y} = g^z##. Multiplying by ##g^{-z}##, we get ##g^{x+y-z} = e## where ##e## is the identity element of ##F_p^*##. But ##e = 1##. So by Fermat's Little Theorem, it follows ##(p - 1) | (x + y - z)##. So ##x + y = z + (p - 1)k## for some integer k. Therefore ##x + y \equiv z (\operatorname {mod} p - 1)##. By substitution, ##\log_g(h_1) + \log_g(h_2) \equiv \log_g(h_1h_2) \operatorname {mod} (p - 1)##.
So far so good, and I think, so done as well.
So, ##\log_g(h_1) + \log_g(h_2) = \log_g(h_1h_2)## where ##h_1, h_2 \epsilon F_p^*##.[]
This last sentence isn't necessary. ##h_i \in \mathbb{F}_p## anyway so you only state, that ##h_i \neq 0## resp. that ##\log_g(0)## isn't defined. This information has nothing to do with the proof, only with the definition of ##\log_g\,##. What is important, is that all numbers ##\log_g(h_i)## are in ##\mathbb{F}^*_p##, because this group has less elements, so the equation is modulo ##p-1##. So it doesn't matter where ##h_i## are from at this point, but it matters where ##\log_g(h_i)## are from, which you already said before.
 
  • #17
fresh_42 said:
So far so good, and I think, so done as well.

This last sentence isn't necessary. ##h_i \in \mathbb{F}_p## anyway so you only state, that ##h_i \neq 0## resp. that ##\log_g(0)## isn't defined. This information has nothing to do with the proof, only with the definition of ##\log_g\,##. What is important, is that all numbers ##\log_g(h_i)## are in ##\mathbb{F}^*_p##, because this group has less elements, so the equation is modulo ##p-1##. So it doesn't matter where ##h_i## are from at this point, but it matters where ##\log_g(h_i)## are from, which you already said before.
Ok I understand and took out the last sentence of the proof. Thank you for your time and help on this proof.
 

Related to Can Discrete Logarithms Be Added in Modular Arithmetic?

1. What is the discrete logarithm property?

The discrete logarithm property is a mathematical concept that is used in cryptography. It states that for a given finite group G and a generator g of G, there exists a unique integer x such that g^x = a, where a is an element of G. This property is used in many cryptographic algorithms, such as Diffie-Hellman key exchange and ElGamal encryption.

2. How is the discrete logarithm problem related to the discrete logarithm property?

The discrete logarithm problem is a computational problem that is based on the discrete logarithm property. It involves finding the value of x in the equation g^x = a, given the values of g, a, and the group G. This problem is considered difficult to solve, especially for large values of x and g, and is the basis for many cryptographic algorithms.

3. What is the significance of the discrete logarithm property in cryptography?

The discrete logarithm property is a fundamental aspect of many cryptographic algorithms, as it allows for the secure exchange of information and the creation of secure encryption schemes. It also provides a basis for the creation of one-way functions, which are essential for ensuring the confidentiality and integrity of data in various applications.

4. Are there any known attacks against the discrete logarithm property?

While the discrete logarithm problem is believed to be difficult to solve, there are some known attacks against it. These include the brute force attack, which involves trying every possible value of x until the correct value is found, and the index calculus algorithm, which is a more efficient method for solving the discrete logarithm problem in certain cases.

5. Is the discrete logarithm property used in any other fields besides cryptography?

Yes, the discrete logarithm property has applications in other fields such as number theory, group theory, and coding theory. It is also used in the creation of pseudorandom number generators and in solving certain types of mathematical problems. However, its most significant application is in cryptography, where it plays a crucial role in ensuring the security of data and communication.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
887
  • Calculus and Beyond Homework Help
Replies
21
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
424
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
634
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
632
  • Calculus and Beyond Homework Help
Replies
3
Views
760
  • Calculus and Beyond Homework Help
Replies
1
Views
516
Back
Top