ForHosting KIT · Mathématiques

Calculateur de racine primitive

Trouve la plus petite racine primitive d'un premier : modulo 7, c'est 3, dont les puissances parcourent les six restes non nuls, alors que celles de 2 se répètent après trois. Vous voyez aussi p − 1 décomposé en puissances de premiers. Gratuit dans votre navigateur.

Gratuit
Fonctionne dans votre navigateur
Sans inscription
Vos données restent sur votre appareil

Lancer gratuitement Voir l’API

Utilisez-le depuis WebAPIE-mailTelegramApp bientôt

Exemple résolu

Si vous saisissez

Puissance (W): 7

Vous obtenez

Racine primitive: 3
Ordre: 6
Chiffres maximum: 15

Une racine primitive modulo un nombre premier p est un générateur du groupe multiplicatif des résidus non nuls modulo p. En termes simples, un certain entier g entre 1 et p moins un a la propriété que ses puissances successives g, g au carré, g au cube, et ainsi de suite, finissent par atteindre chaque classe de résidu première avec p avant de se répéter. Ce g est un générateur de (Z/pZ)*, et le plus petit g positif de ce type est la réponse classique de théorie des nombres que les élèves, les cryptographes, et les résolveurs de concours recherchent. Ce calculateur prend un module premier p, vérifie que p est premier, factorise p moins un, et renvoie la plus petite racine primitive avec l'ordre du groupe et la factorisation en puissances premières de p moins un. Le parcours est entièrement déterministe : Miller-Rabin avec des ensembles de témoins fixes, factorisation par essai, et exponentiation modulaire sans réseau, sans aléatoire, et sans dépendance à la date.

Ce qu'est une racine primitive et ce que contient la réponse

Pour un module premier p, l'ensemble des résidus 1, 2, …, p moins un forme un groupe multiplicatif cyclique d'ordre p moins un. Un entier g est une racine primitive modulo p lorsque l'ordre de g dans ce groupe est exactement p moins un : les puissances g à la k pour k de 0 à p moins deux sont toutes distinctes modulo p et épuisent chaque résidu non nul.

Tout entier n'est pas un générateur ; par exemple modulo 7, les puissances de 2 cyclent seulement à travers trois valeurs avant de se répéter, donc 2 n'est pas une racine primitive, tandis que 3 génère les six unités et est la plus petite. Il n'y a pas de devinette probabiliste présentée comme une racine et pas de repli silencieux pour les modules composés, car une racine primitive au sens classique est définie pour les nombres premiers (et quelques familles composées spéciales que cette page ne couvre pas).

Si vous avez besoin des facteurs d'un entier arbitraire plutôt que d'un générateur mod p, utilisez plutôt une capacité de factorisation ; cette page répond uniquement à la question du plus petit générateur mod nombre premier.

Comment le nombre premier est vérifié et comment la plus petite racine est trouvée

Les signes plus initiaux optionnels sont autorisés ; les espaces internes, les préfixes hexadécimaux, et la notation exponentielle sont rejetés avec un message clair afin qu'une mauvaise cellule ne devienne pas un mauvais générateur. Après l'analyse, le moteur exécute un test de primalité de Miller-Rabin déterministe avec des ensembles de témoins prouvés suffisants pour tout entier d'au plus quinze chiffres décimaux.

Lorsque p est premier, le moteur factorise p moins un par division d'essai en roue, collecte les facteurs premiers distincts q de cet ordre, et cherche g égale 2, 3, 4, … pour le premier candidat tel que g élevé à (p moins un) divisé par q ne soit pas congru à 1 modulo p pour chaque q de ce type. Ce critère classique est nécessaire et suffisant pour que g ait l'ordre p moins un.

Le cas particulier p égale 2 renvoie une racine primitive de 1, l'unique unité de ce groupe.

Où les plus petites racines primitives s'inscrivent dans l'étude, la cryptographie et le code

Les élèves rencontrent les racines primitives en apprenant les groupes cycliques, les logarithmes discrets, et la structure des corps finis d'ordre premier. Les fiches d'exercices demandent souvent le plus petit générateur modulo un petit nombre premier ; cette page renvoie cette réponse avec la factorisation à l'appui de p moins un afin que vous puissiez vérifier les tests d'ordre à la main.

Les problèmes de concours et les énoncés de kata de programmation exigent fréquemment la plus petite racine primitive comme sous-routine pour construire des polynômes primitifs, indexer des tables de logarithme discret, ou amorcer des démonstrations de théorie des nombres.

En cryptographie appliquée, Diffie-Hellman et les constructions apparentées ont besoin d'un générateur d'un sous-groupe d'ordre premier large ; bien que les systèmes de production utilisent des nombres premiers sûrs soigneusement choisis et des générateurs standardisés, un calculateur transparent pour des nombres premiers ordinaires reste utile lorsque vous validez des paramètres à l'échelle des devoirs, écrivez des tests unitaires pour des utilitaires d'ordre modulaire, ou expliquez pourquoi g égale 2 fonctionne pour certains nombres premiers et pas pour d'autres.

Les enseignants peuvent pré-générer des corrigés sans faire confiance à des widgets web opaques.

Cas d’usage

Devoirs et préparation aux concours

Recherchez la plus petite racine primitive modulo un nombre premier pour des exercices de manuel, des exercices de logarithme discret, et des concours de programmation qui exigent le plus petit générateur.

Tests déterministes de paramètres cryptographiques

Générez des générateurs reproductibles pour des tests unitaires d'ordre modulaire, des démonstrations de Diffie-Hellman sur des nombres premiers jouets, et des assertions de CI sans intégrer de tables statiques.

Enseigner les groupes cycliques

Montrez que les puissances de la racine renvoyée épuisent (Z/pZ)* et contrastez avec des non-générateurs en utilisant la factorisation de p−1 dans la réponse.

Questions fréquentes

Combien coûte le calculateur de racine primitive ?

Il est gratuit dans votre navigateur sur cette page.

Que se passe-t-il si p n'est pas premier ?

Les racines primitives classiques en ce sens sont définies pour des modules premiers ; un n composé est hors périmètre.

L'algorithme est-il aléatoire ?

Non. La primalité utilise des ensembles de témoins Miller-Rabin déterministes, la factorisation est par division d'essai, et les puissances modulaires sont exactes. Le même p produit toujours la même racine.

Quel est le plus grand nombre premier que je peux envoyer ?

p peut avoir au plus 15 chiffres décimaux. Des valeurs plus grandes échouent avec un message clair indiquant que la limite de chiffres a été dépassée.

Pourquoi les facteurs premiers de p − 1 sont-ils affichés ?

Ce sont eux que le contrôle utilise. Un candidat g est racine primitive lorsque g puissance (p − 1)/q ne vaut pas 1 modulo p pour chaque premier q divisant p − 1 : vous pouvez ainsi refaire le test.

Outils associés

Pour les développeurs — accès API

Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.

Endpoint

POSThttps://api.kit.forhosting.com/numth/primitive-root

Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.

Appeler depuis votre stack

curl -X POST https://api.kit.forhosting.com/numth/primitive-root \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"p":"7"}'

const res = await fetch("https://api.kit.forhosting.com/numth/primitive-root", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "p": "7"
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/primitive-root",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "p": "7"
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/primitive-root", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"p":"7"}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"p":"7"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/primitive-root", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

Exemple de requête

{
  "p": "7"
}

Exemple de réponse

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.primitive_root",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.

Tarifs

par requête$0.002

Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.

Limites

max_digits 15

Erreurs

HTTP	Code	Signification
`401`	`unauthorized`	Clé API absente ou invalide : vérifiez l’en-tête Authorization.
`402`	`insufficient_balance`	Solde insuffisant : rechargez votre compte pour lancer cette tâche.
`404`	`unknown_type`	Type de tâche inconnu : vérifiez le champ type de votre requête.
`429`	`rate_limited`	Trop de requêtes : ralentissez la cadence, puis réessayez.

Notes techniques

Ce qu'est une racine primitive et ce que contient la réponse

Cet outil renvoie le nombre premier p comme chaîne décimale, la plus petite racine primitive, l'ordre du groupe p moins un, un indicateur booléen is_prime qui est toujours true en cas de succès, les facteurs de puissance première ordonnés de p moins un utilisés dans les tests d'ordre, et la limite max_digits publiée afin que les clients puissent valider avant un lot. Les modes d'échec sont explicites : un p manquant, des non-entiers, des fractions, la notation scientifique, des valeurs inférieures à deux, des valeurs de plus de quinze chiffres, et un p composé déclenchent tous invalid_input.

Comment le nombre premier est vérifié et comment la plus petite racine est trouvée

Le champ préféré est p comme entier JSON ou chaîne décimale ; les alias prime, modulus, et n sont acceptés afin que formulaires, chaînes de requête, et tableurs puissent réutiliser le même contrat. Si le test échoue, la réponse est invalid_input nommant que p n'est pas premier.

Où les plus petites racines primitives s'inscrivent dans l'étude, la cryptographie et le code

Sur cette page, le travail s'exécute entièrement dans votre navigateur ; via l'API, chaque recherche réussie coûte $0.002, la validation échouée n'est pas facturée, et rien n'est stocké après le retour de la réponse. Cette séparation — exploration interactive gratuite et API payante identique — correspond au reste du catalogue KIT de niveau A, et vous permet de passer d'une démonstration en classe à un pipeline automatisé sans changer le résultat mathématique.

Questions techniques

Le résultat est-il toujours la plus petite racine primitive ?

Oui. Le moteur cherche g = 2, 3, 4, … et renvoie le premier générateur, donc la racine est minimale parmi les résidus positifs.

Consulter la documentation complète du KIT →

Lancer gratuitement

Exemple résolu

Ce qu'est une racine primitive et ce que contient la réponse

Comment le nombre premier est vérifié et comment la plus petite racine est trouvée

Où les plus petites racines primitives s'inscrivent dans l'étude, la cryptographie et le code

Cas d’usage

Devoirs et préparation aux concours

Tests déterministes de paramètres cryptographiques

Enseigner les groupes cycliques

Questions fréquentes

Outils associés

Pour les développeurs — accès API

Endpoint

Appeler depuis votre stack

Exemple de requête

Exemple de réponse

Tarifs

Limites

Erreurs

Notes techniques

Ce qu'est une racine primitive et ce que contient la réponse

Comment le nombre premier est vérifié et comment la plus petite racine est trouvée

Où les plus petites racines primitives s'inscrivent dans l'étude, la cryptographie et le code

Questions techniques

merci