Enter Modular Exponentiation
Solve 39 mod 11 using:
Modular exponentiation
Build an algorithm:
n is our exponent = 9
y = 1 and u ≡ 3 mod 11 = 3
See here
n = 9 is odd
Since 9 is odd, calculate (y)(u) mod p
(y)(u) mod p = (1)(3) mod 11
(y)(u) mod p = 3 mod 11
3 mod 11 = 3
Reset y to this value
Determine u2 mod p
u2 mod p = 32 mod 11
u2 mod p = 9 mod 11
9 mod 11 = 9
Reset u to this value
Cut n in half and take the integer
9 ÷ 2 = 4
n = 4 is even
Since 4 is even, we keep y = 3
Determine u2 mod p
u2 mod p = 92 mod 11
u2 mod p = 81 mod 11
81 mod 11 = 4
Reset u to this value
Cut n in half and take the integer
4 ÷ 2 = 2
n = 2 is even
Since 2 is even, we keep y = 3
Determine u2 mod p
u2 mod p = 42 mod 11
u2 mod p = 16 mod 11
16 mod 11 = 5
Reset u to this value
Cut n in half and take the integer
2 ÷ 2 = 1
n = 1 is odd
Since 1 is odd, calculate (y)(u) mod p
(y)(u) mod p = (3)(5) mod 11
(y)(u) mod p = 15 mod 11
15 mod 11 = 4
Reset y to this value
Determine u2 mod p
u2 mod p = 52 mod 11
u2 mod p = 25 mod 11
25 mod 11 = 3
Reset u to this value
Cut n in half and take the integer
1 ÷ 2 = 0
Because n = 0, we stop
We have our answer
