Formula/Algorithn for Exponential factoring?

Question

Given $s = a^b$ find $a$ and $b$. my first algorithm was the obvious brute force method of checking all $b$ roots or dividing by all possible $a$. But I am wondering if there is a more efficient method. My first optimization was noting that only Prime $b$ have to be tested but that is still a form of brute force. Can any additional number theory properties be used to generate faster method or algorithm? How dos this problem stack up in terms of difficulty when compared to factoring?

Answer 1

This is best. Infinitely quicker than full factoring. Prime $b,$ with $$ b \leq \frac{\log s}{\log 2} $$ because $a \geq 2.$ Newton's method for $$ x^b - s = 0. $$ It is actually possible to do Newton's method in integers, as long as, when getting near the actual $\lfloor s^{1/b} \rfloor,$ you avoid an infinite loop by switching to just adding or subtracting $1$ as needed. I do this for integer square roots, cube roots, and fifth roots in C++. Oh, if you have a maximum legal integer such as $2^{31}-1,$ it is also necessary, doing this in integers, to check whether $s$ greater than or equal to the biggest legal $a_{\mbox{max}}^b$ that occurs in integers, in which case the value $a_{\mbox{max}}$ is returned. This was surprising at the time, got an infinite loop by asking for the square root (floor thereof) for an integer between $46340^2$ and $2^{31}-1.$

I believe GMP has this fully implemented in integers of arbitrary size.