solving quadratic congruence but overflows in mathematica

Question

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.

Now I know I can use the PowerMod function, but what should I do if the original code was x= Mod[a*2^((p - 1)/4), p]?

Answer 1

Yes, of course, always use PowerMod to compute large powers. I don't see an issue with your second formula, just do

Mod[a * PowerMod[2, (p-1)/4, p], p]