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 合数。但 Carmichael 数通过所有费马测试。
用例
- 素性测试
- 模逆元计算
- 密码学基础
费马小定理：若 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 合数。但 Carmichael 数通过所有费马测试。