How do you solve $x*x = 1009732533765288 \mod 1009732533765289$?

Question

How do you solve $x*x = 1009732533765288 \mod 1009732533765289$? Wolframalpha when you plug that in has the answers as:

$x \equiv 389427288088687 \mod 1009732533765289$

and

$x \equiv 620305245676602 \mod 1009732533765289$

both of $389427288088687 + 620305245676602 = 1009732533765289$. I'm wondering how it solves these so I can write a program to solve these types of equations. Thanks.

Answer 1

I am going to use the fact that the number is odd to avoid technicalities. Since your number has size approximately $10^{15}$ it can be factored in a variety of ways.

One could then solve it for each $p^k$. To do this one can find a primitive root $r$ in the normal way and just letting $x=r^{(p-1)p^k/4}$ or $x=r^{3(p-1)p^k/4}$ (there is no solution if $p$ is not congruent to $1\bmod 4$).

Then one can use the Chinese remainder theorem to find a solution that works for all primes simultaneously.

If the number is even we do the following: If the number is a multiple of $4$ there is no solution, and if the number is not a multiple of $4$ then just make sure that the number you get at the end with CRT is odd and we are good to go.