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?

Improve this question
$\endgroup$
15
  • $\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
    Commented Jan 8, 2019 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$
    – Turbo
    Commented Jan 8, 2019 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
    Commented Jan 8, 2019 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
    Commented Jan 8, 2019 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$
    – Turbo
    Commented Jan 9, 2019 at 3:52

0

Reset to default

You must log in to answer this question.