Is square removal easier than factoring? It seems to me that the square removal task can be reduced to the factoring task, but that there is no way to reduce factoring to square removal. Is there a way to make this "feeling" more precise, i.e. some commonly believed hypothesis which would be violated if factoring could be reduced to square removal? But if square removal should indeed be easier than factoring (in the sense outline above), then the next question is whether it is an NP-intermediate problem (i.e. whether a polynomial time algorithm for it is known or not).



Here is a clumsy description of the square removal and factoring tasks:

Let $n\in\mathbb{N}^*$ be given in binary representation. Let $n=\prod_i p_i^{\alpha_i}$ with $p_i$ prime, $\alpha_i\in\mathbb{N}^*$, and $p_i\neq p_j$ for $i\neq j$ be the prime factorization of $n$.


For square removal, the binary representation of $m=\prod_i p_i$ is requested.
For factoring, finding (the binary representation of) a non-trivial factor of $n$ is requested, i.e. a number $q=\prod_j p_j^{\beta_j}$ with $1&lt;q&lt;n$, $\beta_j\in\mathbb{N}$, and $\beta_j\leq\alpha_j$.
We can show that if all $\alpha_i$ are different, then square removal and factoring of $n$ are equally hard.

It is obvious, that if we can factor $n$, we can also compute square removal of $n$.

The other direction is a bit more tricky. First compute the square removal of $n$ and let's call this $m$. From the definition it follows that $m$ divides $n$. Divide by $m$ repeatedly until we reach a number, which is not divisible by $m$, I'll call this $x$

$$x = \frac{n}{m^b}$$

Now compute $p = \frac{m}{\gcd(x, m)}$, if $p$ had more than one prime factor, those would have identical $\alpha_i$ in the original product $n$, which contradicts the assumption about all $\alpha_i$ being different, hence $p$ is a prime factor in $n$.

Knowing one prime factor in $n$ it is possible to reduce the problem to factoring a smaller $n'$, which satisfy the same criteria, so the algorithm can be repeated.

We can also show that if all $\alpha_i$ are equal, then square removal is easy. That's because $\alpha_i$ can only have logarithmic size in $n$, and every possible $\alpha_i$ can be tested by computing the $\alpha_i$th root of $n$.

However the result obtained that way will be incorrect if the $\alpha_i$ were not equal. The obtained result will be correct iff it is square free. And @joro pointed out, that no polynomial algorithm is known to decide if a number is square free.

So for some $n$ square removal and factoring is equivalent. For other $n$ square removal is easy. Telling those two cases apart appears to be hard.