11
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – pg1989 Jun 12 '17 at 15:32
  • 1
    $\begingroup$ 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) $\endgroup$ – SEJPM Jun 12 '17 at 16:56
  • 5
    $\begingroup$ It is not known to be easy in general, but in some cases it can be. $\endgroup$ – Samuel Neves Jun 12 '17 at 16:57
  • 1
    $\begingroup$ @SamuelNeves, that would be a good answer, especially with a choice quote or two from the paper. $\endgroup$ – otus Jun 13 '17 at 4:52
  • 1
    $\begingroup$ If feasible, it would also break the Okamoto Uchiyama homomorphic encryption scheme. $\endgroup$ – Geoffroy Couteau Jun 13 '17 at 7:59
7
$\begingroup$

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.

As far as concrete factorization algorithms targeting this type of integers, there are various strands:

  • Peralta and Okamoto slightly optimized ECM against this form, but the result is not significantly superior to regular ECM.
  • 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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.