Fast square-free decomposition of integers using class groups

Abstract

Let $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: $$\tilde{\mathcal{O}}(L_b[1/2,1]\ln (n)+L_b[1/2,1/2]\ln (n{)}^2).$$ 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.

43 pages