Can one solve Legendre's equation a x^2 + b y^2 + c z^2 = 0 efficiently? We show the answer is 'yes' if it is certified that it is solvable at all: if one is given n,p,q with a | n^2 + bc b | p^2 + ca c | q^2 + ab then solutions xyz can be attained in seconds. In principle this result is already know since provably effective 3D-lattice reduction methods exist (e.g. Vallee) but no working code is available. In practice Legendre's method, combined with some 2D-lattice reduction, works quickly. The hybrid method here seems to be the most rapid procedure when abc has up to a few hundred digits, at least. Gauss's (first) algorithm is also available but suffers from some defects making it unlikely to succeed quickly for large problems. Code available below.
Choose yer weapon: