Re: Jacobi symbols of higher degree
From: Kristian Gjøsteen (kristiag+news_at_item.ntnu.no)
Date: 10/17/05
 Next message: Jan Panteltje: "Secret dot color code on inkjet prints broken"
 Previous message: Joseph Ashwood: "Re: How regularly is the GnuPG source code examined?"
 In reply to: MB: "Re: Jacobi symbols of higher degree"
 Next in thread: David Wagner: "Re: Jacobi symbols of higher degree"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Mon, 17 Oct 2005 19:34:54 +0000 (UTC)
MB <mb4666@yahoo.com> wrote:
>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.
Let p=2rs+1. Then x is a 2rth residue iff x has order s.
If c is a quadratic residue, then the order of c divides rs, and
the order of C divides s.
If c is a nonquadratic residue, then 2r must divide the order of
c, hence 2 divides the order of C, and C is not a 2rth residue.
>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).
Let's consider p=41=2*4*5+1. 1 has square roots 9 and 9. But 9
is a quadratic residue.
 Kristian Gjøsteen
 Next message: Jan Panteltje: "Secret dot color code on inkjet prints broken"
 Previous message: Joseph Ashwood: "Re: How regularly is the GnuPG source code examined?"
 In reply to: MB: "Re: Jacobi symbols of higher degree"
 Next in thread: David Wagner: "Re: Jacobi symbols of higher degree"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
