[math-fun] mult. group of GF(p) uniformly distributed?
Is this known or conjectured with a conjecture name? If X is a uniform random distribution over [0,p-1], p prime, is g^X a uniform random distribution, for a generator g ?
Let p=7, g=2. For X in [0,6], g^X takes on the values 1, 2, 4, 1, 2, 4, 1. This isn't uniform: it takes the value 1 thrice, the values 2 and 4 twice, and 3, 5, and 6 never. Am I misunderstanding your question? On Fri, Oct 14, 2016 at 4:08 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Is this known or conjectured with a conjecture name?
If X is a uniform random distribution over [0,p-1], p prime, is g^X a uniform random distribution, for a generator g ?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
But 2 is not a generator of [0,6] = Z/7. For a generator g of Z/p, the powers g^k will be all distinct for 0 <= k <= p-1; hence {g^k | 0 <= k < p} = Z/p. So g^X is in fact uniform on Z/p when X is. —Dan
On Oct 14, 2016, at 2:25 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Let p=7, g=2. For X in [0,6], g^X takes on the values 1, 2, 4, 1, 2, 4, 1. This isn't uniform: it takes the value 1 thrice, the values 2 and 4 twice, and 3, 5, and 6 never.
Am I misunderstanding your question?
On Fri, Oct 14, 2016 at 4:08 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Is this known or conjectured with a conjecture name?
If X is a uniform random distribution over [0,p-1], p prime, is g^X a uniform random distribution, for a generator g ?
I did misunderstand. However, I think we have an off-by-one problem: g^k will never, in fact, take on the value 0. It will be equally distributed over the nonzero values, of which there are only (p-1). On Fri, Oct 14, 2016 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
But 2 is not a generator of [0,6] = Z/7. For a generator g of Z/p, the powers g^k will be all distinct for 0 <= k <= p-1; hence {g^k | 0 <= k < p} = Z/p.
So g^X is in fact uniform on Z/p when X is.
—Dan
This isn't uniform: it takes the value 1 thrice, the values 2 and 4 twice, and 3, 5, and 6 never.
Am I misunderstanding your question?
On Fri, Oct 14, 2016 at 4:08 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Is this known or conjectured with a conjecture name?
If X is a uniform random distribution over [0,p-1], p prime, is g^X a uniform random distribution, for a generator g ?
On Oct 14, 2016, at 2:25 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Let p=7, g=2. For X in [0,6], g^X takes on the values 1, 2, 4, 1, 2, 4,
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, definitely an off-by-one problem! —Dan
On Oct 14, 2016, at 3:12 PM, Allan Wechsler <acwacw@gmail.com> wrote:
I did misunderstand. However, I think we have an off-by-one problem: g^k will never, in fact, take on the value 0. It will be equally distributed over the nonzero values, of which there are only (p-1).
On Fri, Oct 14, 2016 at 6:02 PM, Dan Asimov <dasimov@earthlink.net> wrote:
But 2 is not a generator of [0,6] = Z/7. For a generator g of Z/p, the powers g^k will be all distinct for 0 <= k <= p-1; hence {g^k | 0 <= k < p} = Z/p.
So g^X is in fact uniform on Z/p when X is.
—Dan
On Oct 14, 2016, at 2:25 PM, Allan Wechsler <acwacw@gmail.com> wrote:
Let p=7, g=2. For X in [0,6], g^X takes on the values 1, 2, 4, 1, 2, 4,
This isn't uniform: it takes the value 1 thrice, the values 2 and 4 twice, and 3, 5, and 6 never.
Am I misunderstanding your question?
On Fri, Oct 14, 2016 at 4:08 PM, Henry Baker <hbaker1@pipeline.com> wrote:
Is this known or conjectured with a conjecture name?
If X is a uniform random distribution over [0,p-1], p prime, is g^X a uniform random distribution, for a generator g ?
Abelian group problems are nearly always easier when phrased additively. The map Z/nZ \to Z/nZ given by x \to ex has cyclic image <gcd(e,n)+nZ> of order n/gcd(e,n), cyclic kernel <n/gcd(e,n)+nZ> of order gcd(e,n). Thus, returning to the multiplicative world, the x \to x^e map modulo p has image of order (p-1)/gcd(e,p-1) and it is gcd(e,p-1)-to-1. Isolating out that fact about x \to ex modulo n makes various little arguments in elementary number theory inexorable rather than the least bit tricky. E.g., if g is a primitive root modulo p then the other primitive roots are exactly g^k for gcd(k,p-1)=1. Jerry Shurman
participants (4)
-
Allan Wechsler -
Dan Asimov -
Henry Baker -
Jerry Shurman