Question

Compute
x Such that
10000
(mod 19)​

Answer 1

Answer:

Using modular multiplication rules:

i.e. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C

We can use this to calculate 7^256 mod 13 quickly

7^1 mod 13 = 7

7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13

We can substitute our previous result for 7^1 mod 13 into this equation.

7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10

7^2 mod 13 = 10

7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13

We can substitute our previous result for 7^2 mod 13 into this equation.

7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9

7^4 mod 13 = 9

7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13

We can substitute our previous result for 7^4 mod 13 into this equation.

7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3

7^8 mod 13 = 3

We continue in this manner, substituting previous results into our equations.

...after 5 iterations we hit:

7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13

7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9

7^256 mod 13 = 9

This has given us a method to calculate A^B mod C quickly provided that B is a power of 2.

However, we also need a method for fast modular exponentiation when B is not a power of 2.