3
$\begingroup$

I have $n$-digit integer $N=a^2b$, $b$ is square-free. In other words, $a$ is maximal square which divides $N$.

What is fastest known algorithm to find $a$? I can write algorithm of $O(n^2\sqrt{N})$ simply trying all squares that are smaller than $N$ and checking for divisibility.

Is this problem as hard as factoring integer?

$\endgroup$
3
$\begingroup$

Using state of the art factoring algorithms, you can substantially improve on the algorithm you state. It appears that no algorithm better than factoring is known at the moment. See this question on mathoverflow.

$\endgroup$
  • $\begingroup$ However, I think that there can exist polynomial time algorithm for checking for square-freeness, because there exists polynomial time primality test and primality testing seems harder problem. $\endgroup$ – Somnium Mar 20 '16 at 22:18
  • $\begingroup$ Perhaps, but at the moment no such algorithm is known. Perhaps you can find it. $\endgroup$ – Yuval Filmus Mar 20 '16 at 22:19
  • 2
    $\begingroup$ @Somnium It's not at all clear that primality is harder than square-freedom. Perhaps you think it's easier because, instead of saying that the number has no factors, you're saying it's allowed some factors, as long as they're of a special form? So it's a kind of relaxation. But, for example, "is not a product of 2 and a prime" is a relaxation of evenness in the same way, but "is not a product of 2 and a prime" is clearly harder to decide than evenness. $\endgroup$ – David Richerby Mar 21 '16 at 2:51
  • $\begingroup$ @David Yes, however, in my problem not $a$ nor $b$ are primes, $a$ is square and $b$ is square-free. $\endgroup$ – Somnium Mar 21 '16 at 6:18
  • $\begingroup$ Probabilistic primality tests are quite fast and easy, but I'm not aware of any probabilistic square-freeness test. So probabilistic primality test seems to be easier, which makes me think non-probabilistic primality test might be easier as well. $\endgroup$ – gnasher729 Apr 3 '17 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.