# 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?

• Out of curiosity: is there a motivation to the question? And, is there any study on the the number of elements in $\mathbb{Z_n^*}$ with $(\frac{a}{n}) = +1$? The formulas with help. – Hsien-Chih Chang 張顯之 Dec 11 '10 at 14:55
• @Hsien-Chih: Sure there is! A lot of cryptography schemes depend on this. See for instance, the work by Blum et al. (which is the main motivation for asking this question). – M.S. Dousti Dec 11 '10 at 16:38
• Thank you for the reference! I'm not familiar with the topic, but it is nice to learn something new. – Hsien-Chih Chang 張顯之 Dec 11 '10 at 16:46
• @Hsien-Chih: You're most welcome! – M.S. Dousti Dec 11 '10 at 18:00

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.
• Thanks Peter. I have a question though. Consider the following quote from Blum et al.: "A Blum integer enjoys an elegant structural property. Namely, $|J_n^{+1}|=|J_n^{-1}|$. More generally, we define an integer $n$ to be regular if it enjoys the above property." Does it mean that, for some irregular integers, $|J_n^{+1}|\ne|J_n^{-1}|$? – M.S. Dousti Dec 11 '10 at 16:48
• I realize I've been assuming the integer $n$ is square-free. If it's not square-free, then we may not have |$J_n^{+1}$| = |$J_n^{-1}$|. Let me fix my answer. – Peter Shor Dec 11 '10 at 16:53
• @Tsuyoshi: Good question. I don't know how to factor arbitrary integers, given an algorithm for factoring square-free integers. However, I think we will have |$J_n^{+1}$|$=$|$J_n^{-1}$| except when $n$ is a square, so the algorithm works except on perfect squares. It's easy to take the square root of perfect squares. – Peter Shor Dec 12 '10 at 1:28