Euler Theorem
オイラーの定理はフェルマーの小定理を一般化する：gcd(a,n)=1 ならば a^φ(n)≡1 (mod n)。ここで φ はオイラーのトーシェント関数である。
目的
法が任意の場合へ冪剰余の簡略化を拡張し、RSA 復号の正しさ証明の基礎となる。
メカニズム
a^φ(n)≡1 (mod n) により、a^e mod n は e mod φ(n) で簡略化できる。RSA 復号：ed≡1 mod φ(N) より m^(ed)≡m^(ed mod φ(N))≡m^1≡m (mod N)。
ユースケース
- RSA の正しさ証明
- モジュラーべき乗の簡略化
- 数論のリサーチ