Calculateur de racine primitive

Saisissez un module n pour trouver sa plus petite racine primitive.

Comment l'utiliser

  1. Saisissez vos valeurs dans les champs ci-dessus.
  2. Appuyez sur Calculer pour voir votre résultat instantanément.
  3. Utilisez le bouton Partager pour copier un lien vers votre résultat.

À propos de ce calculateur

Un nombre g est une racine primitive modulo n si ses puissances — g¹, g², g³, et ainsi de suite — parcourent tous les nombres premiers avec n avant de se répéter, c'est-à-dire que le plus petit exposant k pour lequel g^k ≡ 1 (mod n) est exactement φ(n), l'indicatrice d'Euler. Autrement dit, une seule racine primitive engendre à elle seule le groupe multiplicatif entier modulo n. Les racines primitives n'existent pas pour tous les modules : la théorie classique des nombres (remontant à Gauss) montre qu'elles n'existent que lorsque n vaut 1 (trivialement), 2, 4, une puissance d'un nombre premier impair, ou le double d'une puissance d'un nombre premier impair.

Les racines primitives sont un outil de travail en cryptographie, pas seulement une curiosité : l'échange de clés de Diffie–Hellman et le cryptosystème d'ElGamal reposent tous deux sur la difficulté du problème du logarithme discret dans un groupe engendré par une racine primitive, et les transformées de théorie des nombres utilisées pour la multiplication exacte et rapide de polynômes (pertinentes pour certains schémas cryptographiques et de correction d'erreurs modernes) dépendent aussi de la recherche de racines primitives adaptées d'un module.

Saisissez un module entier n de 2 à 100 000 et ce calculateur trouve sa plus petite racine primitive, ainsi que φ(n) et le nombre de racines primitives. Si aucune racine primitive n'existe pour ce n, il ne renvoie aucun résultat.

Cette page vous a-t-elle été utile ?

Vous pouvez choisir jusqu’à 3 réactions.

Commentaires

  • Soyez le premier à commenter.

Calculatrices populaires

Toutes les calculatrices