mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-12-07, 21:22   #1
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default 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
akruppa is offline   Reply With Quote
Old 2005-12-07, 21:40   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

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......
R.D. Silverman is offline   Reply With Quote
Old 2006-01-14, 21:56   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
CUDALucas gives all-zero residues fivemack GPU Computing 4 2016-07-21 15:49
Fun with LL residues NBtarheel_33 Data 19 2015-04-21 16:02
residues and non residues of general quadratic congruences smslca Math 0 2012-10-12 06:42
Quadratic Residues Romulas Math 3 2010-05-09 03:27
Fake Residues 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.