It is shown that Coppersmith method yields optimal integer root extraction for univariate polynomials in https://arxiv.org/abs/1605.08065 and a follow up work attempts this for bivariate polynomials https://eprint.iacr.org/2012/108.pdf but seems to fall much short of general result for univariate case.

Is it believed that the Coppersmith method is best possible for multivariate case and what do we know about the multivariate case?

  • 1
    $\begingroup$ Optimal ... for doing what? $\endgroup$ – Gerry Myerson Dec 31 '18 at 14:49
  • $\begingroup$ The technique cannot be beaten to extract roots. $\endgroup$ – Freeman. Dec 31 '18 at 14:56
  • $\begingroup$ OK, so, it's a method for finding roots of univariate polynomials. But multivariate polynomials have an infinity of roots, so, what would "optimal" mean? $\endgroup$ – Gerry Myerson Dec 31 '18 at 14:58
  • $\begingroup$ Usually we place a bound on integer roots since only integer roots matter. $\endgroup$ – Freeman. Dec 31 '18 at 14:59
  • 1
    $\begingroup$ Provided details. $\endgroup$ – Freeman. Dec 31 '18 at 15:04

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.