0
$\begingroup$

In the final step in Coppersmith technique we have $n$ polynomials (possibly non-homogeneous) in $\mathbb Z[x_1,\dots,x_m]$ where $m\leq n$ and using elimination theory we extract the common integer roots of these $n$ polynomials.

  1. Can we use resultants here? As I understand resultants are for algebraically closed fields and $\mathbb Z$ is not even a field. How does Coppersmith's technique work to obtain integer roots? Is there some variation here?

  2. Is there any other technique applicable here? What are some good comprehensive explicit example friendly references to know more on this?

$\endgroup$
  • $\begingroup$ Resultants are defined for polynomials over arbitrary rings and always give an upper bound for the set of common roots. Good methods for computing resultants exist but they are not straightforward (e.g. theory of subresultants, Gröbner bases...). $\endgroup$ – François Brunault Jan 8 at 14:18
  • $\begingroup$ @FrançoisBrunaulth Thank you. If I need to compute integer roots what modifications I need? Is it possible for you to provide full post with references? I will appreciate it. $\endgroup$ – Freeman. Jan 8 at 15:16
  • $\begingroup$ I realize that for resultants or Gröbner bases to work, you need to assume that your system of polynomial equations has only finitely many solutions. Is it the case? Otherwise, your question amounts to find the integral points on some algebraic variety, which is hard even in the case of curves. So unless you provide more details, I cannot answer your question. $\endgroup$ – François Brunault Jan 8 at 19:07
  • $\begingroup$ I mean, finitely many complex solutions (in other words, the algebraic set defined by your system is $0$-dimensional). $\endgroup$ – François Brunault Jan 8 at 19:59
  • $\begingroup$ @FrançoisBrunault Sorry I was under opinion if we had $n$ non-homogeneous algebraically independent polynomials in $n$ variables the common solution had to be $0$-dimensional. Am I wrong in this and if so what else I need to guarantee $0$ dimensionality? $\endgroup$ – Freeman. Jan 9 at 3:52

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.