Our algorithm (LMM) goes back to Lagrange 1770 and should be better known, as it generalises the well-known continued fraction algorithm for solving Pell's equation. (See a slide-talk (pdf) by Keith Matthews.)
Another approach to the algorithm, using ideals, was discovered by Richard Mollin - see Expositiones Math. 19 (2001) 55-73.
The standard method is due to Gauss - see G.B. Mathews Number Theory, page 97 or John Robertson, Computing in quadratic orders, page 14.
The book L'équation diophantienne du second degré, Alain Faisant, Hermann 1991, has an algorithm for getting all solutions, which also uses continued fractions.
Last modified 7th March 2015
Return to main page