Does exist an efficient algorithm to solve the equation $\ ax^2-cy-d=0$?

Question

Given the Diophantine equation: $\ ax^2-cy-d=0$ , the coefficients $\ c$ and $\ d$ are numbers in range of $\ 10^{300} $. Does exist an efficient way to find solution for it?

Answer 1

You want $ax^2 - d \equiv 0 \mod c$. If $(a, c) = 1$, that says $x^2 \equiv d/a \mod c$. So you need to solve the modular square root problem. If $c$ is prime, that can be solved using the Tonelli-Shanks algorithm. If not, you need to factor $c$. For a number on the order of $10^{300}$, that may be beyond the reach of current technology.

Answer 2

It means $c|ay^2-d$ A requirement is that for any prime factor p of c, $\frac da$ is quadratic residue of p, or both a and d are multiple of $p^h$ where $p^h | c$. Given we have all prime factors of c and $\frac da$ is quadratic residue of all p, since there're efficient algorithm to solve square root in finite field, the equation could be solved efficently as soon as we could get all prime factors of c.

Answer 3

Above equation shown below:

ax^2-cy-d=0 -----(1)

For a=1, equation (1) has parametric solution:

x=(12k^2-14k+3)

y=(44k^2-24k+3)

c=(2k^2-6k+3)

d=2k(7k-3)(4k^2-1)

Since above solution is parametric even

if "OP" takes k=(10^300) he can still get

solution for equation (1) for [c,d]> (10^300)