Hex number exponentiation - modulo

[Mr Peanut]

I have a hexadecimal number: 0x83

I need to determine 0x83^11 mod 15. Where the 11 and 15 are decimal.

I figured 0x83 = 131 decimal.

131^11 = 194977389846841709335931.

194977389846841709335931 mod 15 = 11

11 = 0x0b

Does that seem right?

 

[obafgkmrns]

That's right, but you can get there more easily. In fact you can do it in your head.

Recognize that 131 = 11 mod 15.
So 131^2 mod 15 = 11^2 mod 15. But 11^2 = 1 mod 15.
Since 131^10 = (131^2)^5, you know that 131^10 = 1 mod 15.
Finally, 131*(131^10) = 11*1 mod 15 = 11.