1
$\begingroup$

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

|improve this question
$\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$

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|.$

|improve this answer
$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.