L'indicateur d'Euler
Fonction indicatrice d'Euler : Phi
Si n est un entier plus grand que 2, l'indicateur d'Euler de n, noté
désigne le nombre d'entiers compris entre 1 et n, et premiers avec n.Si n est premier,
= n-1. Si n est produit de 2 premiers, n = p×q, alors =(p-1)×(q-1). Un théorème d'Euler affirme que :
- Très dur à calculer si n est grand, d'où la recherche incessante de grands nombres permiers.
- Calculer est aussi dur que de factoriser n, ce qui assure la complexité des clés.
