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?).
Thanks in advance.
Best Answer
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.)