We present a new algorithm based on binary quadratic forms to factor integers of the form N = pq 2 . Its heuristic running time is expo-nential in the general case, but becomes polynomial when special (arith-metic) hints are available, which is exactly the case for the so-called NICE family of public-key cryptosystems based on quadratic fields introduced in the late 90s. Such cryptosystems come in two flavours, depending on whether the quadratic field is imaginary or real. Our factoring al-gorithm yields a general key-recovery polynomial-time attack on NICE, which works for both versions: Castagnos and Laguillaumie recently ob-tained a total break of imaginary-NICE, but their attack could not apply to real-NICE. Our algorithm is rather different from classical factoring algorithms: it combines Lagrange's reduction of quadratic forms with a provable variant of Coppersmith's lattice-based root finding algorithm for homogeneous polynomials. It is very efficient given either of the following arithmetic hints: the public key of imaginary-NICE, which provides an alternative to the CL attack; or the knowledge that the regulator of the quadratic field Q(√ p) is unusually small, just like in real-NICE.Read less <