寻找最大平方除数的算法

Question

给定一个正整数 n，找到最大整数 a，使得 a*a 整除 n。

如果你知道 n 的因式分解，那就相当简单了。问题是，它是否可以比使用最知名的方法对 n 进行因式分解更快地完成？有没有多项式算法？（位长为 n 的多项式）

例如，使用 Pollard 的 rho 分解算法，它将在 O(n^(1/4)) 中运行，但我正在寻找更好的算法。