Exercise 2.3 from "Introduction to Mathematical Cryptography"
Let $p$ be a prime and $g$ an element in $\mathbb{F}_p^*$ of order $r$.
(a) Suppose that $x = a$ and $x = b$ are both integer solutions to the equation $g^x\equiv_p h$. Prove that $a\equiv_r b$.
(b) Prove that $\log_g{(h_1h_2)}\equiv_r \log_g{(h_1)} + \log_g{(h_2)}$ for all $h_1, h_2\in\mathbb{F}_p^*$ such that $g^x\equiv_p h_1$ and $g^x\equiv_p h_2$ have integer solutions.
(c) Prove that $\log_g{(h^n)}\equiv_r n\cdot\log_g{(h)}$ for all $h\in \mathbb{F}_p^*$ such that $g^x\equiv_p h$ has an integer solution and $n\in \mathbb{Z}$.
Solution:
(a) Suppose $x=a$ and $x=b$ are both integer solutions to the equation $g^x\equiv_p h$. Then we have that $g^a\equiv_p h$ and $g^b\equiv_p h$. But this means that $g^a\equiv_p h\equiv_p g^b$. Multiplying the equation by $g^{-b}$, we get that $g^{a-b}\equiv_p 1$. By fermats little theorem this is true if and only if $r\mid a-b$. Hence $a\equiv_r b$.
I found a solution manual and I had almost done everything correct but I don't get the last step. They never said why they can conclude that $r\mid a-b$ so I just said something (fermats little theorem ;), (which is also the step I never managed to take), no idea why though. Would be happy if someone could tell me.
(b) Let's define $x_1=\log_g{(h_1)}$ and $x_2=\log_g{(h_2)}$. That is $g^{x_1}=h_1$ and $g^{x_2}=h_2$. Now, since $h_1 h_2=g^{x_1} g^{x_2}=g^{x_1+x_2}$. Now we have that $h_1 h_2=g^{x_1+x_2}\Leftrightarrow \log_g{(h_1 h_2)}=x_1+x_2=\ln=kog_g{(h_1)}+\log_g{(h_2)}$ Which ends the proof.
(c) I would like to do the last part by induction but I'm not really good at that.
BASE CASE:
n=1 is trivial.
Now suppose it's true for $n=k$ and we wan't to show it's true for $n=k+1$. We then have $\log_g{(h^{k+1})}=\log_g{(h^{k}h)}$ and from here I don't really know where to go.
Hope someone can help me, thanks :)
(a) you get $g^{a-b}=1$ mod $p$. By definition, $r$ "the order of $g$" is the smallest (for the divisor relation) positive integer verifying $g^k=1$ mod $p$. Since $a-b$ also verifies this relation and since $r$ is the smallest, it follows that $r$ must divide $a-b$. No need for Fermat's little theorem, it would only give you that $r$ divides $p-1$.
(b) ok.
(c) Let us prove that $log_g(h^k)=k.log_g(h)$ for $k\geq 0$ first by induction.
If $k=0$ then $log_g(g^k)=log_g(g^0)=log_g(1_G)=0$ by definition so we are good.
You have that $log_g(h^{k+1})=log_g(h^kh)=log_g(h^k)+log_g(h)$ because of (b). Now apply your induction hypothesis to $log_g(h^k)$ and conclude.
Finally show that $log_g(h^{-1})=-log_g(h)$ and conclude that $log_g(h^k)=k.log_g(h)$ for $k\in\mathbb{Z}$.