Алгоритм быстрого возведения в степень с реализацией на Java
Алгоритм быстрого возведения в степень с реализацией на Java
Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении степени.

Подробно читайте на Википедии.

А сейчас перейдем к реализации на Java


public class BinaryExponentiation {
    public static int pow(int x, int n, int mod) {
        int res = 1;
        for (long p = x; n > 0; n >>= 1, p = (p * p) % mod) {
            if ((n & 1) != 0) {
                res = (int) (res * p % mod);
            }
        }
        return res;
    }
    // usage example
    public static void main(String[] args) {
        System.out.println(8 == pow(2, 3, 100));
    }
}

198