<p>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. </p>

CC BY-SA 2.5
2010-12-11T16:48:23.607Z
Thanks Peter. I have a question though. Consider the following quote from [Blum et al.](http://link.aip.org/link/SMJCAT/v20/i6/p1084/s1): "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}|$?
Sadeq Dousti
CC BY-SA 2.5
2010-12-11T16:53:05.820Z
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 
CC BY-SA 2.5
2010-12-11T21:33:19.883Z
I understand the “if” direction, but cannot follow the “only if” direction.  Once you have a polynomial-time algorithm for factoring square-free integers, how do you factor an integer which is not necessarily square-free in polynomial-time?
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-12T01:28:23.737Z
@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 
CC BY-SA 2.5
2010-12-15T23:26:29.070Z
@Peter: That seems to work.  Thanks for the explanation!  Can you edit the answer to incorporate this?  I think the only change needed is to change “square-free (i.e., …)” in the first sentence to “not a perfect square.”
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T02:44:59.167Z
@Tsuyoshi: Done.
Peter Shor 
CC BY-SA 2.5
2010-12-11T16:16:22.200Z
2010-12-16T02:43:19.440Z
2010-12-16T02:43:19.440Z
Peter Shor 
<h3>Background</h3>

<p>Let $(\tfrac{a}{p})$ denote the <a href="http://en.wikipedia.org/wiki/Legendre_symbol" rel="nofollow">Legendre symbol</a>, defined for all integers $a$ and all odd primes $p$ by:</p>

<p>$(\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}$
</p>

<p>For any integer $a$ and any positive odd integer $n$ the <a href="http://en.wikipedia.org/wiki/Jacobi_symbol" rel="nofollow">Jacobi symbol</a> is defined as the product of the Legendre symbols corresponding to the prime factors of $n$:</p>

<p>$(\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}$
</p>

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

<hr>

<p>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,</p>

<blockquote>
  <p>Given an odd $n$, can we compute $\left|J_n^{+1}\right|$ in polynomial time?</p>
</blockquote>

CC BY-SA 2.5
2010-12-11T14:55:15.207Z
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 張顯之
CC BY-SA 2.5
2010-12-11T16:38:24.470Z
@Hsien-Chih: Sure there is! A lot of cryptography schemes depend on this. See for instance, the work by [Blum et al.](http://link.aip.org/link/SMJCAT/v20/i6/p1084/s1) (which is the main motivation for asking this question).
Sadeq Dousti
CC BY-SA 2.5
2010-12-11T16:46:43.160Z
Thank you for the reference! I'm not familiar with the topic, but it is nice to learn something new.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-11T18:00:33.930Z
@Hsien-Chih: You're most welcome!
Sadeq Dousti
<cc.complexity-theory><ds.algorithms><nt.number-theory>
Computing Size of Set with Particular Jacobi Symbol in Poly-Time
Sadeq Dousti
# Computing Size of Set with Particular Jacobi Symbol in Poly-Time

(Asked by: username_0 on 2010-12-11)

### Background

Let $(\tfrac{a}{p})$ denote the [Legendre symbol](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, ds.algorithms, nt.number-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: @Hsien-Chih: Sure there is! A lot of cryptography schemes depend on this. See for instance, the work by [Blum et al.](http://link.aip.org/link/SMJCAT/v20/i6/p1084/s1) (which is the main motivation for asking this question).  
> **username_1**: Thank you for the reference! I'm not familiar with the topic, but it is nice to learn something new.  
> **username_0**: @Hsien-Chih: You're most welcome!  

---

## 1 answers

### Answer by username_2 on 2010-12-11. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks Peter. I have a question though. Consider the following quote from [Blum et al.](http://link.aip.org/link/SMJCAT/v20/i6/p1084/s1): "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}|$?  
> **username_2**: 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.  
> **username_3**: I understand the “if” direction, but cannot follow the “only if” direction.  Once you have a polynomial-time algorithm for factoring square-free integers, how do you factor an integer which is not necessarily square-free in polynomial-time?  
> **username_2**: @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.  
> **username_3**: @Peter: That seems to work.  Thanks for the explanation!  Can you edit the answer to incorporate this?  I think the only change needed is to change “square-free (i.e., …)” in the first sentence to “not a perfect square.”  
> **username_2**: @Tsuyoshi: Done.  

---

