Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre symbol $(a/p)$?
By the AKS primality test, it suffices to assume $p$ is prime. I know of two tricks to compute the Legendre symbol: quadratic reciprocity and Euler's criterion. The difficulty with naive application of quadratic reciprocity is that, in the worst case, I am led to factor, but I don't know how to do this efficiently. On the other hand, Euler's criterion naturally leads to an attractive repeated squaring algorithm, but the final multiplications are between integers of length at least $O(p)$.
Here's a related question. The accepted answer indicates that quadratic reciprocity should solve my problem, but perhaps that answer implicitly uses a factoring oracle. If not, I would love a reference that shows "the complexity of the usual computation with the laws of quadratic reciprocity is logarithmic in $p$."
Best Answer
For quadratic reciprocity, you need the Jacobi symbol. It's an extension of the Legendre symbol to composite $p$ that still satisfies quadratic reciprocity, so you can just apply quadratic reciprocity to your heart's content without worrying about primality. The Jacobi symbol does not generally tell you whether a number is a perfect square, so it doesn't have the same interpretation as the Legendre symbol, but it agrees with the Legendre symbol whenever $p$ is prime (so it will tell you the answer in your case, even though the intermediate results are a little strange).
However, Euler's criterion already works in polynomial time. You want to compute $a^{(p-1)/2}$ modulo $p$. As you observed, repeated squaring is a good way to deal with the fact that the exponent $(p-1)/2$ is large. Aside from that, you just need to do arithmetic modulo $p$, since you can reduce each intermediate calculation modulo $p$ before continuing. Thus, it can be done in polynomial time. (In your question, you said you need integers of length $p$, but it should be $\log p$.)