27^400 mod 619
Solution:
Fast Modular Exponentiation
`27^400" mod "619`
Comparing with `A^B" mod "C`
We get `A=27,B=400,C=619`
Step 1: Divide B into powers of 2 by writing it in binary
`400=110010000` in binary
`400=2^4+2^7+2^8`
`400=16+128+256`
`27^400" mod "619=27^((16+128+256))" mod "619`
`27^400" mod "619=(27^16*27^128*27^256)" mod "619`
Step 2: Calculate mod C of the powers of two <= B
`27^1" mod "619=27" mod "619=27`
`27^2" mod "619=(27^1*27^1)" mod "619=(27^1" mod "619*27^1" mod "619)" mod "619=(27*27)" mod "619=729" mod "619=110`
`27^4" mod "619=(27^2*27^2)" mod "619=(27^2" mod "619*27^2" mod "619)" mod "619=(110*110)" mod "619=12100" mod "619=339`
`27^8" mod "619=(27^4*27^4)" mod "619=(27^4" mod "619*27^4" mod "619)" mod "619=(339*339)" mod "619=114921" mod "619=406`
`27^16" mod "619=(27^8*27^8)" mod "619=(27^8" mod "619*27^8" mod "619)" mod "619=(406*406)" mod "619=164836" mod "619=182`
`27^32" mod "619=(27^16*27^16)" mod "619=(27^16" mod "619*27^16" mod "619)" mod "619=(182*182)" mod "619=33124" mod "619=317`
`27^64" mod "619=(27^32*27^32)" mod "619=(27^32" mod "619*27^32" mod "619)" mod "619=(317*317)" mod "619=100489" mod "619=211`
`27^128" mod "619=(27^64*27^64)" mod "619=(27^64" mod "619*27^64" mod "619)" mod "619=(211*211)" mod "619=44521" mod "619=572`
`27^256" mod "619=(27^128*27^128)" mod "619=(27^128" mod "619*27^128" mod "619)" mod "619=(572*572)" mod "619=327184" mod "619=352`
Step 3: Use modular multiplication properties to combine the calculated mod C values
`27^400" mod "619`
`=(27^16*27^128*27^256)" mod "619`
`=(27^16" mod "619*27^128" mod "619*27^256" mod "619)" mod "619`
`=(182*572*352)" mod "619`
`=36644608" mod "619`
`=427`
`:.27^400" mod "619=427`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
