0
$\begingroup$

Let $f(x,y)= ax^2+bxy+cy^2$, or similarly denote it by $(a,b,c)$. This question is about the case $(1,0,p)$ where $p$ is prime. Suppose I have one solution $\bar{x}_1=(x_0,y_0)$ for $f(x,y)=m$ for some odd integer $m$ with at least two prime factors.

Is there an algorithm to find a second solution $\bar{x}_1 \not=(\pm x_0,\pm y_0)$ that is better than $\mathcal{O}(m^2)$ ? Preferably, something much better than that... even something better than $\mathcal{O}(x_0y_0)$ if possible. Of course, brute force works...but is there something better? Specially when $p,m$ start to get bigger trial and error trough $(x,y) \in \mathbb{N}^2$ is not practical.

Edit 1: The solutions are over the integers. The algorithm need not be deterministic, just good in practice with better big-O notation work to find a solution than described above.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Draw a line between $(x_0,y_0)$ and an arbitrary second point, and compute the intersection between this line and the ellipse $x^2+py^2=m$? You should be able to parameterize all solutions using this approach, I think. $\endgroup$
    – Mastrem
    Commented Oct 17, 2023 at 20:52
  • $\begingroup$ are you looking for integer or rational solutions? Must the algorithm be determinstic? $\endgroup$
    – Noam D. Elkies
    Commented Oct 17, 2023 at 21:09
  • $\begingroup$ @NoamD.Elkies Integer solutions. The algorithm need to be deterministic, but better than $\mathcal{O}(m^2)$ or even $\mathcal{O}(x_0y_0)$ would be very nice. $\endgroup$
    – ReverseFlowControl
    Commented Oct 17, 2023 at 22:44
  • $\begingroup$ In certain cases there is no a second solution. Let's take $x^2+3y^2=63$. The only solution is $(x,y)=(\pm6,\pm3)$. So possibly the algorithm, if it exists, is supposed to find a second solution OR to find that there are no other solutions. $\endgroup$
    – G. Melfi
    Commented Oct 18, 2023 at 12:35
  • $\begingroup$ @NoamD.Elkies Sorry, it need NOT be deterministic. G.Melfi the number of "unique" solutions is roughly proportional to the number of factors of $m$, something like that, that is why the condition that $m$ have at least two prime factors. Of course, two odd prime factors....we don't care for $2$ as a factor. $\endgroup$
    – ReverseFlowControl
    Commented Oct 18, 2023 at 13:23

0

Reset to default

You must log in to answer this question.