1
$\begingroup$

Given a quadratic diophantine equation in $\mathbb Z[x,y,z]$ of form

$$ax^2+by^2+cx+dy+ez+f=0$$ are there standard methods to solve for it when $$\|(x^2,y^2,z)\|_\infty\leq e^{1/2}$$ $$\|(a,b,c,d,e,f)\|_\infty\leq e$$ holds in $O(\mathsf{polylog}(e))$ time?

I noticed we can change the form to shape $X^2+Y^2+ez+g=0$ where $X=a'x+b'$ and $Y=c'y+d'$ for some $a',b',c',d',g\in\mathbb Z$ by completing the square.

So we are asking $$(a'x+b')^2+(c'y+d')^2\equiv-g\bmod e$$ where $$\|(x,y)\|_\infty\leq e^{1/4}$$ holds.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This can be potentially solved by a variation of the Coppersmith method, e.g., by that of Bauer and Joux (2007).

Improve this answer
$\endgroup$
5
  • $\begingroup$ 'Potentially' or provably? $\endgroup$
    – VS.
    Commented Jun 13, 2020 at 6:05
  • $\begingroup$ It's an heuristic method with expected but not provable outcome. $\endgroup$
    – Max Alekseyev
    Commented Jun 13, 2020 at 12:33
  • $\begingroup$ I think that is for a general trivariate. This is a particular quadratic surface. Arithmetic might help that just combinatorics without arithmetic. Perhaps lot more is known in arithmetic geometry about such surfaces. It is worth going through the arithmetic geometry route. $\endgroup$
    – VS.
    Commented Jun 13, 2020 at 13:40
  • $\begingroup$ Anyway, I did not check carefully and have no ground to say that it's provable. $\endgroup$
    – Max Alekseyev
    Commented Jun 13, 2020 at 13:58
  • $\begingroup$ Perhaps it is provable for particular surfaces. $\endgroup$
    – VS.
    Commented Jun 13, 2020 at 14:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .