高速指数計算法 mod m バージョン

前回書き下した再帰を用いた高速指数計算関数をmod mバージョンにして、7を一般化した数bにしてみよう。 するとこうなる。関数名はpowからexpmodに置き換えた。

func expmod(b:Int, e:Int, m:Int) -> Int {
    if e == 0 { return 1 }
    let s = expmod(e/2) % m
    // 2乗する
    let r = (s * s) % m
    if isOdd(e) {
        return (r * b) % m
    } else {
        return r
    }
}

を計算したい場合はこの関数を使えばよい。