Fermat Little Theorem
フェルマーの小定理：p が素数で gcd(a,p)=1 ならば a^(p-1)≡1 (mod p)。素数判定や法の逆元の基礎である。
目的
高速なモジュラーべき乗の簡略化と、素数判定の理論的基礎を与える。
メカニズム
a^(p-1)≡1 (mod p) から a^(-1)≡a^(p-2) (mod p)（法の逆元）が導ける。フェルマー素数判定：ランダムな a で a^(n-1)≡1 (mod n) を確認し、失敗なら n は合成数と確定する。ただしカーマイケル数はすべてのフェルマーテストを通過してしまう。
ユースケース
- 素数判定（フェルマーテスト）
- モジュラ逆元の導出
- クリプトの理論的基礎