Fastest modular exponentiation
Haskell

Though it's simple, it should be pretty fast if built with GHC:

{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}

module Main where

import Data.Bits

seqI :: Integer -&gt; Integer
seqI x = seq x x

seqB :: Bool -&gt; Bool
seqB x = seq x x

getInteger :: IO Integer
getInteger = fmap (seqI . read) getLine

modExp' :: Integer -&gt; Integer -&gt; Integer -&gt; Integer -&gt; Integer
modExp' r b p m = let nextR = seqI $ mod (seqI $ r*b) m
                      nextB = seqI $ mod (seqI $ b*b) m
                      nextP = seqI $ shiftR  p 1
                      incl  = seqB $ testBit p 0
                      cont  = seqB $ nextP  /= 0
                  in  if incl
                         then if cont
                                 then modExp' nextR nextB nextP m
                                 else nextR
                         else if cont
                                 then modExp' r     nextB nextP m
                                 else r

modExp :: Integer -&gt; Integer -&gt; Integer -&gt; Integer
{-# INLINE modExp #-}
modExp !b !p !m = modExp' 1 b p m

main = do
          b &lt;- getInteger
          p &lt;- getInteger
          m &lt;- getInteger
          print $ modExp b p m


Prime modulus optimization

If the modulus is guaranteed to be a prime, but the exponent might be greater than or equal to the modulus, the last line should be changed to:

          print $ modExp b (mod p (m - 1)) m


Handling multiple inputs

If you'd like it to handle multiple inputs per run, add import System.IO under the other import and the following two lines just under the print line:

          isDone &lt;- isEOF
          if isDone then return () else main


Running

Once it's compiled, it can be run as modexp &lt; file.