Let P>3 be a prime and let K be in {1,2,3,4,7}. P has a representation as x^2+K*y^2 with x,y>0 integers in these cases: * If K=1: iff P=4*m+1. This is the case P=sum of two squares. * If K=2: iff P=8*m+1 or 8*m+3. * If K=3: iff P=6*m+1. This and the preceding two were understood by Euler and Fermat. * If K=4: iff P=4*m+1. This one is basically the same as K=1. * If K=7: iff P mod 28 = 1,9,11,15,23, or 25. Further, whenever P is prime and such a representation exists, it is unique. Further, if N is nonprime with GCD(N,6)=1 then you can factor N into primes and/or squared primes, represent them, then multiply the (+-x+-i*sqrt(K)*y) complex number forms of the reps together to represent N in all possible ways. This also allows you to rapidly count the number of representations once you know N's prime factorization. For every other K>0, the class number of the positive quadratic forms with the same discriminant as x^2+K*y^2 exceeds 1 so that unique factorization in the complex number field fails so that the preceding paragraph fails. Now, to FIND the unique representation of prime P>3 as x^2+K*y^2 with x,y>0 integers (K fixed), do the following. 1.solve for d so that d^2 + K is divisible by P and 0<d<P/2. [Thjs can be done fast with Shanks-Tonelli algorithm.] 2.perform the Euclidean algorithm on (d,P): q = P; LoopForever{ if( P-d*d is K times a square ){ output the representation of P = d*d+K*square and stop. } t = d; d = q mod d; q = t; } I claim this is guaranteed to work to find the rep whenever P is prime, P>3, K in {1,2,3,4,7} and P is such that a rep exists; and in these cases the loop only gets iterated a logarithmic number of times at most. -- Warren D. Smith http://RangeVoting.org  <-- add your endorsement (by clicking "endorse" as 1st step)