0
$\begingroup$

In a related post: Algorithm for solving binary quadratic Diophantine equations (BQDE) and its CTC there was a conclusion that with regard to general binary quadratic diophantine equation (with all non-zero coefficients), the solutions (if existent) can be found in exponential time.

However, is this also the case for simple hyperbolic case (i.e. where $A$ and $C$ are zero, leading to form: $Bxy + Dx + Ey + F = 0$)? Alpertron (https://www.alpertron.com.ar/METHODS.HTM) shows a method for such a case which involves finding all integer divisors of $DE-BF$ - a task which can be tricky for large coefficients. For certain, sufficiently large coefficients Alpertron's method would imply that this can be computed in sub-exponential time (using GNFS).

Is there any algorithm to be used for SHCDE which would find the solutions in less than exponential time (unlike standard ones for general BQDE)?

$\endgroup$
  • $\begingroup$ Yes, it's possible to find a solution to those equations in exponential time. This follows trivially, as your problem is a special case of BQDE (namely, the special case where we take $A=C=0$), so any algorithm for BQDE can also be used to solve your problem. Your question seems like it could be clearer about the distinction between an upper bound and a lower bound. Just because there exists an exponential-time algorithm, doesn't necessarily mean that this is the fastest possible algorithm. Would you like to edit it to focus on asking for a lower bound? $\endgroup$ – D.W. Dec 21 '16 at 4:58
  • $\begingroup$ Incidentally, Alpertron's method does not imply that a solution can be found in sub-exponential time. You can factor in sub-exponential time, but Alperton's method still requires enumerating all divisors of a large number, and there might be exponentially many divisors. $\endgroup$ – D.W. Dec 22 '16 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.