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?