Quote:
Originally Posted by SPWorley

Cornacchia's algorithm can be used in this case too, generally you can solve a^2 + d*b^2 = p, with 0<d<p. There is a modified algorithm for a^2 + d*b^2 = 4p. Crandall/Pomerance: Prime Numbers (Algorithm 2.3.12 +) is another reference.