Modulo operation of large powers

796 Views Asked by At

I came through this property in a cryptography book.

$(ab)\bmod n=\bigl((a \bmod n)(b \bmod n)\bigr)\bmod n$.

There is an example in the book,

$10^n\bmod 3= (10\bmod n)^n$.

Now if I have to calculate $8^15 \bmod 17$ can I calculate $8 \bmod 17$ and multiply the answer (which is $9$) $15$ times, so the answer becomes $16$?

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, except that $8 \bmod 17$ is just $8$. You can also continually square to save some operations. So you get:

$$8 \equiv 8 \pmod {17},$$ $$8^2 = 64 \equiv 13 \pmod {17},$$ $$8^4 \equiv 13^2 = 169 \equiv 16 \pmod {17},$$ $$8^8 \equiv 16^2 = 256 \equiv 1 \pmod {17},$$ $$8^{15} = 8^8 \cdot 8^4 \cdot 8^2 \cdot 8 \equiv 1 \cdot 16 \cdot 13 \cdot 8 = 1664 \equiv 15 \pmod {17}.$$