Breaking a prime p into a^2 + 3* b^2

[SPWorley]

I'm playing with cubic reciprocity formulas.

From that link, it states "A theorem of Fermat states that every prime p ≡ 1 (mod 3) is the sum of a square and three times a square: p = a^2 + 3b^2"

How would you go about finding a and b given p?

Is there a better strategy than brute force, iterating b=1, b=2, b=3, b=4.. etc and seeing if the remainder (p-3*b^2) is a square?
There are efficient square-detecting routines, but even if they're cheap, you could be iterating up to sqrt(p) times!

How about the case where p=a^2 +2* b^2, which comes up when dealing with quartic reciprocity?

[R.D. Silverman]

Originally Posted by SPWorley

I'm playing with cubic reciprocity formulas.

From that link, it states "A theorem of Fermat states that every prime p ≡ 1 (mod 3) is the sum of a square and three times a square: p = a^2 + 3b^2"

How would you go about finding a and b given p?

]

Factor p over Q(sqrt(-3)). See H. Cohen's book on Algebraic Number Theory.
I believe that a variation of Cornachia'a algorithm is used, but my memory
could be faulty. It's been a long time since I looked at this kind of stuff.

[Gammatester]

Originally Posted by SPWorley

How about the case where p=a^2 +2* b^2, which comes up when dealing with quartic reciprocity?

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.

[SPWorley]

Thanks very much for the references.. it's all there in Crandall/Pomerance.

Pretty straightforward, too!

I appreciate it.