Sept a deux racines primitives, huit n'en a aucune
Publié le 27/10/2026 · 3 min de lecture · Calculateurs du quotidien
Lena Hoffmann — Rédactrice Sciences & Éducation chez OneKitly
Mathématiques · Physique
Vérifié à partir de 2 sources
Une racine primitive modulo n est un nombre dont les puissances parcourent toute valeur première avec n avant de revenir à un. Modulo 7, le nombre 3 y parvient : 3, 2, 6, 4, 5, 1 — les six résidus, dans un ordre brouillé, puis retour au départ. Cinq fait de même, et rien d'autre : il y en a donc deux. Modulo 11, il y a quatre générateurs ; modulo 8, aucun : les puissances d'aucun nombre n'atteignent tous les candidats, car la structure s'y scinde en deux moitiés indépendantes au lieu de former un seul cycle. Le compte, quand des générateurs existent, vaut φ(φ(n)) — pour 7, φ(6) = 2, et pour 11, φ(10) = 4.
Modulo 7, les nombres 3 et 5 engendrent chacun toute valeur non nulle par multiplications répétées. Modulo 8, rien n'y parvient ; modulo 11, il y a quatre générateurs.
Les modules qui marchent forment une courte liste
Des générateurs n'existent que pour 1, 2, 4, une puissance quelconque d'un premier impair, et le double d'une telle puissance — rien d'autre. Cela exclut d'emblée 8, 12 et 15, et explique que 9 marche là où 8 échoue, malgré leur petite taille commune. La raison est que la structure multiplicative modulo tout le reste se décompose en morceaux indépendants, et qu'aucun élément unique ne peut engendrer un produit de cycles indépendants. C'est un cas rare où la classification est complète, brève et vérifiable contre le calculateur en une minute — bon exemple d'un théorème plus utile qu'une recherche.
À quoi sert un générateur
En posséder un transforme la multiplication en addition. Toute valeur non nulle s'écrit comme le générateur élevé à une certaine puissance : multiplier deux valeurs revient donc à additionner leurs exposants — le tour que jouent les logarithmes avec les nombres ordinaires, en contexte fini. C'est cette correspondance qu'exploitent les protocoles d'échange de clés : élever un générateur commun à un exposant secret est facile, retrouver l'exposant à partir du résultat paraît difficile, si bien que deux parties peuvent s'accorder sur une valeur qu'aucune n'a transmise. Toute la construction dépend du groupe formant un seul cycle, ce que garantit précisément une racine primitive.
| Module | Générateurs | Combien |
|---|---|---|
| 7 | 3, 5 | 2 |
| 9 | 2, 5 | 2 |
| 11 | 2, 6, 7, 8 | 4 |
| 8, 12, 15 | aucun | 0 |
Questions fréquentes
- Existe-t-il une formule pour la plus petite racine ?
- Aucune n'est connue, et la recherche se fait par essais. Les candidats sont testés dans l'ordre et chaque test est bon marché — il suffit de vérifier que le candidat élevé à l'indicatrice divisée par chaque facteur premier ne vaut pas un — mais rien ne permet de prédire quel candidat réussira. En pratique, la plus petite racine est presque toujours un très petit nombre, deux, trois ou cinq, et les heuristiques annoncent une croissance extrêmement lente avec le module ; cette attente est bien étayée et non démontrée, forme récurrente des résultats dans ce coin du domaine.
- Pourquoi le nombre de générateurs dépend-il de φ(φ(n)) ?
- Parce qu'une fois un générateur trouvé, tout autre est l'une de ses puissances, et une puissance engendre tout le cycle exactement quand son exposant est premier avec la longueur du cycle. Le cycle a pour longueur φ(n) : le nombre d'exposants utilisables vaut donc φ(φ(n)), par l'argument de comptage qui définit l'indicatrice au départ. Modulo 7, le cycle a longueur 6, les exposants premiers avec 6 sont 1 et 5, et les deux générateurs 3 et 5 sont le premier générateur élevé à ces puissances. La double application de la même fonction n'est pas fortuite — c'est la même question posée sur les exposants au lieu des valeurs.
Articles qui pourraient t'intéresser
Tous les guides →Outils similaires
Sources
Tu as repéré une erreur dans cet article ?