I am solving $x^2 \equiv a\pmod{p}$, here $a = 73$ and $p = 370370384407407431$.
My Mathematica code is
x = Mod[a^((p + 1)/4), p]
but it overflows.
Is there anything I can do to reduce the algorithm so that it can solve the large numbers? Thank you a lot!