CODEWITHSUNDEEP
algorithmmathnumber-theory
roxrook
roxrook

Reputation: 13853

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

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,

Upvotes: 4

Views: 2782

Answers (3)

Aryabhatta
Aryabhatta

Reputation:

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

Upvotes: 5

Margus
Margus

Reputation: 20038

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}

enter image description here

Upvotes: 0

David Heffernan
David Heffernan

Reputation: 612964

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.

Upvotes: 2

Related Questions