Fast square-free decomposition of integers using class groups

Let \(n=a^2b\) $n=a^{2}b$ , where b is square-free. In this paper we present an algorithm based on class groups of binary quadratic forms that finds the square-free decomposition of n, i.e. a and b, in heuristic expected time: \(\begin{aligned} \widetilde{\mathcal {O}}{(L_{b}[1/2,1] \ln (n) + L_{b}[1/2,1/2] \ln (n)^2)}. \end{aligned}\) $$\begin{array}{c}\hfill \tilde{\mathcal{O}}(L_b[1/2,1]ln(n)+L_b[1/2,1/2]ln{(n)}^2).\end{array}$$ If a, b are both primes of roughly the same cryptographic size, then our method is currently the fastest known method to factor n. This has applications in cryptography, since some cryptosystems rely on the hardness of factoring integers of this form.