4.4.1 Totient d'Euler

Il faut en tout premier lieu aborder les bases mathématiques qui fondent RSA. Parmi celles-ci se trouve la fonction de totient d'Euler, $\phi (n)$. Cette fonction donne le nombre d'entiers positifs plus petits ou égals à $n$ relativement premiers à $n$. Un nombre est relativement premier à un autre lorsqu'ils n'ont aucun diviseur commun excepté 1. Pour un nombre premier $p$, le résultat sera

$$\phi (p)=p-1$$

Par exemple, il existe 10 entiers positifs relativement premiers au nombre premier 11.

Supposons maintenant que $p$ et $q$ sont deux nombres premiers. Définissons $n$ comme étant le résultat de la multiplication de $p$ et $q$. Sans le démontrer, le totient de $n$ sera

$$\phi (n)=\phi (p)\cdot \phi (q)=(p-1)\cdot (q-1)$$

Prenons par exemple les deux nombres premiers 11 et 13. $n=11\times 13=143$. Le totient de $n$ sera $\phi (n)=10\times 12=120$.