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

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.

share|improve this question
add comment

4 Answers

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

share|improve this answer
4  
It is also in co-NP. –  Rune Mar 1 '10 at 23:49
add comment

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

share|improve this answer
1  
That's good, but unfortunately it doesn't specify whether it means deterministic/randomized and conditional/unconditional. –  aorq Feb 23 '10 at 1:28
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
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.