# By what modulo calculations with discrete logarithms are performed?

For odd prime $$p$$, I have been given a group $$\mathbb{Z}_p^*$$ of all invertible elements from $$\mathbb{Z}_p$$. Basically, $$\mathbb{Z}_p^* = \{1,2,\ldots , p-1 \}$$. I also have $$a$$ and $$b$$, which are two generators of $$\mathbb{Z}_p^*$$. My question is, by what modulo calculations with the discrete logarithm are performed for $$\mathbb{Z}_p^*$$? Or in other words, does it hold: $$a^k \equiv b \pmod p$$ $$k \equiv \log_a b \pmod{p}$$ Or does it hold: $$a^k \equiv b \pmod{p-1}$$ $$k \equiv \log_a b \pmod{p-1}$$

And also, a followed up question:
If $$\mathbb{Z}_p^*$$, $$a$$ and $$b$$ are as described above, does it holds, that if $$k=\log_a b$$ then $$k\in \mathbb{Z}_p^*$$?

Neither of the question's alternative hold.

For any $$n>1$$, and any $$a$$ with $$\gcd(a,n)=1$$, $$a^k \equiv b \pmod n\quad\iff\quad k \equiv \log_a b \pmod{\text{ord}_n(a)}$$

where $$\text{ord}_n(a)$$ is the order of $$a$$ in the multiplicative group $$\mathbb Z_n^*$$, that is the smallest $$r\ge1$$ with $$a^r\equiv1\pmod n$$.

The order of an element divides the order of the group, which is $$\varphi(n)$$ for group $$\mathbb Z_n^*$$, where $$\varphi$$ is Euler's totient function. Therefore $$k\equiv\log_a b \pmod{\varphi(n)}\quad\implies\quad a^k \equiv b \pmod n$$

When $$a$$ is a generator of $$\mathbb Z_n^*$$, which is testable as $$a^{\varphi(n)/q}\not\equiv1\bmod p$$ for every prime $$q$$ dividing $$\varphi(n)$$, we simply have $$a^k \equiv b \pmod n\quad\iff\quad k \equiv \log_a b \pmod{\varphi(n)}$$

Restating this for prime $$p$$, and any $$a$$ with $$a\not\equiv0\pmod p$$, $$k\equiv\log_a b \pmod{(p-1)}\quad\implies\quad a^k \equiv b \pmod p$$ and, for the lowest $$r\ge1$$ dividing $$p-1$$ such that $$a^r\equiv1\pmod p$$, $$a^k \equiv b \pmod p\quad\iff\quad k \equiv \log_a b \pmod{r}$$

When $$a$$ is a generator of $$\mathbb Z_p^*$$, which is testable as $$a^{(p-1)/q}\not\equiv1\bmod p$$ for every prime $$q$$ dividing $$(p-1)$$, we simply have $$a^k \equiv b \pmod p\quad\iff\quad k \equiv \log_a b \pmod{(p-1)}$$

• Good, another educative answer. – kelalaka Dec 20 '20 at 23:06