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

$ curl repovive.com/roadmaps/math-fundamentals/exponents-roots/power-modulo-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████

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

$ curl repovive.com/roadmaps/math-fundamentals/exponents-roots/power-modulo-implementation

Repovive

Power Modulo - Implementation - Exponents & Roots | Math Fundamentals | Repovive

Repovive.

Math Fundamentals18 sections · 842 units13h total

Open in Course

Power Modulo - Implementation

Bit-by-bit squaring

Here's the iterative modular exponentiation:


function powerMod(x, n, m)
    result := 1
    x := x mod m
    while n > 0
        if n mod 2 = 1 then
            result := (result * x) mod m
        x := (x * x) mod m
        n := n / 2
    return result

Time: $O(\log n)$ . Space: $O(1)$ . You avoid overflow by taking $\bmod m$ after every multiplication. This keeps all intermediate values below $m$ .