In a cryptography class, I'm required to write code to check if a number is a quadratic residue mod p. I'm trying to do this by using the Legendre symbol but I'm having some trouble with one exercise in particular:
in this exercise, $p$ is 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
and we want to check if the following number is a quadratic residue mod $p$:
25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803
using the formula: $$\left(\frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \mod p$$
is obviously out of the table.
I also considered finding the prime factors of the number and use the fact that:
$$\left(\frac{ab}{p} \right) = \left(\frac{a}{p} \right)\left(\frac{b}{p} \right)$$
but the number is so big that I think this is not a good approach.
What is a better way of approaching this problem?