Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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})^*$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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