Fast quadratic norm algorithms

Question

Given rational numbers $a$ and $b$, what is the fastest way to determine whether there are any rational solutions to $a=x^2+by^2$?

I am interested in the case where the numerator and denominator of $a$ have about $4$ digits, and those of $b$ have about $8$ digits. I am willing to restrict attention to solutions where $x$ and $y$ also have numerators and denominators that are not too large, if that will help. I would like to solve a large number of problems of this type, perhaps tens of millions, so efficiency is important. Both $a$ and $b$ will be different for each problem. I would also be interested in heuristics for roughly how often rational solutions exist.

Answer 1

This is a conic, so factoring the discriminant is important, then you can check local solubility at all bad primes. This gives whether it is solvable. With a little extra work (maybe negligible compared to factoring), Simon's algorithm will give you a solution. http://www.ams.org/journals/mcom/2005-74-251/S0025-5718-05-01729-1/ or alternatively Cremona-Rusin http://www.ams.org/journals/mcom/2003-72-243/S0025-5718-02-01480-1/

I would guess that in your application, the main thing is to be able to factor numbers whose size is 12 digits quite efficiently.

As for heuristics, the local root number is probably $-1$ about the half the time at primes dividing the discriminant, and up to evenness of number of such primes I guess these are independent. So global solubility should depend on the number of prime factors. Doing a simple test (with small numbers) on 10000 random trials gave about 36% soluble with 3 prime factors, 20% with 4 prime factors, 10% with 5 prime factors, 5% with 6.