Raised to the power and modulus

Question

Task: $26^{61}(\pmod {851}$ And I stucked with the operation pow(26,61) because it's too hard for me. I read the article about this problem, but I don't quite understand how to solve it. I can convert $61_{10}$ into $111101_2$ and then make something like this

1| $a^1$

0| $a^2=a^1a^1$

1| $a^4=a^2a^2$

1| $a^8=a^4a^4$

1| $a^{16}=a^8a^8$

1| $a^{32}=a^{16}a^{16}$

And then I can calculate it somehow - take expressions that have "1", and ignore expressions that have "0". But this algorithm came without any explanation and example. So, can someone explain how to calculate my task? Also, the task refers to RSA algorithm - signing the message if it's important. Thanks.

Answer 1

You are using the laws of exponents to write $26^{61}=26^{32+16+8+4+1}=26^{32}\cdot26^{16}\cdot 26^8 \cdot 26^4\cdot 26$ Your repeated squaring has calculated each of the values to multiply together. As you want the final result $\pmod {851}$, you can reduce $\pmod {851}$ at every step so you don't ever deal with numbers larger than $851^2$

Answer 2

we can calculate $$26^6\equiv 223 \mod 851$$ thus we get $$(26^6)^{10}=26^{60}\equiv 519\mod 851$$ and $$26^{10}\cdot 26\equiv 519\cdot 26 \equiv 729\mod 851$$