Wikipedia:Reference desk/Archives/Mathematics/2018 March 8

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.

March 8

I got 0.972 for this probability question

Please check [1]. Thank you. 151.202.5.26 (talk) 12:53, 8 March 2018 (UTC)

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)

To go through some workings for $k=4$: $e^{-{\frac {5}{3}}}\sum _{x=0}^{4}{\frac {1}{x!}}\left({\frac {5}{3}}\right)^{x}=e^{-{\frac {5}{3}}}\left(1+{\frac {5}{3}}+{\frac {25}{18}}+{\frac {125}{162}}+{\frac {625}{1944}}\right)={\frac {10009}{1944*e^{\frac {5}{3}}}}$ which simplifies to your answer of 0.972. Iffy★Chat -- 13:14, 8 March 2018 (UTC)

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. -- ToE 15:40, 8 March 2018 (UTC)

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?

(Specifically, g and x are chosen uniformly from Z*n for some n). — Preceding unsigned comment added by 77.125.78.146 (talk) 16:42, 8 March 2018 (UTC)

Thanks — Preceding unsigned comment added by 77.125.78.146 (talk) 16:39, 8 March 2018 (UTC)

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 $\mathbb {Z} _{2}$ 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)

Let's say I limit the discussion to the multiplicative group mod n (x and g are chosen uniformly from this group). — Preceding unsigned comment added by 77.125.78.146 (talk) 16:45, 8 March 2018 (UTC)

Then still no, with this failing for any such group (except the trivial case of $\mathbb {Z} _{2}^{*}$). Also, please sign your posts with 4 tildes (~~~~). –Deacon Vorbis (carbon • videos) 16:58, 8 March 2018 (UTC)

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)

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.

In the particular case of g^k in a modular group, the faulty reasoning does not lead to a correct conclusion either. For some results showing that g^k can be constrained to certain variables, you may look at our articles Fermat's little theorem (k=p-1) or quadratic residue (k=2). Tigraan^{Click here to contact me} 19:44, 8 March 2018 (UTC)

thanks! 77.125.78.146 (talk) 20:02, 8 March 2018 (UTC)