Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
Thanks Alex!!!! –  user4811 Sep 10 '13 at 1:34
1  
@Alex For the left-to-right implication in the first equivalence to hold true, you should probably add that $p \nmid a$. –  hakoja Sep 10 '13 at 9:32
    
thanks yes you are right –  Alex Sep 10 '13 at 10:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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