Euler Theorem
Le théorème d'Euler généralise le petit théorème de Fermat : si gcd(a,n)=1, alors a^φ(n)≡1 (mod n), où φ est la fonction indicatrice d'Euler.
Objectif
Étendre la simplification des exponentiations modulaires à des modules arbitraires ; fondement de la preuve de correction du déchiffrement RSA.
Mécanisme
a^φ(n)≡1 (mod n) permet de simplifier a^e mod n par e mod φ(n). Déchiffrement RSA : m^(ed)≡m^(ed mod φ(N))≡m^1≡m (mod N), car ed≡1 mod φ(N).
Cas d’usage
- Preuve de correction de RSA
- Simplification d'exponentiation modulaire
- Théorie des nombres