# Solving ax^2+bxy+cy^2=n fast?

Hi, I was wondering whether equations as ax^2+bxy+cy^2=n can be solved fast. Solve is a general application with overhead. I think of methods such as can be found on www.alpertron.com.ar/METHODS.HTM by Dario Alejandro Alpern, or www.numbertheory.org/php/ by Keith Matthews. It seems to me logic that for instance BinaryQF would facilitate this within Sage.

I wrote some routines using Python (like NZMATH cornacchiamodify, but these have to be optimized via Cython and GMP. Another source is the LMM algorithm. Before I take this route, I want to check that I'm not reinventing the wheel and/or I'm able to cooperate with someone.

edit retag close merge delete

Are a, b, c, n all integers, and are you looking for integer solutions (x,y)?

( 2014-06-22 07:36:42 -0500 )edit

Could you provide a link to the work you have already done?

( 2014-06-29 15:29:51 -0500 )edit

Thanks for all replies! Yes, I'm looking at integers. A few months ago Thilina Rathnayake implemented routines in Sympy (http://thilinaatsympy.wordpress.com/2013/09/14/status-of-the-diophantine-module-2/). This seems to me a good start as Sympy is a standard package. I'll have a 2nd look at my routines and I'll provide a link within a few days (if that's still wanted). Roland

( 2014-06-29 15:45:18 -0500 )edit

Sort by ยป oldest newest most voted

It's a special case, but the pari function qfbsolve(Q,p) solves Q(x,y)=p where Q is a binary quadratic form and p a prime. It would be easy to wrap that function in sage/libs/pari/gp.pyx. For now:

sage: Q = gp.Qfb(1,0,1)
sage: Q
Qfb(1, 0, 1)
sage: Q.qfbsolve(97)
[9, 4]

more

Indeed, there is no code in Sage to solve the quadratic Diophantine in two variables like Alpern's program does. You are welcome to contribute, and I'm willing to help. Contact me through my G+ page if you are interested.

The most immediate task would be to integrate the sympy stuff. I have opened this ticket:

http://trac.sagemath.org/ticket/16590

Until then you can use sympy within Sage:

sage: from sympy.solvers.diophantine import *
sage: from sympy import sympify
sage: var('x,y,m')
(x, y, m)
sage: diop_solve(sympify(x**2 + y**2 - 5))
{(-2, -1), (-2, 1), (2, -1), (2, 1)}
sage: diop_solve(sympify(x**2 - 3*y**2 - 1))
{(-sqrt(3)*(-sqrt(3) + 2)**t/2 + (-sqrt(3) + 2)**t + sqrt(3)*(sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t,
-sqrt(3)*(-sqrt(3) + 2)**t/3 + (-sqrt(3) + 2)**t/2 + (sqrt(3) + 2)**t/2 + sqrt(3)*(sqrt(3) + 2)**t/3)}

more

Hi,

The case of the sum of squares (a=c=1 and b=0) has been implemented recently in trac ticket #16308. It uses factorisation of integers and Cornacchia's algorithm (as well as a naive method for small input but implemented in C).

I agree with Ralf it would be nice to have more general method for quadratic diophantine equations!

Vincent

more

Sage code which wraps some fast Pari functions and implements a fast solver from Will Jagy ('Conway_positive_primitive' and 'Conway_positive_all') can be found at [1].

The main function combines several important cases in a single function:

represented_by_binaryQF(
a, b, c,     # the coefficients
M,           # limit
primitively, # default false
prime,       # default false
verbose      # default true
)


See the many examples given there.

more