Calculatrice de racine primitive

Bienvenue sur la Calculatrice de racine primitive, un puissant outil en ligne gratuit qui trouve toutes les racines primitives modulo n'importe quel entier positif n. Cette calculatrice fournit une vérification étape par étape, des tables de puissance et une visualisation animée du groupe cyclique pour vous aider à comprendre comment les racines primitives génèrent des groupes multiplicatifs. Que vous étudiiez la théorie des nombres, que vous vous prépariez à des examens de cryptographie ou que vous travailliez avec l'arithmétique modulaire en programmation compétitive, cet outil fournit des résultats instantanés et précis avec des informations pédagogiques.

Qu'est-ce qu'une racine primitive ?

Une racine primitive modulo n est un entier g dont les puissances génèrent tous les entiers qui sont premiers avec n. Formellement, g est une racine primitive mod n si l'ordre multiplicatif de g modulo n est égal à l'indicateur d'Euler \(\varphi(n)\). Cela signifie que l'ensemble

contient exactement tous les \(\varphi(n)\) entiers de 1 à n-1 qui sont premiers avec n. Une racine primitive est essentiellement un générateur du groupe cyclique \((\mathbb{Z}/n\mathbb{Z})^*\).

Exemple rapide

Considérons n = 7. Puisque 7 est premier, \(\varphi(7) = 6\). Vérifions si g = 3 est une racine primitive :

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

Les puissances produisent {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}, qui sont tous les entiers premiers avec 7. Ainsi, 3 est une racine primitive modulo 7.

Quand les racines primitives existent-elles ?

Les racines primitives modulo n existent si et seulement si n est sous l'une de ces formes :

• n = 1, 2 ou 4
• n = p^k où p est un nombre premier impair et k ≥ 1
• n = 2p^k où p est un nombre premier impair et k ≥ 1

Par exemple, des racines primitives existent pour 7, 9, 11, 13, 14, 18, 23, 25, 27, 46, mais pas pour 8, 12, 15, 16, 20, 21, 24.

Comment trouver les racines primitives

1. Entrez le modulo : Saisissez un nombre entier positif n (de 2 à 100 000) dans le champ de saisie.
2. Calculer : Cliquez sur "Trouver des racines primitives" ou appuyez sur Entrée.
3. Voir toutes les racines : Consultez la liste complète des racines primitives, ainsi que l'indicateur d'Euler et les statistiques.
4. Étudier la table de puissance : Examinez comment la plus petite racine primitive génère tous les résidus premiers entre eux.
5. Visualiser le groupe cyclique : Pour les petits modulos, visualisez la roue animée montrant la structure cyclique.

Combien de racines primitives n possède-t-il ?

Si des racines primitives existent modulo n, le nombre est égal à :

Par exemple, pour n = 13 : \(\varphi(13) = 12\) et \(\varphi(12) = 4\), il y a donc exactement 4 racines primitives modulo 13 (qui sont 2, 6, 7, 11).

L'algorithme de vérification

Pour vérifier efficacement si g est une racine primitive modulo n :

1. Calculez \(\varphi(n)\) à l'aide de la décomposition en facteurs premiers de n
2. Trouvez tous les facteurs premiers distincts \(p_1, p_2, \ldots, p_k\) de \(\varphi(n)\)
3. Pour chaque facteur premier \(p_i\), vérifiez : \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. Si TOUTES les vérifications réussissent, alors g est une racine primitive

Cette méthode est beaucoup plus rapide que de calculer toutes les puissances de g, car nous n'avons qu'à tester \(k\) exponentiations au lieu de \(\varphi(n)\).

Les racines primitives en cryptographie

Échange de clés Diffie-Hellman

Le protocole Diffie-Hellman utilise un grand nombre premier p et une racine primitive g modulo p. Alice choisit un secret a, envoie \(g^a \bmod p\). Bob choisit un secret b, envoie \(g^b \bmod p\). Tous deux calculent le secret partagé \(g^{ab} \bmod p\). La sécurité repose sur le fait que le problème du logarithme discret est informatiquement difficile.

Cryptage ElGamal

ElGamal utilise également une racine primitive comme générateur. La clé publique est \((p, g, g^x \bmod p)\) où x est privé. Le fait que g génère tous les éléments garantit que chaque message peut être crypté.

Signatures numériques

Le DSA (Digital Signature Algorithm) et les schémas associés utilisent des racines primitives dans des sous-groupes de \((\mathbb{Z}/p\mathbb{Z})^*\) pour créer et vérifier des signatures numériques.

Table de référence : Plus petites racines primitives

Foire aux questions

Qu'est-ce qu'une racine primitive modulo n ?

Une racine primitive modulo n est un entier g tel que les puissances \(g^1, g^2, \ldots, g^{\varphi(n)}\) produisent tous les entiers premiers avec n lorsqu'ils sont pris modulo n. En d'autres termes, g génère l'ensemble du groupe multiplicatif \((\mathbb{Z}/n\mathbb{Z})^*\). L'ordre multiplicatif de g modulo n est égal à l'indicateur d'Euler \(\varphi(n)\).

Pour quelles valeurs de n les racines primitives existent-elles ?

Les racines primitives existent modulo n si et seulement si n est 1, 2, 4, p^k ou 2p^k, où p est un nombre premier impair et k ≥ 1. Par exemple, des racines primitives existent pour n = 7 (premier), n = 9 (3²), n = 14 (2×7), mais PAS pour n = 8, 12, 15 ou 16.

Combien de racines primitives n possède-t-il ?

Si des racines primitives existent modulo n, le nombre de racines primitives est égal à \(\varphi(\varphi(n))\), où \(\varphi\) est la fonction indicateur d'Euler. Par exemple, pour n = 13 (premier), \(\varphi(13) = 12\) et \(\varphi(12) = 4\), il y a donc exactement 4 racines primitives modulo 13.

Pourquoi les racines primitives sont-elles importantes en cryptographie ?

Les racines primitives sont fondamentales pour le protocole d'échange de clés Diffie-Hellman et le système de cryptage ElGamal. Dans ces protocoles cryptographiques, une racine primitive g modulo un grand nombre premier p est utilisée comme générateur. La sécurité repose sur la difficulté du problème du logarithme discret : étant donné \(g^x \bmod p\), il est informatiquement difficile de trouver x.

Comment vérifier que g est une racine primitive modulo n ?

Pour vérifier que g est une racine primitive mod n : (1) Calculez \(\varphi(n)\). (2) Trouvez tous les facteurs premiers \(p_1, p_2, \ldots, p_k\) de \(\varphi(n)\). (3) Vérifiez que \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) pour chaque facteur premier \(p_i\). Si toutes les vérifications réussissent, g est une racine primitive. C'est beaucoup plus rapide que de calculer toutes les puissances de g.

Outils connexes