517 mod 23
First step: Converting the power to binary. Dividing by 2 we get the following.
2 |
17 |
1 |
|
8 |
0 |
4 |
0 |
|
2 |
0 |
|
1 |
1 |
|
0 |
|
We get the following binary:: (10001)2
Step 2: Using the repeated square algorithm.
52^0 mod 23 à 5
Squaring the result we get,
Again, squaring the result
22 mod 23 à 4 mod 23 à 4
Squaring again,
42 mod 23 à 16 mod 23 à 16
Squaring result again,
162 mod 23 à 256 mod 23 à 3
Now, raising to its successive power.
(31*160*40*20*51) mod 23
(3*1*1*1*5) mod 2
15 mod 23 = 15
In this way, repeated sqauring algorithm can be used to calculate the mod of a higher number without using a calculator.