Computing Size of Set with Particular Jacobi Symbol in Poly-Time
The Jacobi symbols $(\frac{a}{n})$ which are $\pm 1$ are exactly those for which gcd$(a,n) =1$, and thus the number of these is $\phi(n)$, where $\phi$ is Euler's $\phi$-function. Now, if $n$ is not a perfect square, exactly half of these are $+1$ (this can be seen using the Chinese remainder theorem). Thus, if you know |$J_n^{+1}$|, you know $\phi(n)$. And given $\phi(n)$, you can factor $n$. So there is a polynomial-time algorithm for |$J_n^{+1}$| if and only if factoring $\in$ P.