1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.