@tous,
je relie mon message du 2021-11-14,il et le trouve incorrect, veuillez m'excuser, cela oblige à compléter même si ce n'est pas encore du niveau de la plupart des membres.
Pour le RSA comme chacun sait on ne peut se contenter de choisir 1 < e < phi(n)=(p-1)(q-1) pour que e soit inversible. Il faut aussi tester que PGCD (e, phi(n))= 1 c'est équivalent à dire que e est premier avec phi(n). C'est cela qui garantit que l'inverse d existe. Les mises en œuvre du RSA le font (TLS, SSL) quoiqu'en pratique on fixe le "module" e=65537 et on cherche des n et p tels que e soit premier avec phi(n=pq) en faisant autant d'essais que possible (la clé publique (e,n) est publiée. Le nombre d' inversibles est par définition de l'indicatrice d'Euler phi(phi(n) puisqu'elle est définie comme le nombre d'entiers premiers avec phi(n). Par exemple p=17, q=3, phi (n=pq)= (17-1)x(3-1)= 32 . Et phi(32) se calcule par la formule d'Euler car n est ici une puissance d'un premier, soit phi(2^5)= 2^(5-1)= 16. Ainsi e=9 a un inverse d=25. Et dans le cas n premier évidemment pas définition d'un nombre premier tous les 1< e <n sont premiers avec n. C'est ce qui permet de constituer une table de codage-décodage de cette énigme puisque tous les codages des lettres [1,26] ont un inverse.
Donc le nombre moyen d'essais est phi(n) / phi(phi(n) = 2 dans l'exemple. J'espère que l'explication motive l'envie d'étudier l'arithmétique. Le calcul de phi(n) est un problème aussi compliqué que la factorisation de n=pq quand n est grand. Il est facile de montrer que la connaissance de phi(n) permet de calculer p et q.