Question

what is the easiest shortest method to calculate:

(4^(103)) mod 517

please explain steps in detail...

Answer 1

It can be done using fast modular exponentiation method:

(4^(103)) mod 517.

Step 1:

write binary equivalent for 103

1100111

103= 2^0+2^1+2^2+2^5+2^6

=1+2+4+32+64

(4^(103)) mod 517 = (4^(1+2+4+32+64) mod 517)

= (4^1*4^2*4^4*4^32*4^64) mod 517

Step 2:

4^1 mod 517 = 4

4^2 mod 517 = ( 4^1 * 4^1) mod 517

= (4^1 mod 517 * 4^1 mod 517) mod 517

= (4 * 4) mod 517

4^2 mod 517 = 16 mod 517= 16

4^4 mod 517 = (4^2*4^2) mod 517

= (16 *16) mod 517

4^4 mod 517 = 256 mod 517 = 256

4^8 mod 517 = (4^4*4^4) mod 517

= (256*256) mod 517

4^8 mod 517= 394

4^16 mod 517= ( 4^8 *4^8) mod 517

4^16 mod 517= ( 394*394) mod 517

= 136

4^32 mod 517= (4^16*4^16) mod 517

= (136*136) mod 517

= 401

4^64 mod 517= (4^32*4^32) mod 517

(401*401) mod 517=14

Step 3:

(4^1*4^2*4^4*4^32*4^64) mod 517

=(4^1 mod 517 * 4^2 mod 517 * 4^4 mod 517 * 4^32 mod 517 * 4^64 mod 517) mod 517

=(4*16*256*401*14) mod 517 = 88386816 mod 517

= 496