Understanding Modulo $(p^n)$ calculation by Binary method

Question

I wanted to find $2^{133}\equiv -5\mod 133$
I know by calculating some power trick we can simplifies thing but I encountered In Number Theory by Jones book ABove can be find using binary method I tried to understand but not get that.

Please Help me to understand above

Answer 1

This is the https://en.wikipedia.org/wiki/Modular_exponentiation#Left-to-right_binary_method: if a bit is $1$ apply $f=x^2 \bmod {133}$ else apply $g=ax^2 \bmod {133}$. The binary representation of $133$ is $10000101$. Here are the single steps for computation, where the $x$ values are reduced modulo $133$ to give the smallest residue (e.g. $100=-33 \pmod {133}$):

Bit  Op    x     
           1
1    g     1^2 * 2 = 2
0    f     2^2 = 4
0    f     4^2 = 16
0    f     16^2 = 256 = 123 = -10
0    f     (-10)^2 = 100 = -33 
1    g     2*(-33)^2 = 2178 = 50
0    f     50^2 = 2500 = 106 = -27
1    g     2*(-27)^2 = 1458 = 128 = -5