Fast algorithm to find factor of a term that is a power

Question

Let's say we have a term (eg an integer, but interested in symbolic polynomial as well) $t$ that can be factored as $t=p^k \cdot m$.

Note: $p$ need not be necessarily prime or otherwise irreducible factor.

What is a fast algorithm to find $p$, given $t$ and $k$ ($k$ is a known fixed integer), without necessarily factoring $t$, since then it is trivial to find $p$, but factorization is slow in general?

PS. My use case is the simplification of kth-roots in a symbolic library I am developing. So that $\sqrt[k]{t}$ can be simplified to the "canonical" form $p \sqrt[k]{m}$, where $m$ cannot be expressed further as a kth-power. Since simplification is used often, a fast algorithm is needed.

Answer 1

No algorithm faster than factorization is known even in the special case $k=2$ (i.e., to compute the square-free core). See e.g. Wikipedia.

• Nikos M.: Hmm, it seems so..