5
$\begingroup$

Is there an algorithm to check whether an integer $n$ is a square? What about higher powers, e.g., testing whether $n$ is a $k$th power?

I understand that the Jacobi symbol $\left(\frac{b}{n}\right)$ can be computed in $O(\log n)$ without needing to know the prime factorization of $n$ but then this seems to be useful only for squares (not higher powers), and even then, it can still be inconclusive.

Maybe there is some way of refining the use of the Jacobi symbol for my question?

$\endgroup$
  • $\begingroup$ squares of nat. numbers have distinct remainders module 2 or module 3, same happens for higher powers. however if you want to test arbitrary higher powers, sth like Fermat's little theorem (or variations thereof) can be of help $\endgroup$ – Nikos M. Jun 4 '14 at 20:28
  • $\begingroup$ sorry prev comment is somewhat irrelevant, just saw the question is about squares/powers modulo n $\endgroup$ – Nikos M. Jun 4 '14 at 20:47
  • $\begingroup$ Apparently the original author did mean for this to be about integers (despite the mention of the Jacobi symbol), but didn't return until significantly later to clarify things. My fault. I've rolled the question back and edited to make clear that this is not about modular arithmetic. @Yuval, can I encourage you to undelete your answer? It provides the canonical answer to this question. $\endgroup$ – D.W. Jun 6 '14 at 1:17
  • $\begingroup$ @D.W. Perhaps you should ask a new question that you can answer with your excellent answer. $\endgroup$ – Yuval Filmus Jun 6 '14 at 1:45
  • $\begingroup$ @YuvalFilmus, thanks for restoring your answer! Good stuff. (I've posted a new question and my answer about modular square roots at cs.stackexchange.com/q/26452/755.) $\endgroup$ – D.W. Jun 6 '14 at 2:06
3
$\begingroup$

The standard algorithm for determining whether an integer $n$ is a perfect power goes like this. We check whether it is a perfect $k$th power for $k \in \{2,\ldots,\log n\}$; as an optimization, it suffices to consider only prime $k$. Given $k$, we compute $\sqrt[k]{n}$ using binary search or using some fixed-point iteration such as Newton's method. Either way, we find a candidate for $\sqrt[k]{n}$, and can check whether $(\sqrt[k]{n})^k = n$ or not. For more details on computing $\sqrt[k]{n}$, consult for example this paper (mentioned in Ricky Demer's deleted answer), Step 1.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.