Modular exponentiation running time I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy&nbsp;&ndash; I'm not a comp sci student).


Is it poly time only for base 2, i.e in binary or will it remain poly time algorithm even if i run it in decimal system i.e base 10?
If I'm calculating $(a^b) \bmod p$,  where $1&lt;a&lt;11$, $1 &lt; b \leq (p-1)/2$, and we run this modular exponentiation at most $p/2$ times, all this being done in decimal base 10 system, will it still be poly time?
Even if this is poly time, and this is a big IF, can this process actually be completed in reasonable time in terms of the real worldly 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.