Cryptographie : Signature numérique et Chiffrement

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 :

Exemple : Phi(8) = 3 car 3,5,7 premiers avec 8

• 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.

C'est ce théorème qui fait fonctionner l'algorithme RSA : si e est l'exposant public et d l'exposant privé, ils sont reliés par ed=k(p-1)×(q-1)+1. Pour tout message M :