You are viewing a single comment's thread. Return to all comments →
So, in our next step we need the help of higher powers, or we need to calculate ab %m.
= 1 % m , b == 0 a^b = a*(a^(b-1)) % m , odd b = a'^2 % m , even b where a' = a^(b/2)
Suppose we need to calculate 2100 % 11.
2^100 = (2^50)^2 (mod 11) 2^50 = (2^25)^2 (mod 11) 2^25 = 2*(2^24) (mod 11) 2^24 = (2^12)^2 (mod 11) 2^12 = (2^6)^2 (mod 11) 2^6 = (2^3)^2 (mod 11) 2^3 = 2*(2^2) (mod 11) 2^2 = (2^1)^2 (mod 11) 2^1 = 2*(2^0) (mod 11) 2^0 = 1
Now popping whole stack,
2^1 = 2*1 = 2 (mod 11) 2^2 = 2^2 = 4 (mod 11) 2^3 = 2*4 = 8 (mod 11) 2^6 = 8^2 = 64 = 9 (mod 11) 2^12 = 9^2 = 81 = 4 (mod 11) 2^24 = 4^2 = 16 = 5 (mod 11) 2^25 = 2*5 = 10 (mod 11) 2^50 = 10^2 = 100 = 1 (mod 11) 2^100 = 1^2 = 1 (mod 11)
Sherlock and Permutations
You are viewing a single comment's thread. Return to all comments →
So, in our next step we need the help of higher powers, or we need to calculate ab %m.
Suppose we need to calculate 2100 % 11.
Now popping whole stack,