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 + 3*b^*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?