Is square removal easier than factoring?

Question

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<q<n$, $\beta_j\in\mathbb{N}$, and $\beta_j\leq\alpha_j$.

Answer 1

I believe no polynomial algorithm is known.

According to a paper this is used in at least one cryptosystem:

Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method.

If you can find $pq$ you will break the cryptosystem by computing $\frac{p^k q}{pq}=p^{k-1}$.

---

This question shows no polynomial algorithm is known to decide if integer is squarefree (all your $\alpha_i=1$).

Answer 2

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.