# Is it easy to factorize a number of the form $n = t^{2} \cdotp p$?

Is it easy to factorize a number of the form $n = t^{2} \cdotp p$, where $t$ and $p$ are large primes?

• As far as I know, this is an open problem. It's been conjectured that numbers of this form can be factored much more efficiently. However, no algorithm has been demonstrated. – pg1989 Jun 12 '17 at 15:32
• If it were easy, it would immediately and completely break the ESIGN signature scheme (section 11.7.2 of the Handbook of Applied Crypto PDF) – SEJPM Jun 12 '17 at 16:56
• It is not known to be easy in general, but in some cases it can be. – Samuel Neves Jun 12 '17 at 16:57
• @SamuelNeves, that would be a good answer, especially with a choice quote or two from the paper. – otus Jun 13 '17 at 4:52
• If feasible, it would also break the Okamoto Uchiyama homomorphic encryption scheme. – Geoffroy Couteau Jun 13 '17 at 7:59

Integers of the form $n = p\cdot q^2$, $p$ and $q$ prime, are the basis of a few public-key cryptosystems, including ESIGN, Okamoto-Uchiyama, cryptosystems based around the hardness of finding the class number of quadratic fields. As such, being able to efficiently factor numbers of this form would immediately break a number of cryptosystems. This would be a big deal. Additionally, this is also related to a classic problem in number theory, which would be of independent interest.
• Boneh, Durfee, and Howgrave-Graham used Coppersmith-style root-finding techniques to factor $n$ in approximately $n^{1/9}$ operations when $p$ and $q$ are similarly-sized. While this may sound impressive, it is not better than the number field sieve for numbers of cryptographically-relevant size.
• Castagnos, Joux, Laguillaumie, and Nguyen observed that, given some extra information about $n$ it becomes possible to factor $n$ in polynomial time. But this is not the general case and only applies to special cases, like NICE.