Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given $n$ I need to quickly determine whether $p^2|n$ for any prime $p$. I've already considered an algorithm that strips all primes not exceeding $n^{1/3}$ and then we can easily check that $n$ is not an exact square (except one).

I've heard mentioned that there is an $O(n^{1/6})$ algorithm in fact but no details were given and I can't see how. I expect this would be an optimal algorithm for small enough $n$. Of course it would be possible to use a sub-exponential algorithm to factor $n$ fully so this question is really about what shortcuts are available when we only care whether $n$ is squarefree.

share|improve this question
add comment

2 Answers

It might seem surprising, but as far as I know there is really not that much to say beyond: factor as fast as you can and check. (And this might be the 'truth' though I do not think there is a proof showing the equivalence of the two problems.)

And, this problem is also well studied as it arises in Computational Algebraic Number Theory; for example in Zassenhaus Algorithm do compute integral basis for maximal orders to decompose a discriminant into squarefree and squre part is the main computational bottleneck.

I do not know what this order $n^{1/6}$ algorithm is, but this is (as you say) worse than factoring for large $n$.

Cf. http://mathworld.wolfram.com/Squarefree.html between equation (2) and (3) for a reference for about what I say.


Added: The reference provided by Igor Rivin is very interesting and pertinent to the question, to save rushed MO-readers some time, I extract some info from it.

The '$O(n^{1/6})$ algorithm' runs more or less along the lines sketched out already by OP. Since checking whether an integer is a square is easy, it suffices to detect factors up to size $n^{1/3}$.

Now, this can be done Pollard--Strassen algorithm that allows to detect factors of size at most $B$ in time $O(n^{\varepsilon}B^{1/2})$, which for $B=n^{1/3}$ yields the claimed thing (up to the epsilon and this can improved a bit, but things stay slightly above $n^{1/6}$).

The running time for the squarefree-proving algorithm under GRH is of order $\exp( (\log n )^{c+o(1)} )$, where this $c$ is defined in a certain complicated way, and is conjectured to be $2/3$.

For comparison, and as mentioned in that reference, there are factoring algorithms with expected running time $\exp( (\log n )^{c'+o(1)} )$ with $c'$ equal to $1/2$ (Elliptic Cuves, Quadratic Sieve) and $1/3$ for Number Field Sieve.

So for this squarefree-proving algorithm one can prove (under GRH) something on its running time that one cannot prove for factoring algorithms.

Thus, it seems to me, if one is mainly interested in actually establishing/computing that a number is squarefree or not (as opposed to needing provable information/bounds on the difficulty of the task) it might still be better to go with factoring, as one expects it to be faster; and if ever the expectations should be wrong then, under typical circumstances, one could still do something else.

share|improve this answer
    
It might be prudent to try a primality test and/or a perfect power test before trial factorization or some other factorization method. If you suspect a large square factor, testing primality and or perfect power after each small factor is removed might be prudent. Gerhard "Ask Me About System Design" Paseman, 2012.08.16 –  Gerhard Paseman Aug 17 '12 at 0:38
1  
Efficient factorization is typically a multi-step/algorithm process. So, in general if one wants to factor efficently, it will always be prudent to use various different method in a layered form. And, actually I guess if the $n$ is not very special it might be the wisest thing to do trial division by small primes first. Quite a bit mor likely something is divisible by 4 that that it is prime or a prime power (except if $n$ is very small). –  quid Aug 17 '12 at 0:49
    
Since I blurred this a bit and it is potentially important I add: the squarefree proving algorithm is conditional on GRH in the sense that only if one assumes it the algo is guaranteed to be correct (as oposed to merely the estimate on its running time depending on it). So knowledge on squarefreenes of some given number, obtained by using this algo, will be conditional on GRH (or an appropriate 'subset' thereof). –  quid Aug 17 '12 at 19:38
add comment

The $N^{1/6}$ algorithm is explained in this work by Booker, Hiary, Keating, which is devoted to a MUCH cooler algorithm (conditional on the GRH, and subexponential (though super polynomial))

share|improve this answer
1  
That's interesting reference! –  quid Aug 17 '12 at 1:05
add comment

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.