4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Dec 11, 2010 at 14:55
  • 1
    $\begingroup$ @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). $\endgroup$
    – Sadeq Dousti
    Dec 11, 2010 at 16:38
  • $\begingroup$ Thank you for the reference! I'm not familiar with the topic, but it is nice to learn something new. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Dec 11, 2010 at 16:46
  • $\begingroup$ @Hsien-Chih: You're most welcome! $\endgroup$
    – Sadeq Dousti
    Dec 11, 2010 at 18:00

1 Answer 1

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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}|$? $\endgroup$
    – Sadeq Dousti
    Dec 11, 2010 at 16:48
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Dec 11, 2010 at 16:53
  • 1
    $\begingroup$ 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? $\endgroup$
    – Tsuyoshi Ito
    Dec 11, 2010 at 21:33
  • 1
    $\begingroup$ @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. $\endgroup$
    – Peter Shor
    Dec 12, 2010 at 1:28
  • $\begingroup$ @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.” $\endgroup$
    – Tsuyoshi Ito
    Dec 15, 2010 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.