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

Answer 2

You don't need to search for all combinations. A rough outline of a simple naive implementation would be:

• Consider each integer i in the range [1..trunc(sqrt(p))].
• Calculate sqrt(p-i^2) and check if it is an integer. If so you are done.
• If not continue to the next i.

Would this suffice for your needs? It will work fine for relatively small p, but obviously would be slow for the sort of large primes used in cryptography.

Answer 3

Well I could recommended you reread Fermat's 4n+1 Theorem.

If software engineers use right tools for the job, thy have simple solutions. My Mathematica function:

P[p_] := Reduce[-p + x^2 + y^2 == 0, {x, y}, Integers]

Examples:

Finding solutions for first few primes p which are 1 or 2 (mod 4).

P /@ {2, 5, 13, 17, 29, 37, 41, 53, 61}