Dear Nate, first, why is $e$ the preferred base for exponentials? Imagine that you have 1 dollar and your bank gives you 100% interest rate. After 1 year, you will have 2 dollars.
Now it offers you to add interests 100 times in a year but the interest is 1% at each moment. How much will you get? You will get
$$ (1+0.01)^{100} \approx 2.704 $$
What if they add you $1/N \times $ 100% at $N$ moments of the year and you send $N$ to infinity? Well, you will have $e\approx 2.71828$ dollars after one year.
In fact, the general exponential - power with the base of $e$ - may be defined by this "repeated small interest" formula as
$$ e^X = \exp(X) = \lim_{N\to \infty} \left(1+\frac {X}{N}\right)^N $$
It only has this simple form if the base is $e$. A more general power may be defined as
$$ Y^X = \exp(X \ln Y) .$$
Here, $\ln$ is the natural logarithm so that $\exp\ln X = X$. If I replaced the base $e$ by another base such as $2$ or $10$, the "repeated small interest" formula above would have to contain $\ln 2$ or $\ln 10$ or other awkward factors at various places. It wouldn't be natural.
So instead of powers $Y^X$ and logarithms with general bases, you should think that in mathematics, only $\exp(X)$ and $\ln(X)$ are really needed, and all the other powers and logarithms may be expressed as composite functions. Also, $\exp(X)$ has the advantage that its derivative is exactly equal to the very same function $\exp(X)$. In particular, the derivative evaluated at $X=0$ is equal to one, very nice and simple. It would be $\ln(Y)$ if you used a different base $Y$ instead of $e$.
Now, what is the exponential of an imaginary exponent? Again, you may write
$$\exp(iX) = \lim_{N\to\infty} \left(1+\frac {iX}{N}\right)^N $$
You multiply $N$ copies of a number that is very close to one. What do you get?
Well, the multiplication by a complex number has the effect of magnifying (or reducing) the plane, and rotating it. In particular, the absolute value of the number $(1+iX/N)$ is essentially one, up to second-order corrections that disappear in the $N\to \infty$ limit. So in the limit, $(1+iX/N)$ is effectively a number whose absolute value equals one.
Multiplying by complex numbers whose absolute value is equal to one looks like a rotation of the complex plane. The angles are preserved - those are some things one should know about the complex numbers. Moreover, it's clear that multiplying by $(1+iX/N)$ is equivalent to the rotation by $X/N$ in radians. If you multiply the same factor $N$ times, you simply get a rotation by $X/N$ in radians.
So the $N$th power of $1+iX/N$, in the limit $N\to\infty$, is the number that you get by rotating $1$ in the counter-clockwise direction by the angle $X$ in radians. Clearly, the answer is
$$ \exp(iX) = \cos (X) + i \sin(X) $$
where the trigonometric functions have arguments in radians, of course. Once again, the mathematically natural unit of an angle is in radians for very similar reasons why the natural base of the powers or exponentials is $e$. Only in radians, it's true that the derivative of $\sin X$ equals $\cos X$ and many other things.
In fact, the previous formula makes it natural to say that $\cos X$ and $\sin X$ are not "independent" functions, either. They may be defined as
$$\cos (X) = \frac 12 ( e^{iX} + e^{-iX} ) $$
$$\sin(X) = \frac{1}{2i} (e^{iX} - e^{-iX} ) $$
You may substitute the last two equations into the previous one or vice versa to check that everything is consistent.
Just to be sure, general complex numbers may also be exponentiated via $\exp(A+iB) = \exp(A)\exp(iB)$ where both factors are known.
If you're trying to test if an integer is a (proper) power, it suffices to check if it's a p-th power for some prime up to its base-2 logarithm. This is pretty fast even for numbers in the range you ask for, where you'd only need about 14 tests. If you need a fast method for very large numbers, Bernstein, Lenstra & Pila's Detecting perfect powers by factoring into coprimes has an essentially-linear solution.
If you're asking about the same test mod a fixed value, then this is the discrete logarithm problem which is notoriously difficult. The best known methods for large values are the index calculus method and the number field sieve. Both are difficult to program.
If you need the greatest power, not just some power, you'll need to do slightly more work. One method: test all exponents, not just primes, up to the base-2 logarithm, in decreasing order. Faster method: test only the primes, but when you find that it is a power take the root and multiply an exponent variable (starting at 1) by the prime. So if you find that it's not a square but it is a third power, take the cube root and set the exponent to 3. Now test if what remains is a cube; if so, change the exponent to 9 and take the cube root again. If what remains is not a cube, continue testing for 5th, 7th 11th, etc. powers up to the new base-2 logarithm.
Best Answer
Standard definition of a complex exponent $w^z$ is $$ w^z=e^{z\log(w)} = e^{a\log(w)}e^{bi\log(w)}$$
where $z = a +bi.$ For $w = re^{i\theta},$ this gives $$ w^z = e^{a\ln(r)}e^{ai\theta}e^{bi\ln(r)}e^{-b\theta}. $$ For $w = 0,$ we have $r=0$ and $\theta =$ whatever. $\ln(0)$ is undefined but we can take the limit $r\downarrow0$ so that $\ln(r)\downarrow-\infty.$ The limit of the expression for $w^z$ is only zero if $a >0,$ otherwise it blows up or oscillates. In other words if $\Re(z)>0$ then $0^z=0.$ Otherwise it's infinite or undefined.