Re: Jacobi symbols of higher degree

From: MB (mb4666_at_yahoo.com)
Date: 10/17/05 

Date: 17 Oct 2005 09:21:44 -0700

David Wagner wrote:
> MB wrote:
> >Infact, the problem from which my question originates is hopefully
> >simpler. Take r=2^k and N product of two distinct large secret primes.
> >Is there any algorithm J(.) such that for each M coprime with N:
> >- if M is a r-th-power mod N then J(M)=1
> >- if M is not a r-th-power mod N then J(M)=-1 with "high probability".
> >(in the case r=2, this J is precisely the ordinary jacobi symbol).
>
> The Jacobi symbol already solves this problem for all k.

I see. But I also see now that the problem I was considering is
slightly different, and boils down to the following:

Let r=2^k, and to make things simpler consider a prime modulus p. Take
c at random in Z*_p. Give a lower bound to the probability that
C=c^(2^k) is *not* a 2^(k+1)-th residue.

If c is a quadratic residue (QR) then C will be a 2^(k+1)-th residue.
But what if c is a non QR (NR)? It is tempting to conclude that then C
is not a 2^(k+1)-th residue either, so that the wanted bound would be
1/2, but this is likely to be false.

For example, if r=2^2=4, c is NR and i= sqrt(-1) mod p is also NR, then
i*c is QR, and has a square root say alpha. Then alpha is an 8th root
of C=2^4 (I haven't checked with numerical data if this situation can
ever arise, though).

Am I missing something obvious? Many thanks for help, suggestions,
pointers to the literature.

-
Michele