What's the fastest algorithm to represent a prime as sum of two squares?

Question

I could use two loops to check for all combinations of two integers that less than p prime, but it's very inefficient. Is there a better algorithm to approach this problem? Any idea?

Where p mod 4 = 1.

Thanks,

Answer 1

You can try using the Hermite-Serret algorithm.

You can also find a good list of algorithms on this math.se page: https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime

See especially, Robin Chapman's answer: https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime/5883#5883