28
$\begingroup$

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.

Improve this question
$\endgroup$
2

4 Answers 4

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ That's good, but unfortunately it doesn't specify whether it means deterministic/randomized and conditional/unconditional. $\endgroup$
    – aorq
    Commented Feb 23, 2010 at 1:28
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ It is also in co-NP. $\endgroup$
    – Rune
    Commented Mar 1, 2010 at 23:49
  • $\begingroup$ Is there a nice demonstration that it lies in co-NP without using a polynomial-time primality-checking algorithm? The easiest co-NP construction I see is where the witness is the factorization, and the verifier checks that they multiply to the given N, and then checks their primality. That PRIMES is in P is a bit heavy-handed, though. $\endgroup$
    – Alex Meiburg
    Commented Jan 22, 2018 at 10:16
  • $\begingroup$ (Not to mention slow! Not that efficiency of co-NP checking is too relevant to .. almost anything) $\endgroup$
    – Alex Meiburg
    Commented Jan 22, 2018 at 10:16
3
$\begingroup$

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."

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ but he only wanted to know if it's square free - not what is the square free part $\endgroup$
    – David Lehavi
    Commented Feb 23, 2010 at 6:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .