Calculate mod in RSA algorithm

Question

How to calculate

Mod of a big number in RSA

Like 5 raise to power 13 mod 77

Comments

Who said that virtual calculators are not allowed. They are provided in the exam interface

---

@Gupta731 For huge computations like, one in https://gateoverflow.in/39588/gate2016-2-29. Virtual Calc fails.

---

Limitations of Calc:

 

Answer 1

To find (5^13)mod77, first divide the problem as follows:

(5*5*5*...*5)mod77

take 5 in pairs of three , and leaves a single 5. Let t=(5*5*5)mod77=125mod77=48

=> The result becomes:=  (t*t*t*t*5)mod77

Now we know (a*b)mod c = ((amod c)*(bmod c))mod c

=> (48mod77*48mod77*48mod77*48mod77*5mod77)mod77

=>((-29)*(-29)*(-29)*(-29)*5)mod77

Find out ((-29)*(-29))mod77 = (841)mod77 = 71

Now the problem is reduced to (71*71*5)mod77         {71mod77 is -6}

so the result is  (-6*-6*5)mod77 = 180mod77 = 26.