<p>We can show that if all $\alpha_i$ are different, then square removal and factoring of $n$ are equally hard.</p>

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

<p>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$</p>

<p>$$x = \frac{n}{m^b}$$</p>

<p>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$.</p>

<p>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.</p>

<p>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$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-01-18T19:46:17.297Z
2015-01-18T19:46:17.297Z
kasperd
<p>I believe no polynomial algorithm is known.</p>

<p>According to a <a href="http://imi.kyushu-u.ac.jp/~takagi/takagi/publications/cr98.ps" rel="nofollow noreferrer">paper</a> this is used in at least one cryptosystem:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<hr>

<p>This <a href="https://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness">question</a> shows no polynomial algorithm is known to decide
if integer is squarefree (all your $\alpha_i=1$).</p>

CC BY-SA 3.0
2015-01-18T12:52:33.883Z
2015-01-18T13:34:14.363Z
2017-04-13T12:57:54.777Z
joro
<p>It seems to me that the <em>square removal</em> task can be reduced to the <em>factoring</em> 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 <a href="http://en.wikipedia.org/wiki/NP-intermediate">NP-intermediate</a> problem (i.e. whether a polynomial time algorithm for it is known or not).</p>

<hr>

<p>Here is a clumsy description of the <strong>square removal</strong> and <strong>factoring</strong> tasks:</p>

<p>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$.</p>

<ul>
<li>For square removal, the binary representation of $m=\prod_i p_i$ is requested.</li>
<li>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$.</li>
</ul>

CC BY-SA 3.0
2015-01-18T12:48:53.380Z
$\prod_ip_i$ is called the radical of $n$. There is relevant discussion in  http://math.stackexchange.com/a/171571 .
Emil Jeřábek
CC BY-SA 3.0
2015-01-18T21:28:36.323Z
Just as a side remark: I assume your question is targeted at integers. For polynomials, square-free factorization is indeed much simpler than full factorization.
Christopher Creutzig
<cc.complexity-theory><nt.number-theory><factoring>
Is square removal easier than factoring?
Thomas Klimpel
# Is square removal easier than factoring?

(Asked by: username_0 on 2015-01-18)

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](http://en.wikipedia.org/wiki/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

**Tags:** cc.complexity-theory, nt.number-theory, factoring

> **Comments:**
> **username_1**: $\prod_ip_i$ is called the radical of $n$. There is relevant discussion in  http://math.stackexchange.com/a/171571 .  
> **username_2**: Just as a side remark: I assume your question is targeted at integers. For polynomials, square-free factorization is indeed much simpler than full factorization.  

---

## 2 answers

### Answer by username_4 on 2015-01-18. Score: 10 | Accepted answer

I believe no polynomial algorithm is known.

According to a [paper](http://imi.kyushu-u.ac.jp/~takagi/takagi/publications/cr98.ps) 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](https://mathoverflow.net/questions/16098/complexity-of-testing-integer-square-freeness) shows no polynomial algorithm is known to decide
if integer is squarefree (all your $\alpha\_i=1$).


---

### Answer by username_3 on 2015-01-18. Score: 11

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 @username_4 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.


---

