title: Is there a polynomial time algorithm to test whether a number exponent of some number?
body: <p>Just study the famous paper <code>PRIMES is in P</code> and get confused.</p>
  
  <p>First step of the proposed algorithm is <code>If (n=a^b for nature number a and b&gt;1), output COMPOSITE.</code> Since the whole algorithm runs in polynomial time, this step must also complete in O((log n)^c)(given input size is O(log n). However, I can't figure out any algorithm to hit the target after some googling.</p>
  
  <p>QUESTION:</p>
  
  <p>Is there any algorithm available to test whether a number exponent of some other number in polynomial time?</p>
  
  <p>Thanks and Best Regards!</p>