Question 1114082
9^563 mod(907)
:
2^10 = 1024 which is greater than 563 and 2^9 = 512
:
we can now decompose exponent 563 into powers of 2
:
563 = 512 + 51 = 512 + 32 + 16 + 2 + 1
:
9^563 mod(907) = 9^512+32+16+2+1 mod(907) = (9^512 * 9^32 * 9^16 * 9^2 * 9^1) mod(907)
:
now calculate the powers of 9 mod(907) - we will need
:
9^1 = 9 mod(907) = 9
9^2 = 81 mod(907) = 81
9^16 = (9^8)^2 mod(907) = 501^2 mod(907) = 251001 mod(907) = 669
9^32 = (9^16)^2 mod(907) = 669^2 mod(907) = 447561 mod(907) = 410
9^512 = (9^256)^2 mod(907) = 812^2 mod(907) = 659344 mod(907) = 862
:
to verify my calculations using this approach, you need to calculate 9^4, 9^8, 9^64, 9^128, 9^256
:
recall that
:
9^563 mod(907) = (9^512 * 9^32 * 9^16 * 9^2 * 9^1) mod(907) =
:
(862 * 410 * 669 * 81 * 9) mod(907) =
:
(353420 * 54189 * 9) mod(907) =
: 
Note 862 * 410 = 353420, 669 * 81 = 54189
:
(597 * 676 * 9) mod(907) =
:
Note 353420 mod(907) = 597, 54189 mod(907) = 676
:
3632148 mod(907) =
:
520
:
********************
9^563 mod(907) = 520
********************
: