Calculate $142^{381}$ mod $773$ without a calculator . Calculate $142^{381}$ mod $773$ without a calculator .
Attempt:
$$142^{(3\cdot 127)}=142^{381}$$
By try some number's
$$142^1\equiv142\pmod{773}$$
$$142^2\equiv66\pmod{773}$$
$$142^3\equiv96\pmod{773}$$
Lets check the gcd between $773,142$
$$\gcd(773,142)$$
$$773=142\cdot 5+63$$
$$142=63\cdot 2+16$$
$$63=16\cdot3+15$$
$$16=15\cdot 1+1$$
$$15=1\cdot15+0$$
$$\gcd(773,142)=1$$
How to find the answer from here ?
 A: Easily we verify $\,773\,$ is prime. So $\!\bmod 773\!:\, $ if $\,142 \equiv a^2\,$ then $142^{386}\equiv a^{772}\equiv 1\,$ by Fermat, so $\,142^{381}\equiv 142^{386} 142^{-5}\equiv (142^{-1})^5.\,$ By here $\,142^{-1}\equiv 7^2\,$ so $\,142\equiv 7^{-2}\,$ is indeed a square, so $\,142^{381}\equiv 49^5\equiv 49(82)^2 \equiv 49(-223)\equiv 178.\,$ Total time: a few minutes by hand.
A: The standard algorithmic solution to the "modular exponentiation" problem is to use "Square and Multiply Algorithm". Let me illustrate:
Suppose you need to calculate $$x^c \bmod n$$
Represent the exponent $c$ in binary:
$$c = \sum_{i=0}^{l-1} c_i 2^i$$ where $c_i$ is $0$ or $1$ and $0 \leq i \leq l-1$
Then use the following algorithm:
SAM (x, c, n){
z = 1

for i = l-1 downto 0 {
   z = z^2 mod n
   if (c_i = 1)
      z = zx mod n
   }

return z
}

Note that there are always $l$ squarings. The number of multiplications is equal to the number of $1$'s in the binary representation of $c$, which is an integer between $0$ and $l$. Thus the total number of modular multiplications is at least $l$ and at most $2l$
I used the above algorithm and found the value $178$
$x = 142, c = 381 = \{101111101\}, n = 773$
Here $l = 9$,
hence the number of squarings $= l = 9$ and
number of multiplications $ = $ number of $1$'s in the binary representation of $381 = 7$
SQUARE: 1
MULTIPLY: 142
SQUARE: 66
SQUARE: 491
MULTIPLY: 152
SQUARE: 687
MULTIPLY: 156
SQUARE: 373
MULTIPLY: 402
SQUARE: 47
MULTIPLY: 490
SQUARE: 470
MULTIPLY: 262
SQUARE: 620
SQUARE: 219
MULTIPLY: 178
===============
FINAL: 178

