1. 3^302 mod 5
Solution:
Fast Modular Exponentiation
3^302" mod "5
Comparing with A^B" mod "C
We get A=3,B=302,C=5
Step 1: Divide B into powers of 2 by writing it in binary
302=100101110 in binary
302=2^1+2^2+2^3+2^5+2^8
302=2+4+8+32+256
3^302" mod "5=3^((2+4+8+32+256))" mod "5
3^302" mod "5=(3^2*3^4*3^8*3^32*3^256)" mod "5
Step 2: Calculate mod C of the powers of two <= B
3^1" mod "5=3" mod "5=3
3^2" mod "5=(3^1*3^1)" mod "5=(3^1" mod "5*3^1" mod "5)" mod "5=(3*3)" mod "5=9" mod "5=4
3^4" mod "5=(3^2*3^2)" mod "5=(3^2" mod "5*3^2" mod "5)" mod "5=(4*4)" mod "5=16" mod "5=1
3^8" mod "5=(3^4*3^4)" mod "5=(3^4" mod "5*3^4" mod "5)" mod "5=(1*1)" mod "5=1" mod "5=1
3^16" mod "5=(3^8*3^8)" mod "5=(3^8" mod "5*3^8" mod "5)" mod "5=(1*1)" mod "5=1" mod "5=1
3^32" mod "5=(3^16*3^16)" mod "5=(3^16" mod "5*3^16" mod "5)" mod "5=(1*1)" mod "5=1" mod "5=1
3^64" mod "5=(3^32*3^32)" mod "5=(3^32" mod "5*3^32" mod "5)" mod "5=(1*1)" mod "5=1" mod "5=1
3^128" mod "5=(3^64*3^64)" mod "5=(3^64" mod "5*3^64" mod "5)" mod "5=(1*1)" mod "5=1" mod "5=1
3^256" mod "5=(3^128*3^128)" mod "5=(3^128" mod "5*3^128" mod "5)" mod "5=(1*1)" mod "5=1" mod "5=1
Step 3: Use modular multiplication properties to combine the calculated mod C values
3^302" mod "5
=(3^2*3^4*3^8*3^32*3^256)" mod "5
=(3^2" mod "5*3^4" mod "5*3^8" mod "5*3^32" mod "5*3^256" mod "5)" mod "5
=(4*1*1*1*1)" mod "5
=4" mod "5
=4
:.3^302" mod "5=4
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
