# Complexity of testing integer square-freeness

How fast can an algorithm tell if an integer is square-free?

I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and ones conditional on GRH (or other reasonable number-theoretic conjectures).

One reference I could find was on the Polymath4 wiki, where it states

No unconditional polynomial-time deterministic algorithm for square-freeness seems to be known. (It is listed as an open problem in this paper from 1994.)

I can't tell if that quote implies that both conditional and randomized polynomial-time algorithms exist, but it might (the exception that proves the rule?).

-

As an upper bound, the problem is clearly in NP at worst. Given a putative factorization, we can check that it is indeed a correct factorization of n and whether it is square free in (very low degree) polynomial time.

Another way of saying this is that there is a non-deterministic polynomial time algorithm. (But this is a far cry, of course, from having a polynomial time random algorithm.)

-
It is also in co-NP. –  Rune Mar 1 '10 at 23:49

MathWorld says that "there is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer".

-
That's good, but unfortunately it doesn't specify whether it means deterministic/randomized and conditional/unconditional. –  aorq Feb 23 '10 at 1:28

I was involved in the conversations about this topic on the Polymath4 blog (actually, looking back, it looks like I was the one who dug up that old paper...) and I came to believe that there was no such algorithm (randomized, conditional, whatever). Certainly I searched the literature as best I could and didn't find one. But I'm pessimistic about finding a reduction from factoring, for reasons I touched on in the linked post.

I was going to mention this beautiful argument, but actually I don't think it applies here -- you can only use squarefreeness to tell if a prime factor $p | N$ ramifies over some extension (Edit: I think this is true -- but something weird might happen if the extension isn't Galois? Maybe? I know so little algebraic number theory it's not even funny), but that's only possible if p divides the discriminant -- but you can do that already by the Euclidean algorithm. So squarefreeness would only let you maybe factor if for some reason you could do the algorithm quickly in number fields with huge discriminant, which admittedly might be possible. Edit: Although of course if the discriminant is big enough to make a difference, it's unclear how you'd extract information about p anyway. Which, modulo a whole bunch of holes and handwaving, would seem to rule out any naive attempt to adapt that "reduction."

-

For quantum computers it is in BQP since factoring is in BQP see the wikipedia article on Shor's algorithm. The general number field sieve is the most efficient classical algorithm for factoring numbers larger than 100 digits according to wikipedia. According to the wikipedia article on factorization for b bits there is a published asymptotic running time of $O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)$ for this algorithm. So this time will be an upper bound for the problem of recognizing square free integers if this algorithm is used.

-
but he only wanted to know if it's square free - not what is the square free part –  David Lehavi Feb 23 '10 at 6:00