Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
Note that more efficient algorithms exist, but they are more complicated. For example cr.yp.to/papers/powers-ams.pdf –  fkraiem Jan 4 at 15:43
    
@fkraiem i cant download the paper right now because of internet problem.Could you provide me algorithm here? –  user3001932 Jan 4 at 15:43

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.