1. ## Decoding a message

I could use all of the help I can get with this...it did not make any sense to me when my teacher explained it. Ok so here's the problem

Let p=13 and q=23. Let e=5. Decode the message: When I think about my professor, I think about 69,214,69.

1. First find d with de congruent to 1 mod((p-1)(q-1)).

2. Now, find 69^d mod((13)(23)) and 214^d mod((13)(23)). I'l give you 214^d is congruent to 15 mod((13)(23)).

3. Write decoded message in terms of letters.

Thank you SO MUCH for any help with this.

***UPDATE: Ok, so I think that d=53. Verify this if you'd like. So now, what I need to do is figure out 69^(53)=____ mod((13)(23)). I am not sure how to do this...the large exponent is throwing me off, so it'd be nice if someone could explain that.

2. Originally Posted by steph3824
I could use all of the help I can get with this...it did not make any sense to me when my teacher explained it. Ok so here's the problem

Let p=13 and q=23. Let e=5. Decode the message: When I think about my professor, I think about 69,214,69.

1. First find d with de congruent to 1 mod((p-1)(q-1)).

2. Now, find 69^d mod((13)(23)) and 214^d mod((13)(23)). I'l give you 214^d is congruent to 15 mod((13)(23)).

3. Write decoded message in terms of letters.

Thank you SO MUCH for any help with this.

***UPDATE: Ok, so I think that d=53. Verify this if you'd like. So now, what I need to do is figure out 69^(53)=____ mod((13)(23)). I am not sure how to do this...the large exponent is throwing me off, so it'd be nice if someone could explain that.
What you need is modular exponentiation

Essentially, you use $69^{a+b}=69^{a}69^b$ and substitute each term with its residue modulo 13*23, so you have smaller numbers. Optimally, using decomposition in base 2, you reduce to power 2 (and powers of 2, by induction). Read the wikipedia (or google for modular exponentiation if it is not clear enough).