Residues in subgroups

[akruppa]

It is plain that if q|p-1, then the probability that an element of (Z/Zp)* chosen uniformly at random is in the subgroup of q-th powers with probability 1/q. This is simply because there are (p-1)/q such powers. So if we fix p and q and let r vary, 1/q-th 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 q-th 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

[R.D. Silverman]

Originally Posted by akruppa

It is plain that if q|p-1, then the probability that an element of (Z/Zp)* chosen uniformly at random is in the subgroup of q-th powers with probability 1/q. This is simply because there are (p-1)/q such powers. So if we fix p and q and let r vary, 1/q-th 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 q-th 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

Actually, unless my memory is failing me, there was some work done
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
Diffie-Hellman 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......

[akruppa]

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