1

The question is simple: given $\sum_i e_i \equiv e \mod m$, what do we know about $g^{\sum_i e_i} \mod m$? I know it's certainly not always $g^e \mod m$ as the following counterexample shows:

Let $e_1 = 2, e_2 = 3, m = 5, g = 2$,

$g^{e_1} \equiv 4 \mod 5$

$g^{e_2} \equiv 3 \mod 5$

$e_1 + e_2 \equiv 0 \mod 5$ but $g^{e_1+e_2} \equiv 2 \mod 5$, not $1$.

I wonder can we say anything about $g^{\sum_i e_i} \mod m$, just given $\sum_i e_i \equiv e \mod m$? Or under what assumption we can have $g^{\sum_i e_i} \equiv g^e \mod m$? Thanks!

qweruiop
  • 374

1 Answers1

1

We have $\sum e_i \equiv e$ implies $\sum e_i = e + km$ for some $k\in\mathbb{N}$ so $$g^{\sum e_i} = g^e g^{mk} \equiv g^e~~~~\text{if}~~~~g^m\equiv 1$$ Since we have no knowledge what the value of $k$ is (assuming we are only given $\sum e_i$ and $e$), this is likely the best criterion we can come up with in general.

Winther
  • 24,478