Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the
current reference desk pages.
I got the same result as you when I plugged the numbers in to
WolframAlpha. Where they made that mistake is difficult to tell, but it's not that large a mistake as it doesn't change their conclusion.
Iffy★
Chat --
13:02, 8 March 2018 (UTC)reply
One source of their error could be if they accidentally (or sloppily) truncated e-5/3 ≈ 0.188876 to 0.188 introducing a 0.46% error. Then 0.188(1+5/3+25/18+125/162+625/1944) ≈ 0.967949, rounding to their answer of 0.968. --
ToE15:40, 8 March 2018 (UTC)reply
Exponent of a random group element
Hello,
If I choose a random uniform element g from a finite group, and calcualte g^x for a uniform x, is g^x also uniform?
What do you mean by uniform x exactly? But the way I'm reading the question, then no. With about the smallest counterexample being just for the group, and the exponent being 0 or 1 with equal probability. Then the result certainly isn't uniform. –
Deacon Vorbis (
carbon •
videos)
16:44, 8 March 2018 (UTC)reply
Thanks. I am asking because in Lindell's "Introduction to cryptography" there appears the following lemma: "let G be a finite group, and let m be an arbitrary element in G. Then choosing uniform k in G and setting k'=k*m gives the same distribution for k' as choosing uniform k' in G". The proof is "let g be an arbitrary element in G, then Pr[k * m = g] = Pr[k = g * m^(-1)]. Since k is uniform, the probability that k is equal to the fixed element g * m^(-1) is exactly 1/|G|".
I thought that if we take m=k=g then g^x is also uniform, since we multiply g by a uniform group element (itself) several times. Where does this reasoning fail?
77.125.78.146 (
talk)
17:38, 8 March 2018 (UTC)reply
That reasoning is faulty because the group element"s" you take (g, g, g,.. g) may well each be uniformly chosen, but they are not independently chosen (actually, they are in perfect correlation). Accordingly, the result is not uniform. For a simpler example of this: the expected ("average") value of the product of two independent variables (X*Y) is the product of the expected values, but the expected value of the square of a real random variable (X*X) is always nonnegative.
Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the
current reference desk pages.
I got the same result as you when I plugged the numbers in to
WolframAlpha. Where they made that mistake is difficult to tell, but it's not that large a mistake as it doesn't change their conclusion.
Iffy★
Chat --
13:02, 8 March 2018 (UTC)reply
One source of their error could be if they accidentally (or sloppily) truncated e-5/3 ≈ 0.188876 to 0.188 introducing a 0.46% error. Then 0.188(1+5/3+25/18+125/162+625/1944) ≈ 0.967949, rounding to their answer of 0.968. --
ToE15:40, 8 March 2018 (UTC)reply
Exponent of a random group element
Hello,
If I choose a random uniform element g from a finite group, and calcualte g^x for a uniform x, is g^x also uniform?
What do you mean by uniform x exactly? But the way I'm reading the question, then no. With about the smallest counterexample being just for the group, and the exponent being 0 or 1 with equal probability. Then the result certainly isn't uniform. –
Deacon Vorbis (
carbon •
videos)
16:44, 8 March 2018 (UTC)reply
Thanks. I am asking because in Lindell's "Introduction to cryptography" there appears the following lemma: "let G be a finite group, and let m be an arbitrary element in G. Then choosing uniform k in G and setting k'=k*m gives the same distribution for k' as choosing uniform k' in G". The proof is "let g be an arbitrary element in G, then Pr[k * m = g] = Pr[k = g * m^(-1)]. Since k is uniform, the probability that k is equal to the fixed element g * m^(-1) is exactly 1/|G|".
I thought that if we take m=k=g then g^x is also uniform, since we multiply g by a uniform group element (itself) several times. Where does this reasoning fail?
77.125.78.146 (
talk)
17:38, 8 March 2018 (UTC)reply
That reasoning is faulty because the group element"s" you take (g, g, g,.. g) may well each be uniformly chosen, but they are not independently chosen (actually, they are in perfect correlation). Accordingly, the result is not uniform. For a simpler example of this: the expected ("average") value of the product of two independent variables (X*Y) is the product of the expected values, but the expected value of the square of a real random variable (X*X) is always nonnegative.