# calculate $a^{(P-1)/2}\pmod{P}$ for large prime

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.

-

You seem to have misspoken. You know that if you square $3^{500001}$ you get $3^{1000002}$, which by Fermat's Little Theorem must be $1$ modulo $1000003$; there is no possibility of the square of $3^{1000002}$ being $-1$ modulo $1000003$.

But, since there are only two congruence classes whose square modulo $p$ is $1$, namely $1$ and $-1$, you know that $3^{500001}$ itself is either $1$ or $-1$ modulo $p$.

The key to this is Euler's Criterion:

Euler's Criterion. If $p$ is an odd prime and $\gcd(a,p)=1$, then $$x^2 \equiv a\pmod{p}$$ has two solutions if $a^{(p-1)/2}\equiv 1 \pmod{p}$, and no solutions if $a^{(p-1)/2}\equiv -1 \pmod{p}$.

So: $3^{500001} \equiv 1 \pmod{p}$ if and and only if $3$ is a square modulo $1000003$, and $3^{500001}\equiv -1\pmod{p}$ if and only if $3$ is not a square modulo $1000003$.

The question then transforms into "How do we tell if $3$ is a square modulo $1000003$?", or more generally:

Given $a$ and a large prime $P$, $1\lt a\lt P$, how do we tell if $a$ is a square modulo $P$?

The answer is that we do it pretty easily using Legendre or Jacobi symbols, as noted by Bill.

For instance, here, since $3$ and $1000003$ are both congruent to $3$ modulo $4$, quadratic reciprocity says that $$\left(\frac{3}{1000003}\right) = -\left(\frac{1000003}{3}\right) = -\left(\frac{1}{3}\right) = -1,$$ so $3$ is not a square modulo $1000003$, hence $3^{500001}\equiv -1\pmod{1000003}$.

-

By using repeated squaring one can compute this Legendre symbol in $\ O((lg\ p)^3)\$ bit operations. Even better, by using Jacobi symbols, one can compute $\:(a|n)\:$ in $\ O((lg\ a)\ (lg\ n))\$ bit operations. See e.g. Bach & Shallit: Algorithmic Number Theory: Efficient algorithms, pp.110-111

Note: for hand computations one often exploits tricks such as noticing certain factorizations, e.g. pulling out factors of 2. The above linked Wiki articles have some examples of such.

-