Discrete Logarithm is Homomorphic

Question

Recall that $l_g(h) ($mod$ p)$ is the discrete log to base $g$ mod $p$, that is, $g^{l_g(h)} \equiv h($mod$ p)$.

Let $p$ be prime, and $g$ a primitive root $($mod$ p)$. Show that: $l_g(h_1h_2)$ = $l_g(h_1) + l_g(h_2)$ for all $h_1, h_2$ in $Z_p^*$

I tried some algebra tricks, starting with the 2 equations:

$g^{l_g(h_1h_2)} \equiv h_1h_2($mod$ p)$

$g^{l_g(h_1) + l_g(h_2)} \equiv h_1 + h_2($mod$ p)$

But I did not get anywhere with any of it, any help would be appreciated!

Answer 1

Recall that $l_g(h) ($mod$ p)$ is the discrete log to base $g$ mod $p$, that is, $g^{l_g(h)} \equiv h($mod$ p)$.

This is a confusing notation, let simplify.

• let $x$ is the discrete log of $h$ to base $g \pmod p$, that is, $g^{x} \equiv h \pmod p$, and
• take $y$ is the discrete log of $h'$ to base $g \pmod p$, that is, $g^{y} \equiv h' \pmod p$.

Now, consider $g^x \cdot g^y \equiv g^{x+y} \equiv h \cdot h'$.