Fast Algorithms for Distinguishing Squarefrees

Question

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.

Answer 1

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))

Answer 2

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.