Solve 1113 mod 53 using:
Modular exponentiation
Build an algorithm:
n is our exponent = 13
y = 1 and u ≡ 11 mod 53 = 11
See here
n = 13 is odd
Since 13 is odd, calculate (y)(u) mod p
(y)(u) mod p = (1)(11) mod 53
(y)(u) mod p = 11 mod 53
11 mod 53 = 11
Reset y to this value
Determine u2 mod p
u2 mod p = 112 mod 53
u2 mod p = 121 mod 53
121 mod 53 = 15
Reset u to this value
Cut n in half and take the integer
13 ÷ 2 = 6
n = 6 is even
Since 6 is even, we keep y = 11
Determine u2 mod p
u2 mod p = 152 mod 53
u2 mod p = 225 mod 53
225 mod 53 = 13
Reset u to this value
Cut n in half and take the integer
6 ÷ 2 = 3
n = 3 is odd
Since 3 is odd, calculate (y)(u) mod p
(y)(u) mod p = (11)(13) mod 53
(y)(u) mod p = 143 mod 53
143 mod 53 = 37
Reset y to this value
Determine u2 mod p
u2 mod p = 132 mod 53
u2 mod p = 169 mod 53
169 mod 53 = 10
Reset u to this value
Cut n in half and take the integer
3 ÷ 2 = 1
n = 1 is odd
Since 1 is odd, calculate (y)(u) mod p
(y)(u) mod p = (37)(10) mod 53
(y)(u) mod p = 370 mod 53
370 mod 53 = 52
Reset y to this value
Determine u2 mod p
u2 mod p = 102 mod 53
u2 mod p = 100 mod 53
100 mod 53 = 47
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
1113 mod 53 ≡ 52
Solve 1113 mod 53 using:
the Successive Squaring Method
Step 1: Convert our power of 0 to binary notation:
Using our binary calculator, we see that 0 in binary form is
The length of this binary term is 0, so this is how many steps we will take for our algorithm below
Step 2: Construct Successive Squaring Algorithm:
| i | a | a2 | a2 mod p |
|---|
