1
$\begingroup$

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

$\endgroup$
5
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Good, another educative answer. $\endgroup$ – kelalaka Dec 20 '20 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.