# 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^*$$?

• $\mod p$, This was intended to be an educative answer : Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y? if not clear, please indicate, Also see Does classifying an integer as a discrete log require it be part of a multiplicative group? Dec 20 '20 at 14:00
• So this answer, where user @fgrieu♦ suggested that operations with discrete logarithm are performed by $\bmod{(p-1)}$ is wrong?
– Jan
Dec 20 '20 at 14:39
• It is the power, see Euler's Theorem. You should take an introduction to abstract algebra course. Dec 20 '20 at 14:42
• So, $a^k \equiv b \pmod p$, but $k\in \mathbb{Z}_{p-1}$?
– Jan
Dec 20 '20 at 14:58
• Yes and no. $a^{\varphi(k)} = 1 \bmod n$ where $k \in \mathbb Z$ and $\gcd(a,p)=1$. There is a representative of $k \in \varphi(n)$ that is $k' = k + t\cdot \varphi(n)$. Since $n$ is a prime than $\varphi(n) = n-1$. See a recent RSA question about Euler's theorem. Dec 20 '20 at 15:01

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. Dec 20 '20 at 23:06