# What is fastest algorithm for factoring out square from number

I have $n$-digit integer $N=a^2b$, $b$ is square-free. In other words, $a$ is maximal square which divides $N$.

What is fastest known algorithm to find $a$? I can write algorithm of $O(n^2\sqrt{N})$ simply trying all squares that are smaller than $N$ and checking for divisibility.

Is this problem as hard as factoring integer?

• @David Yes, however, in my problem not $a$ nor $b$ are primes, $a$ is square and $b$ is square-free. – Somnium Mar 21 '16 at 6:18