Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Want to show that, if $P$ is the original plaintext block and $(\gamma^a)'$ is the inverse of $\gamma^a$ modulo $p$, then $$(\gamma^a)'\delta \equiv P \pmod p$$

So, we have:

  • $\gamma = \alpha^k \pmod p$
  • $\delta = P(\alpha^a)^k mod p$
  • $C = (\gamma, \delta)$

Plugging the values above to $(\gamma^a)'\delta$ $$(\gamma^a)'\delta = ((\alpha^k)^a)' P(\alpha^a)^k \equiv P \pmod p$$ $$((\alpha^k)^a)' P(\alpha^a)^k \equiv ((\alpha^k)^a)' (\alpha^a)^k \equiv 1 \pmod p$$

Not sure if I'm doing this correctly...

share|cite|improve this question
Ok. What have you tried? – mixedmath Apr 17 '13 at 0:32
up vote 2 down vote accepted

Hint: We want to show that if $(\gamma^a)'$ is the inverse of $\gamma^a$ modulo $p$, then $(\gamma^a)'\delta \equiv P \pmod p$.

We have:

  • $\gamma = \alpha^k \pmod p$

  • $\delta = P(\alpha^a)^k \pmod p$

  • $C = (\gamma, \delta)$

So, we need to find: $(\gamma^a)'\delta$

Plug in the above values and what do end up with?

$$(\gamma^a)'\delta = ((\alpha^k)^a)' P(\alpha^a)^k \equiv \alpha^{-ak} \cdot \alpha^{ak} P \equiv P \pmod p $$

What allows me to swap and cancel those values?

share|cite|improve this answer
...nice job here, too! – amWhy Apr 17 '13 at 1:06
Thanks for responding, but still unsure about how to proceed. I've update the post with what you've suggested but I'm not sure if I'm going in the right direction. – Tejen Shrestha Apr 17 '13 at 2:11
@Amzoti Ok, so can you divide both sides by $\alpha^{-ak}$?. If so, it seems like I end up with $1 \equiv 1 \pmod p$. – Tejen Shrestha Apr 17 '13 at 2:25
@icanc: Huh? the RHS is our final result and is P. Why are you dividing anything from the left of that? Maybe just a slip up? Regards – Amzoti Apr 17 '13 at 2:28

Your Answer


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.