1
$\begingroup$

Why is $g^e \mod p = g^{e \mod (p-1)} \mod p$ if p is prime. I don't get it. It follows from Fermat's little theorem.

$\endgroup$

1 Answer 1

4
$\begingroup$

Fermat's little theorem $$a^p \equiv a \pmod{p} \Leftrightarrow a^{p-1} \equiv 1 \pmod{p}(p \nmid a)$$

so next divides $e$ with $p-1$:$$e=(p-1)r+s;$$ $$s\equiv e \pmod{p-1};$$ so we get $$g^{(p-1)r+s} \pmod {p} \equiv (g^{p-1})^rg^s \pmod{p}$$ follow Fermat's little theorem $g^{p-1} \equiv 1\pmod{p}$ finally we get :$$g^{(p-1)r+s} \pmod {p} \equiv (g^{p-1})^rg^s \pmod{p} \equiv g^s \pmod{p}$$ $\Leftrightarrow$ $$g^e \pmod{p} \equiv g^{e \pmod{p-1}} \pmod{p}$$

$\endgroup$
1
  • 1
    $\begingroup$ @Alex For the left-to-right implication in the first equivalence to hold true, you should probably add that $p \nmid a$. $\endgroup$
    – hakoja
    Sep 10, 2013 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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