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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Mar 20, 2016 at 22:18
  • $\begingroup$ Perhaps, but at the moment no such algorithm is known. Perhaps you can find it. $\endgroup$
    – Yuval Filmus
    Commented Mar 20, 2016 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
    Commented Mar 21, 2016 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
    Commented Mar 21, 2016 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
    Commented Apr 3, 2017 at 21:57
0
$\begingroup$

It's obviously not harder than factoring, because you can solve the problem by factoring N into primes, and taking pairs of prime factors. So trying all squares less than N is quite bad.

The question is whether we can solve this faster than factoring, which depends on the algorithm used.

For factoring using the naive algorithm, you would check if any primes up to $N^{1/2}$ divide N. But here we only need to check primes up to $N^{1/3}$: If there are no factors up to $N^{1/3}$ then N is prime or the product of two primes. So N is square free unless it is the square of a prime, which is easy to check. So you can solve the problem in $O(N^{1/3})$ instead of $O(N^{1/2})$ using the most basic factoring algorithm.

The Pollard-rho algorithm finds the smallest factor in $(p^{1/2})$ where p is the smallest factor. You use this to try to find factors. In the original Pollard-rho algorithm, once you have done about $N^{1/4}$ iterations of the algorithm, you can say "if there was a factor then I would have found it by now" and check whether N is a prime using some primality test. For this problem, you would say after $N^{1/6}$ iterations "if there was a square factor and another factor than I would have found a factor by now". So then you check if N is a square or a prime. Unfortunately, if N is the product of two large primes, Pollard-rho tells you quite quickly that N is very likely to be square free, in $O(N^{1/6})$, but a proof will take $O(N^{1/4})$.

And there's a link showing that for the fastest known factoring algorithm, looking for squares is not any faster.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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