> If I wanted to prove that some number N is not equal to the

> form a^b, then wouldn't I have to start by finding the square

> root, the third root, the fifth root, and every odd-number

> root ... and not stop until the result was either integral or

> less than 2?

Correct as far as it goes, though yuou can optimize by only

testing primeth roots because if you've already tested for

a p-th root and the test failed, you already know that it

isn't a pq-th root.

> What would be the maximal order of this type of calculation

> if N is 'm' digits long?

m *log(10)/log(2).

Paul