La fonction indicatrice d’Euler, notée φ(n), compte les entiers positifs jusqu’à n qui n’ont aucun facteur commun avec n. Ce qui ressemble à un simple exercice de dénombrement est au fondement de l’arithmétique modulaire, de la généralisation du petit théorème de Fermat par Euler et de la génération des clés RSA. Ce calculateur détermine φ(n) par décomposition en facteurs premiers, présente le calcul étape par étape et, pour les petites valeurs de n, énumère directement tous les entiers premiers avec n.

Ce que φ(n) compte réellement

φ(n) compte les entiers positifs k de l’intervalle 1 ≤ k ≤ n tels que gcd(k, n) = 1, c’est-à-dire lorsque k et n sont premiers entre eux. Par convention, φ(1) = 1. Si p est premier, tous les entiers inférieurs à p sont premiers avec lui ; φ(p) = p − 1. L’onglet Liste des entiers premiers entre eux affiche directement ces valeurs lorsque n est assez petit (jusqu’à 2,000).

Comment la décomposition en facteurs premiers donne la formule

Pour calculer rapidement φ(n) lorsque n est grand, il est inutile de tester chaque entier : il suffit de décomposer n en facteurs premiers. L’indicatrice d’Euler est une fonction multiplicative : φ(mn) = φ(m)φ(n) si gcd(m, n) = 1. Avec φ(p^k) = p^k − p^(k-1) = p^k(1 − 1/p) pour toute puissance d’un nombre premier, on obtient la formule générale φ(n) = n·Π(1 − 1/p), le produit portant sur chaque facteur premier distinct p de n. Les exposants disparaissent entièrement de la formule. L’onglet Décomposition en facteurs premiers présente cette dérivation terme par terme pour la valeur de n saisie.

Pourquoi φ(n) est utile en cryptographie

Le chiffrement RSA génère une paire de clés publique et privée à partir de deux grands nombres premiers distincts p et q, avec n = pq comme module public. L’exposant privé est déterminé à l’aide de φ(n) = (p−1)(q−1) — la même formule que la ligne d’interprétation du calculateur met en évidence lorsque n est le produit de deux nombres premiers distincts. Dans les implémentations RSA réelles, p et q comportent des centaines de chiffres, mais le calcul de l’indicatrice est identique à celui présenté ici pour les petits exemples. Les outils Calculateur de décomposition en facteurs premiers et Calculateur de modulo permettent d’explorer d’autres notions de théorie des nombres liées à l’arithmétique modulaire et à la cryptographie.