1
$\begingroup$

I have a question about the Pohlig-Hellman Algorithm for the discrete log problem. I understand the concept, but doing the exact calculations I get confused at one point; to illustrate, let's look at the equation $2^x=3$ in the group $(\mathbb{Z}/29\mathbb{Z})^*$.

If my calculations are correct, we get that $x \equiv 1$ in a subgroup of order 4 and $x \equiv 5$ in a subgroup of order 7. Using the isomorphism $((\mathbb{Z}/29\mathbb{Z})^*, \cdot) \cong (\mathbb{Z}/28\mathbb{Z}, +)$, we get the equations $$x \equiv 1 \mod 4 \\ x \equiv 5 \mod 7$$ which is then pasted together using the Chinese Remainder Theorem to get $x \equiv 5 \mod 28$.

Now here is where I am confused: The results x=1 and x=5 are derived using calculations in $((\mathbb{Z}/29\mathbb{Z})^*, \cdot)$. Why can we just 'transfer' the very same numbers to the respective subgroups of $(\mathbb{Z}/28\mathbb{Z}, +)$, when we do not know the image of these elements under the isomorphism? Is it just because we are technically already in the group $(\mathbb{Z}/28\mathbb{Z}, +)$ when we are dealing with the exponents? Or am I missing something more crucial here?

Thank you in advance for any kind of advice.

$\endgroup$
1
$\begingroup$

Because $x$ is defined modulo $28$ ($2^{28} = 2^0$ in $(\mathbf{Z}/29\mathbf{Z})^*$), you can view $x$ as an element of $\mathbf{Z}/28\mathbf{Z}$, while $2$ and $3$ are elements of $(\mathbf{Z}/29\mathbf{Z})^*$.

$\endgroup$

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.