power_modulo.hs

-- Power modulo a number
powmod :: Int -> Int -> Int -> Int
powmod a pw n   | pw <= 0        = 1
                | pw == 1        = a `mod` n
                | even pw        = powmod' (sqmod a n) (pw `div` 2) n 1
                | otherwise      = powmod' (sqmod a n) (pw `div` 2) n (a `mod` n)
    where
        sqmod :: Int -> Int -> Int
        sqmod a n = (a*a) `mod` n
        powmod' :: Int -> Int -> Int -> Int -> Int
        powmod' a pw n res  | pw == 1        = (res * a) `mod` n
                            | even pw        = powmod' (sqmod a n) (pw `div` 2) n res
                            | otherwise      = powmod' (sqmod a n) (pw `div` 2) n ((res * a) `mod` n)