Re: Jacobi symbols of higher degree
From: MB (mb4666_at_yahoo.com)
Date: 10/17/05
 Next message: ddyer_at_realme.net: "Re: needed: reviewers for an implementaion of AES"
 Previous message: lkcl: "Re: advice sought on key/data histogram analysis of rijndael/128 and serpent"
 In reply to: David Wagner: "Re: Jacobi symbols of higher degree"
 Next in thread: Kristian Gjøsteen: "Re: Jacobi symbols of higher degree"
 Reply: Kristian Gjøsteen: "Re: Jacobi symbols of higher degree"
 Reply: David Wagner: "Re: Jacobi symbols of higher degree"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
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 rthpower mod N then J(M)=1
> > if M is not a rthpower 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
 Next message: ddyer_at_realme.net: "Re: needed: reviewers for an implementaion of AES"
 Previous message: lkcl: "Re: advice sought on key/data histogram analysis of rijndael/128 and serpent"
 In reply to: David Wagner: "Re: Jacobi symbols of higher degree"
 Next in thread: Kristian Gjøsteen: "Re: Jacobi symbols of higher degree"
 Reply: Kristian Gjøsteen: "Re: Jacobi symbols of higher degree"
 Reply: David Wagner: "Re: Jacobi symbols of higher degree"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]