Solving $x^2 + y^2 = M$ with $M$ prime

Question

This question is related with the topic: Solving $x^2 + y^2 = M$ over integers

I have understood the formula used to determine $(x,y)$ such that $x^2+y^2=M$ with $M$ composite. But what if $M$ is a large prime such as $M=1000000241$ do I have to do only bruteforcing? Are there other methods?

EDIT:

I know that $M$ must be a prime of the form $4k+1$ but how to find $(x,y)$?

Thanks

Answer 1

The bad news is that, yes, brute force is [currently] your only real recourse for large primes.

The good news is that primes which are the sum of two squares have a unique representation in that form… so once you find a representation, you’re done.

Answer 2

$x^2 + y^2 = M$ represents a circle with $(0,0)$ as its center and $\sqrt{M}$ as its radius.

So once you plot this circle on a Cartesian system, then you should be able to find all values of $x$ and $y$ that satisfy your equation.

(I'm assuming you're allowed the use of a graphing calculator.)