How can I calculate $a^{(P-1)/2}\pmod{P}$?
for example $3^{500001}\bmod{1000003}$ given that $1000003$ is prime.
I know that if we square the number $3^{500001}$ the result will be either $1$ or $-1$ modulo $1000003$.
but my question is how to continue?
I have this question as bonus in previous exam.