factor = n mod 10^k result = 1 while (n != 0) if (n is odd) then result = (result * factor) mod 10^k factor = (factor * factor) mod 10^k n >>= 1