Binary Exponentiation - Algorithm Tutorial | Repovive

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

Fast Exponentiation (Binary Exponentiation)

Binary Exponentiation, also known as exponentiation by squaring or fast power, computes $x^n$ in $O(\log n)$ time instead of $O(n)$ . You use the property that $x^n = (x^{n/2})^2$ when $n$ is even.

If you compute $x^n$ naively, you need $n$ multiplications. For $n = 10^9$ , this won't finish in time. You repeatedly halve the exponent to achieve logarithmic complexity.

text

function power(x, n, mod):
    result = 1
    x = x mod mod

    while n > 0:
        if n is odd:
            result = (result * x) mod mod
        x = (x * x) mod mod
        n = n / 2 (integer division)

    return result

Example trace: $3^{13} \mod 1000$ $1.$ $n = 13$ (odd): $result = 3$ , $x = 9$ , $n = 6$ $2.$ $n = 6$ (even): $x = 81$ , $n = 3$ $3.$ $n = 3$ (odd): $result = 243$ , $x = 561$ , $n = 1$ $4.$ $n = 1$ (odd): $result = 594$ , done

Applications: You use binary exponentiation for modular arithmetic, matrix exponentiation, cryptography (RSA), and computing large Fibonacci numbers.

Time complexity: $O(\log n)$ multiplications.

Space complexity: $O(1)$ for iterative version.

Binary Exponentiation Algorithm Tutorial

Learn

Fast Exponentiation (Binary Exponentiation)

Implement this Algorithm

Related Algorithms