20051207, 21:22  #1 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Residues in subgroups
It is plain that if qp1, then the probability that an element of (Z/Zp)* chosen uniformly at random is in the subgroup of qth powers with probability 1/q. This is simply because there are (p1)/q such powers. So if we fix p and q and let r vary, 1/qth of the r are such a power.
What if we fix q and r, and let p vary over primes that are 1 (mod q) instead? Is it still true that with p chosen uniformly at random from those primes, r is a qth power with probability 1/q? It seems to me that it should be, but is this proven? For example, for q=2, r=2 we have that p must be 1,7 (mod 8) and these primes are asymptotically as dense as the 3,5 (mod 8) primes, so the probability is indeed 1/2. But what about large q? Alex 
20051207, 21:40  #2  
Nov 2003
1110100100100_{2} Posts 
Quote:
by Clauss Schnorr on this a while back. I don't have my references with me. He was looking at the *uniformity* of distribution, and I *believe* he may have found some results, [based on R.H] that the distribution is *not* uniform. He was studying some uniformity conditions arising from DiffieHellman key exchange. Do a search on his name along with "Diffie Hellman" and it should turn up. Note also that part of the problem is that once you say "choose p uniformly", then you must have an upper bound on p. There is no uniform distribution over all of Z [as I am sure you know]. Such a distribution does exist in Bayesian statistics as an "improper prior", but it must be convolved with a sample distribution (under an integration of course) to get a posterior. I am at a temporary location for my job and all my references are many miles away in my old office...... 

20060114, 21:56  #3 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
I forgot to reply to this.
I had kinda expected that there'd be a simple and probably classical answer, didn't think it'd be an open question. Thanks for the pointers, Bob. I glanced over Schnorr's publication list but didn't immediately spot the paper in question. I'll look more carefully at a later time. Alex 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
CUDALucas gives allzero residues  fivemack  GPU Computing  4  20160721 15:49 
Fun with LL residues  NBtarheel_33  Data  19  20150421 16:02 
residues and non residues of general quadratic congruences  smslca  Math  0  20121012 06:42 
Quadratic Residues  Romulas  Math  3  20100509 03:27 
Fake Residues  jinydu  Lounge  1  20080916 17:02 