Calculatrice de la fonction indicatrice d'Euler

Bienvenue sur la Calculatrice de la fonction indicatrice d'Euler, un outil complet de théorie des nombres qui calcule φ(n) (la fonction phi d'Euler) avec une décomposition en facteurs premiers étape par étape, une visualisation interactive de la grille des nombres premiers entre eux et une analyse approfondie. Que vous étudiiez l'algèbre abstraite, que vous vous prépariez à des concours de mathématiques, que vous travailliez sur la cryptographie RSA ou que vous exploriez l'arithmétique modulaire, cette calculatrice offre des calculs de qualité professionnelle avec un riche contenu éducatif.

Qu'est-ce que la fonction indicatrice d'Euler ?

La fonction indicatrice d'Euler φ(n), également connue sous le nom de fonction phi d'Euler, compte le nombre d'entiers positifs de 1 à n qui sont premiers entre eux (copremiers) avec n. Deux nombres sont premiers entre eux lorsque leur plus grand commun diviseur (PGCD) est égal à 1.

Par exemple, φ(12) = 4 car exactement quatre nombres — 1, 5, 7 et 11 — sont premiers avec 12 parmi les entiers de 1 à 12.

La formule du produit

La manière la plus efficace de calculer φ(n) utilise la décomposition en facteurs premiers de n. Si \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\), alors :

Cela signifie que nous multiplions n par \((1 - 1/p)\) pour chaque facteur premier distinct p de n. Les exposants n'ont pas d'importance — seuls les nombres premiers distincts comptent.

Propriétés clés

Théorème d'Euler

Le théorème d'Euler est le résultat clé qui rend la fonction indicatrice cruciale en cryptographie :

Ceci généralise le petit théorème de Fermat (qui est le cas particulier où n est premier). Il constitue le fondement mathématique du chiffrement RSA.

Comment utiliser cette calculatrice

1. Entrez un entier positif : Tapez n'importe quelle valeur de 1 à 1 000 000 dans le champ de saisie.
2. Utilisez les exemples rapides : Cliquez sur les boutons d'exemple pour essayer des valeurs classiques comme des nombres premiers, des nombres composés ou des nombres semi-premiers de type RSA.
3. Consultez vos résultats : La calculatrice affiche φ(n), la décomposition en facteurs premiers, le ratio de coprimalité et les propriétés détectées.
4. Explorez la grille : Pour n ≤ 400, voyez quels nombres sont premiers avec n dans une grille visuelle animée.
5. Étudiez le graphique de tendance : Voyez comment φ(k) varie pour k = 1 à min(n, 100).

Lien avec le chiffrement RSA

Dans la cryptographie RSA, la fonction indicatrice d'Euler joue un rôle central :

1. Choisissez deux grands nombres premiers p et q. Calculez n = p × q.
2. Calculez φ(n) = (p−1)(q−1).
3. Choisissez un exposant public e avec pgcd(e, φ(n)) = 1.
4. Calculez l'exposant privé d tel que e × d ≡ 1 (mod φ(n)).

La sécurité de RSA repose sur la difficulté de calculer φ(n) sans connaître la factorisation de n. Si un attaquant pouvait calculer efficacement φ(n), il pourrait casser le chiffrement RSA.

Valeurs courantes de φ(n)

Foire aux questions

Qu'est-ce que la fonction indicatrice d'Euler ?

La fonction indicatrice d'Euler φ(n), également appelée fonction phi d'Euler, compte le nombre d'entiers positifs de 1 à n qui sont premiers avec n (coprimes). Deux nombres sont dits premiers entre eux lorsque leur plus grand commun diviseur (PGCD) est 1. Par exemple, φ(12) = 4 car seuls 1, 5, 7 et 11 sont premiers avec 12.

Comment calculer la fonction indicatrice d'Euler ?

Pour calculer φ(n) : (1) Trouvez la décomposition en facteurs premiers de n. (2) Appliquez la formule du produit : φ(n) = n × ∏(1 − 1/p) pour chaque facteur premier distinct p de n. Par exemple, φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Pour un nombre premier p, φ(p) = p−1. Pour une puissance de nombre premier p^k, φ(p^k) = p^k − p^(k−1).

Pourquoi la fonction indicatrice d'Euler est-elle importante dans le cryptage RSA ?

Dans le cryptage RSA, le module n = p × q est le produit de deux grands nombres premiers. L'indicatrice φ(n) = (p−1)(q−1) est utilisée pour calculer la clé privée : l'exposant de déchiffrement d doit satisfaire e × d ≡ 1 (mod φ(n)), où e est l'exposant de chiffrement public. Sans connaître φ(n) — ce qui nécessite de factoriser n — le calcul de d est informatiquement infaisable.

Qu'est-ce que le théorème d'Euler et quel est son rapport avec la fonction indicatrice ?

Le théorème d'Euler stipule que si a et n sont premiers entre eux, alors a^φ(n) ≡ 1 (mod n). C'est une généralisation du petit théorème de Fermat (qui s'applique quand n est premier). Il est fondamental en arithmétique modulaire et en cryptographie, fournissant la base mathématique du chiffrement RSA et de l'exponentiation modulaire efficace.

Quelles sont les propriétés clés de la fonction indicatrice d'Euler ?

Les propriétés clés incluent : (1) φ(1) = 1. (2) Pour un nombre premier p : φ(p) = p−1. (3) Pour une puissance de nombre premier p^k : φ(p^k) = p^(k−1)(p−1). (4) Propriété multiplicative : si pgcd(m,n) = 1, alors φ(m×n) = φ(m)×φ(n). (5) Somme sur les diviseurs : Σ φ(d) = n pour tous les diviseurs d de n. (6) φ(n) est toujours pair pour n > 2.

Que signifie le fait que deux nombres soient premiers entre eux ?

Deux entiers a et b sont premiers entre eux (également appelés copremiers) si leur plus grand commun diviseur est 1, ce qui signifie qu'ils ne partagent aucun facteur premier commun. Par exemple, 8 et 15 sont premiers entre eux car pgcd(8,15) = 1, même si aucun des deux n'est premier. La fonction indicatrice φ(n) compte exactement combien d'entiers de 1 à n sont premiers avec n.

Ressources supplémentaires

• Théorème d'Euler - Wikipédia