Computing Size of Set with Particular Jacobi Symbol in Poly-Time Background

Let $(\tfrac{a}{p})$ denote the Legendre symbol, defined for all integers $a$ and all odd primes $p$ by:

$(\tfrac{a}{p}) = \begin{cases}
\;\;\,0\mbox{ if } a \equiv 0 \pmod{p}
\\+1\mbox{ if }a \not\equiv 0\pmod{p} \mbox{ and for some integer }x, \;a\equiv x^2\pmod{p}
\\-1\mbox{ if there is no such } x. \end{cases}$

For any integer $a$ and any positive odd integer $n$ the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of $n$:

$(\frac{a}{n}) = (\frac{a}{p_1})^{\alpha_1}(\frac{a}{p_2})^{\alpha_2}\cdots (\frac{a}{p_k})^{\alpha_k}\mbox{ where } n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

Fortunately, computing Jacobi symbol can be performed efficiently, without having to know the factorization of $n$.



Let $J_n^{+1} = \{a \in \mathbb{Z}_n^* \mid (\frac{a}{n}) = +1 \}$. Deciding membership in $J_n^{+1}$ is easy. The question is,


  Given an odd $n$, can we compute $\left|J_n^{+1}\right|$ in polynomial 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.