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

savecancel

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]

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

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)}

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.

[1] http://oeis.org/wiki/User:Peter_Lusch...