if $a,b,c$ are selected at random from a large cyclic group, then what could be the probability that $g^{a+b}$=$g^c$? it simply corresponds to the probability that multiplication of two random numbers A and B in group G equals to a given random number C in G
1
$\begingroup$
$\endgroup$
-
3$\begingroup$ Theorem: let $g$ be an element of a finite group $G$, and $a, b$ be integers. Then $g^a = g^b$ if and only if $a$ and $b$ are congruent modulo the order of $g$. $\endgroup$ – fkraiem Jun 21 '17 at 12:45
-
1$\begingroup$ Since this looks a bit like homework or an assignment — what have you tried and/or what research have you done? $\endgroup$ – e-sushi Jun 21 '17 at 13:41
-
$\begingroup$ By the way, the fact that you say that "a,b,c are selected at random from a large cyclic group" may indicate a misunderstanding. In order for exponentiation to make sense; they must be ether "plain" integers, or integers modulo the order of $g$ (or at the very least a multiple thereof, such as the order of $G$). They can't be elements of just any group; what sense would it make if exponents were elliptic curve points, for example? $\endgroup$ – fkraiem Jun 21 '17 at 13:44
-
$\begingroup$ You are right, I meant $a$,$b$ and $c$ are random plain integers $\endgroup$ – Yahya Hassanzadeh Jun 21 '17 at 14:06
-
$\begingroup$ The result should actually be $0$ because, this is (basically) the same question as: What is the probabiltity that two random integers are equal (note that a random integer added with a random integer is another random integer). Also note that we can't sample uniformly at random from an infinite set (because then every number would have probability $0$ of being picked). $\endgroup$ – SEJPM♦ Jun 21 '17 at 20:47
1
$\begingroup$
$\endgroup$
As suggested in the first comment, $g^{a+b}=g^c$ if and only if $a+b$ is congruent to $c$ modulo $Order(g).$
Assuming $a,b$ are chosen at random from $G$, $g^{a+b}$ is uniformly distributed in $G$.
Since $Order(g)$ divides $|G|$, $g^{a+b}$ is uniformly distributed in the equivalence classes that the distinct powers of $g$ induce. Now the uniformity gives that the probability that $$g^{a+b}=g^c$$ for any fixed $c$ is exactly $$\frac{1}{Order(g)}.$$ Of course if $g$ is a generator then $Order(g)=|G|.$
-
$\begingroup$ shouldn't the birthday paradox also play into the probability, after all we are only interested in any such triple without any fixed constant in it? $\endgroup$ – SEJPM♦ Jun 22 '17 at 12:35
-
$\begingroup$ Birthday paradox would apply, for example, to a set of exponents: how many exponents must you have before some subset of three of them satisfies this condition? The question as asked appears to be of the probability that some triple $(a, b, c)$ drawn from some distribution on some space satisfies the condition. If drawn uniformly from $\mathbb{Z}/n\mathbb{Z}$ for $n = \operatorname{ord}(g)$, then there are clearly $n^3$ possible triples, and since for each $(a, b)$ there is a unique $c$ with $a+b \equiv c \pmod n$, there are $n^2$ satisfying the condition, hence probability $n^2/n^3 = 1/n$. $\endgroup$ – Squeamish Ossifrage Jul 22 '17 at 4:33
