Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a number $n$, what is best efficient way to check if it is of $a^b$ form for some $a,b\geqslant2$.
Provided $n$ can be as large as $10^{16}$.

share|cite|improve this question
Note that more efficient algorithms exist, but they are more complicated. For example – fkraiem Jan 4 '14 at 15:43
@fkraiem i cant download the paper right now because of internet problem.Could you provide me algorithm here? – user3001932 Jan 4 '14 at 15:43

The idea is that there are very few possible values for $b$ (only about $\log n$), so it is okay to just brute force through them. And then for each $b$ the array $[1^b, 2^b, 3^b, \dots, n^b]$ is sorted in ascending order, so we can do a binary search for a value in it which is equal to $n$. Using fast exponentiation, this gives an algorithm which runs in $O(\log^2n\log\log n)$ multiplications mod $n$.

I'll leave the actual (pseudo)code as an exercise, and it can also be found (along with a complexity analysis) in Dietzfelbinger, Primality Testing in Polynomial Time (LNCS 3000), as Algorithm 2.3.5.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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