費馬小定理在證明 ElGamal 簽名正確性中的作用
在有關ElGamal 簽名方案的 Wikipedia 文章中，費馬小定理用於以下正確性證明：
從 ElGamal 中的簽名生成我們可以得出：
$$ H(m) \equiv xr + sk \pmod {p-1} $$ 然後 - 文章指出 - 費馬小定理暗示以下內容：
$$ \begin{align} g^{H(m)} &\equiv g^{xr}g^{ks} &\pmod p\ &\equiv (g^x)^r(g^k)^s &\pmod p\ &\equiv (y)^r(r)^s &\pmod p \end{align} $$ 這個證明對我來說很有意義，我只是想知道，這里以什麼方式使用費馬小定理，而不僅僅是取冪的正常屬性。
感謝fgrieu 的上述評論以及此處的以下引用 (PDF)：
定理：
讓 $ p $ 是一個素數，讓 $ a $ 是一個不能被整除的數 $ p $ . 那麼如果
$$ r \equiv s \pmod {p − 1} $$ 我們有 $$ a^r \equiv a^s \pmod p $$簡而言之，當我們工作時 $ \mod p $ , 可以取指數 $ \mod{p − 1} $ .
我（認為我）理解，第一步（隱式）如何依賴於費馬小定理：
$$ \begin{align} g^{H(m) \pmod{p-1}} &= g^{xr+sk \pmod{p-1}} \ g^{H(m)} &\equiv g^{xr+sk} \pmod p \end{align} $$
為了 $ c\ne0 $ , 的定義 $ a\equiv b\pmod c $ 是： $ \exists d\in\mathbb Z $ 這樣 $ a=b+cd $ .
將該定義應用於 $ H(m)\equiv xr+sk\pmod{p-1} $ , 我們有 $ \exists d\in\mathbb Z $ 這樣 $ H(m)=xr+sk+(p-1)d;\text{ (equ. 1)} $ .
費馬小定理是 $ p $ 素數和 $ g\not\equiv0\pmod p $ , 它認為 $ g^{p-1}\equiv1\pmod p;\text{ (equ. 2)} $ .
我們現在可以計算
$$ \begin{align} g^{H(m)} &\equiv g^{xr+sk+(p-1)d}&\pmod p&&\text{ (by equ. 1)}\ &\equiv {(g^x)}^r;{(g^k)}^s;(g^{p-1})^d&\pmod p&&\text{ (rearanging)}\ &\equiv {(g^x)}^r;{(g^k)}^s;1^d&\pmod p&&\text{ (by equ. 2)}\ &\equiv {(g^x)}^r;{(g^k)}^s&\pmod p&&\text{ (simplifying)}\ &\equiv y^r;r^s&\pmod p&&\text{ (by definition of }y\text{ and }r\text{)} \end{align} $$