冪乗計算のバイナリ法と冪剰余

GCJJ決勝のB問題を解いてたら解けなくて気づいたらここに辿り着いてたのでメモ。

冪剰余計算

import Data.List

bits :: Integer -> [Integer]
bits e = reverse $ bits' e
    where
    bits' 0 = []
    bits' x = (x `mod` 2) : bits' (x `div` 2)

binaryMod :: Integer -> Integer -> Integer -> Integer
binaryMod x e m = foldl' ope 1 $ bits e
    where
    ope n 0 = n^2 `mod` m
    ope n 1 = n^2 `mod` m * x `mod` m

なお、binaryMod内の`mod` mを除けば冪乗を計算するバイナリ法として動作。
使ってみると、(13783^5789) ^ (4498^10798) `mod` 5578 は1245だと返した。