Euler Theorem
欧拉定理推广费马小定理：若 gcd(a,n)=1，则 a^φ(n)≡1 (mod n)，φ 为欧拉函数。
用途
推广模幂简化至任意模数，RSA 解密正确性证明基础。
机制
欧拉定理：当 a 与 n 互素时 a^φ(n)≡1 (mod n)。RSA 中私钥指数 d 满足 ed≡1 (mod φ(N))，因此解密运算 m^(ed) ≡ m^(ed mod φ(N)) ≡ m^1 ≡ m (mod N)，即密文的幂指数可先对 φ(N) 降次再计算，大幅减少模乘次数——这是 RSA 加解密在计算上可行的核心依据。
用例
- RSA 正确性证明
- 模幂简化
- 数论