---
title: Fermat Little Theorem
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# Fermat's Little Theorem
若 $p$ 是質數, $a \in Z_p^*$ 且 $a, p$ 互質，則 :
$$
a^{p-1} \equiv 1\ (mod\ p)
$$

## Proof
- 若 $ma \equiv na\ (mod\ p)$ 則 $m \equiv n\ (mod\ p)$
- $\{a, 2a, 3a, ..., (p-1)a\}\ mod\ p$ 的結果為 $\{1, 2, 3, ..., (p-1)\}$ 的排列組合

$$
\begin{split}
\prod_{i=1}^{p-1}(ia) &\equiv \prod_{i=1}^{p-1}(i)\ (mod\ p)\\
a^{p-1}(p-1)! &\equiv (p-1)!\ (mod\ p)\\
a^{p-1} &\equiv 1\ (mod\ p)
\end{split}
$$

## 反元素
更進一步, 若想找 $a$ 的反元素 $a^{-1}$

$$
\begin{split}
a^{p-1} &\equiv 1 \\
a \times a^{p-2} &\equiv 1
\end{split}
$$

跟這個式子比較
$$
a \times a^{-1} \equiv 1
$$

得到
$$
a^{-1} \equiv a^{p-2}
$$