See Solving the Pell Equation (reviewed here). You probably know Lenstra Jr.'s article in the AMS Notices. There's also Primes of the form $x^2 + ny^2$ by Cox.