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.

-

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.
Now that I think about, the fact that you have a diagonal conic means that you would only have to factor $a$ and $b$, and 8 digits is small enough to have a look-up table. Cremona-Rusin might also be faster for conics like these, Simon is more for large coefficients with small discriminant. –  NAME_IN_CAPS Jun 24 at 23:50