Can Discrete Logarithms Be Added in Modular Arithmetic?

[fishturtle1]

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}$.

 

[fresh_42]

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$ ?

 

[fishturtle1]

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.

 

[fresh_42]

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$.

 

[fishturtle1]

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$.

 

[fresh_42]

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$

 

[fishturtle1]

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)$

 

[fresh_42]

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)$

 

[fishturtle1]

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^*$. []

 

[fresh_42]

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$.

 

[fishturtle1]

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)$.

 

[fresh_42]

$\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)$

 

[fishturtle1]

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)$. []

 

[fresh_42]

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$.

 

[fishturtle1]

$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^*$.[]

 

[fresh_42]

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.

 

[fishturtle1]

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.