Calculatrice Racines Primitives Mod P (Théorie Nombres)

Calculatrice racines primitives mod p premier: trouver plus petite RP, liste toutes, compter phi(phi(p)), ordre multiplicatif, test Lehmer théorie nombres.

Paramètres de calcul
Ce calculateur vous a-t-il été utile ?

Racines primitives: définition

Entier g est racine primitive (RP) mod n si ordre multiplicatif de g dans (Z/nZ)* est phi(n). Existence (Gauss): seulement pour n in {1, 2, 4, p^k, 2p^k} avec p premier impair.

Nombre de RP

Premier p impair: nombre RP = phi(p-1).

  • p = 7: 2 RP = {3, 5}.
  • p = 11: 4 RP = {2, 6, 7, 8}.
  • p = 17: 8 RP.

Test de Lehmer

  1. phi(p) = p - 1.
  2. Factoriser p - 1.
  3. Pour chaque premier q_i: g^((p-1)/q_i) mod p.
  4. Tous != 1: RP. Un = 1: pas RP.

Exemple p = 17

p - 1 = 16 = 2^4. q = 2. g = 3: 3^8 mod 17 = -1, est RP.

Ordre multiplicatif

Plus petit k > 0 avec g^k = 1 mod n. Divise phi(n). g est RP ssi ord = phi(n).

Existence autres structures

  • (Z/p^kZ)*: cyclique, RP existent.
  • (Z/8Z)*: non cyclique, pas de RP.
  • (Z/p1 p2 Z)*: non cyclique.
  • F_q^*: cyclique, generateurs RP.

Logarithme discret

g RP: tout a = g^k unique. log_g(a) (DLP) difficile. Base Diffie-Hellman, ElGamal.

Tables RP

  • p = 5: {2, 3}.
  • p = 7: {3, 5}.
  • p = 11: {2, 6, 7, 8}.
  • p = 13: {2, 6, 7, 11}.
  • p = 17: {3, 5, 6, 7, 10, 11, 12, 14}.

Applications

  • Diffie-Hellman.
  • ElGamal chiffrement/signature.
  • PRNG.
  • Tests primalite.
  • NTT FFT modulaire.
  • Reed-Solomon.
  • Lucas-Lehmer Mersenne.
  • Pohlig-Hellman DLP.

Conjecture Artin

Artin 1927: a non carre, premiers avec a RP densité positive 0.3739 constante Artin. Hooley 1967 conditionnel GRH.

Histoire

Euler (1744) ordre multiplicatif. Lagrange (1769). Gauss (1801) Disquisitiones, concept RP. Lehmer (1900-30) tests. Artin (1927) conjecture.

Modes calculatrice

Cinq: plus petite RP, liste (p <= 200), comptage phi(phi(p)), ordre mod n, verification Lehmer.

Generateurs de groupes cycliques et le logarithme discret

Une racine primitive modulo un premier p est precisement un generateur du groupe multiplicatif des residus non nuls : ses puissances successives parcourent chaque unite exactement une fois avant de revenir au depart. Cela rend le groupe cyclique, une structure d'une enorme commodite, car tout element peut s'ecrire comme la racine primitive elevee a un exposant. Cet exposant s'appelle le logarithme discret, ou indice, de l'element, et il transforme la multiplication modulo p en addition ordinaire des exposants, exactement comme les logarithmes ordinaires transforment la multiplication en addition de nombres reels.

L'obstacle, et la source de l'importance du concept en cryptographie, est que calculer un logarithme discret est repute difficile. Etant donnes une racine primitive g et une valeur a, trouver l'exposant k avec g eleve a k egal a a resiste a tous les algorithmes efficaces connus pour de grands premiers, tandis que l'operation inverse de l'exponentiation est rapide. Cette asymetrie est le moteur de l'echange de cles de Diffie-Hellman, ou deux parties elevent chacune une racine primitive partagee a un exposant secret et echangent les resultats, et des schemas de chiffrement et de signature d'ElGamal. Dans tous les cas la securite repose sur le fait qu'un groupe soit cyclique et qu'un generateur soit disponible, ce qu'une racine primitive fournit exactement.

Trouver les racines primitives : le test de Lehmer et leur structure

Verifier si un candidat g est une racine primitive n'exige pas de calculer son ordre complet en essayant chaque exposant. Le test de Lehmer offre un raccourci : factorisez p moins un en ses diviseurs premiers distincts, et verifiez que g eleve a la puissance (p moins un) divisee par q n'est pas congru a un pour chaque premier q. Si g survit a chacune de ces quelques verifications, son ordre ne peut etre un diviseur propre de p moins un, donc il doit etre une racine primitive. Cela reduit le travail d'une recherche sur p exposants a une poignee d'exponentiations modulaires, c'est pourquoi la calculatrice rapporte les resultats par premier du test.

Une fois une seule racine primitive connue, tout l'ensemble suit un schema net. Chaque autre racine primitive est ce generateur eleve a un exposant premier avec p moins un, il y en a donc exactement phi(p moins un), correspondant au compte que donne la calculatrice. Les racines primitives existent aussi au-dela des premiers : Gauss demontra qu'elles apparaissent precisement pour les modules un, deux, quatre, les puissances d'un premier impair et le double de telles puissances, et nulle part ailleurs. Pour ces modules on peut construire la meme table d'indices ou de logarithmes discrets, convertissant des multiplications difficiles en recherches faciles, une technique anterieure au calcul electronique qui remplissait jadis des tables imprimees dans les manuels de theorie des nombres.

Mis à jour en juillet 2026

Questions fréquentes

Qu'est-ce qu'une racine primitive ?

C'est un entier g dont l'ordre multiplicatif modulo n egale phi(n) : ses puissances g^0, g^1, ... engendrent tous les elements inversibles modulo n avant de se repeter. Autrement dit, g est un generateur du groupe multiplicatif (Z/nZ)*. Il rend le groupe cyclique et est un concept central de la theorie des nombres.

Pour quels modules existe-t-il des racines primitives ?

Gauss demontra qu'elles existent seulement pour n = 1, 2, 4, p^k et 2p^k, ou p est un premier impair et k >= 1. Pour tous les autres modules le groupe (Z/nZ)* n'est pas cyclique et n'a pas de generateur. Tout premier impair a donc toujours des racines primitives.

Combien y a-t-il de racines primitives modulo p ?

Pour un premier p le nombre de racines primitives est phi(p-1), soit phi(phi(p)). Par exemple pour p = 7, phi(6) = 2 et les racines primitives sont 3 et 5 ; pour p = 11, phi(10) = 4 et ce sont 2, 6, 7, 8. Une racine connue, les autres sont ses puissances d'exposant premier avec p-1.

Comment verifier que g est une racine primitive ?

Avec le test de Lehmer : on factorise p-1 en ses premiers distincts q et on verifie que g^((p-1)/q) n'est pas congru a 1 modulo p pour chaque q. S'il passe toutes les verifications, l'ordre de g ne peut etre un diviseur propre de p-1, donc g est une racine primitive. Quelques exponentiations modulaires suffisent.

Qu'est-ce que l'ordre multiplicatif ?

C'est le plus petit entier positif k tel que g^k soit congru a 1 modulo n. L'ordre divise toujours phi(n) (theoreme de Lagrange). Si l'ordre de g est exactement phi(n), alors g est une racine primitive ; sinon g n'engendre qu'un sous-groupe propre des elements inversibles.

Qu'est-ce que le logarithme discret ?

Une racine primitive g modulo p etant fixee, tout element a s'ecrit g^k : l'exposant k est le logarithme discret (ou indice) de a. Il transforme les multiplications en additions d'exposants. Le calculer pour de grands premiers est calculatoirement difficile, et c'est la base de la cryptographie a cle publique.

Comment sont-elles utilisees en cryptographie ?

La difficulte du logarithme discret securise l'echange de cles de Diffie-Hellman et les systemes de chiffrement et de signature d'ElGamal. Les deux parties elevent une racine primitive partagee a des exposants secrets : l'exponentiation est rapide, mais l'inverser pour trouver l'exposant est prohibitif. Il faut un groupe cyclique avec un generateur.

Qu'est-ce que la conjecture d'Artin ?

Artin (1927) conjectura que tout entier qui n'est ni un carre parfait ni -1 est racine primitive pour une infinite de premiers, avec une densite positive liee a la constante d'Artin (~0,3739). Par exemple 2 est racine primitive pour environ 37% des premiers. Hooley (1967) en donna une preuve conditionnee a l'hypothese de Riemann generalisee.

Commentaires (0)

Pas encore de commentaire. Soyez le premier !