|
|
|
|
|
|
|
|
Solution
|
Solution provided by AtoZmath.com
|
|
|
|
Fast modular exponentiation calculator
|
1. Chinese Remainder Theorem
 1. x=2 (mod 5),x=3 (mod 7),x=10 (mod 11)
2. x=4 (mod 10),x=6 (mod 13),x=4 (mod 7),x=2 (mod 11)
3. x=6 (mod 11),x=13 (mod 16),x=9 (mod 21),x=19 (mod 25)
4. 3x=7 (mod 10)
5. 3x=6 (mod 12)
6. 2x=5 (mod 7),3x=4 (mod 8)
7. 2x=1 (mod 3),3x=5 (mod 8)
8. 2x=6 (mod 14),3x=9 (mod 15),5x=20 (mod 60)
9. x=3 (mod 7),x=3 (mod 5),x=4 (mod 12)
10. x=1 (mod 4),x=0 (mod 6)
2. Modulo
1. 42 mod 5
2. 3^302 mod 5
3. 19^24 mod 21
4. 7^106 mod 143
5. 27^400 mod 619
6. 42^-1 mod 5
3. Extended Euclidean Algorithm, Euclid's Algorithm, Modular multiplicative inverse
1. 11 and 12
2. 7 and 11
3. 3 and 7
|
Example1. 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` |
|
|
|
|
|
