mersenneforum.org > Math Residues in subgroups
 Register FAQ Search Today's Posts Mark Forums Read

 2005-12-07, 21:22 #1 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Residues in subgroups 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
2005-12-07, 21:40   #2
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 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......

 2006-01-14, 21:56 #3 akruppa     "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

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack GPU Computing 4 2016-07-21 15:49 NBtarheel_33 Data 19 2015-04-21 16:02 smslca Math 0 2012-10-12 06:42 Romulas Math 3 2010-05-09 03:27 jinydu Lounge 1 2008-09-16 17:02

All times are UTC. The time now is 15:27.

Sun Jan 17 15:27:53 UTC 2021 up 45 days, 11:39, 0 users, load averages: 2.81, 2.56, 2.41