How to perform integer modular exponentiation in Golang

Question

How to calculate a**b % m where all the members are integers, and a^b is outside the int range?

I.e. to raise a to the power b under modulo m. I.e. an equivalent of this Python code:

pow(a, b, m)

Answer 1

Use the Exp function from the built-in math/big package. But it requires plenty of type conversions.

import "math/big"

func pow(a, b, m int) int {
    result := new(big.Int).Exp(
        big.NewInt(int64(a)),
        big.NewInt(int64(b)),
        big.NewInt(int64(m)),
    )
    return int(result.Uint64())
}

Try it.

Answer 2

It should be possible to do this in a more memory-efficient way, without resorting to big integers.

This is a direct translation from the pseudocode found on Wikipedia:

package main

import (
    "fmt"
)

func modPow(a, b, m int) int {
    if m == 1 {
        return 0
    }

    c := 1

    for i := 0; i < b; i++ {
        c = (c * a) % m
    }

    return c
}

func main() {
    fmt.Println(modPow(1234, 5678, 9012))
}

^{Disclaimer: I don't know golang :)}

---

Playground link

Answer 3

Calculating the exponent manually as suggested by Robby, but efficiently:

func pow(a, b, m int) int {
    if b < 0 {
        panic("Negative power given")
    }

    result := 1
    power := a

    for b > 0 {
        if b & 1 == 1 {
            result = result * power % m
        }
        power = power * power % m
        b >>= 1
    }

    return result
}

This is an iterative version of exponentiation by squaring. The time complexity is O(log(b)) if we assume that every multiplication takes O(1) time.

Try it.

Negative power

If m is prime, it's possible to calculate the negative power. It requires 2 steps:

1. Calculate the positive power
2. Divide 1 by the result using Fermat's little theorem

func powUniversal(a, b, m int) int {
    if b >= 0 {
        return pow(a, b, m)
    }
    subResult := pow(a, -b, m)
    return pow(subResult, m - 2, m)
}

You can check that it works by asserting powUniversal(a, b, m) * powUniversal(a, -b, m) % m == 1.