Modular exponentiation running time
With regards to (3), there's a fairly simple algorithm to compute large exponents.
exp(a, b) =
  if b is even
     let half = exp(a , b/2)
     return half * half
  else
    return a * exp(a, b-1)

This will be logarithmic in the magnitude of $b$, meaning the number of multiplications is linear in the number of bits used to represent $b$. It's also a very general algorithm: it works for normal exponentiation, matrices, modular arithmetic, etc. The complexity will change depending on the complexity of your multiplication operation.