[sluukkonen]

There is. x^n = (x^(n/2))^2 if n is even, (x^(n-1/2))^2 if n is odd, so it's possible to exponentiation in logarithmic time.