Racine n-ième modulaire
Trouvez toutes les racines k-ièmes d'un nombre modulo un premier : les racines carrées de 2 modulo 17 sont 6 et 11, dans l'ordre. S'il n'en existe aucune, vous obtenez une réponse claire plutôt qu'une liste vide. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- A
- 2
- K
- 2
- Puissance (W)
- 17
- A modulo
- 2
- Nombre de racines
- 2
- Racines
- 6, 11
- PGCD de k et φ
- 2
Une racine k-ième modulaire d’un entier a modulo un premier p est tout résidu x tel que x élevé à la puissance k est congruent à a modulo p. Les racines carrées modulo des premiers apparaissent dans les tutoriels Tonelli–Shanks, les racines cubiques et d’ordre supérieur en algèbre des corps finis, et les cours de cryptographie ont besoin d’un oracle fiable qui liste toutes les racines ou refuse clairement lorsqu’aucune n’existe. Ce calculateur accepte a, un exposant positif k et un module premier p, réduit a dans l’intervalle canonique de zéro à p moins un, et renvoie la liste ordonnée complète des solutions dans ce corps.
Ce que sont les racines k-ièmes modulaires et quand elles existent
Dans le groupe multiplicatif d’un corps premier tout résidu non nul a un ordre bien défini qui divise p moins un. Élever x à la k produit une application dont l’image est l’ensemble des résidus puissance k-ième. Pour une cible a non nulle la congruence x à la k congruent à a modulo p a des solutions si et seulement si a élevé à (p moins un) divisé par d est congruent à un, où d est le plus grand commun diviseur de k et p moins un.
Lorsque ce critère est vérifié il y a exactement d racines non nulles distinctes. Le résidu zéro est particulier : zéro à toute puissance positive est zéro, donc a congruent à zéro a pour seule racine zéro. Les modules composés sortent de ce cadre de groupe cyclique et sont rejetés afin que le solveur ne prétende jamais qu’un produit par le théorème des restes chinois est une réponse de corps premier.
Les étudiants rencontrent les racines carrées en vérifiant les symboles de Legendre à la main, les racines d’ordre supérieur en étudiant les classes cyclotomiques ou les logarithmes discrets, et les échecs d’existence lorsqu’un devoir demande la racine cubique d’un non-résidu cubique.
Comment ce calculateur trouve chaque racine
Appelez la capacité avec les champs entiers a, k et p. L’implémentation vérifie d’abord que k est un entier positif et que p est un premier dans la borne publiée via un test de Miller–Rabin déterministe. Après réduction de a modulo p, le cas du résidu zéro renvoie la seule racine zéro.
Pour a non nul elle calcule d égal au pgcd de k et p moins un et applique le test d’existence ci-dessus. Lorsque d vaut un il existe une racine unique obtenue en élevant a à l’inverse modulaire de k modulo p moins un, la voie rapide pour les exposants premiers entre eux.
Lorsque d est supérieur à un le solveur trouve une racine primitive g modulo p, récupère le logarithme discret de a en base g par baby-step giant-step, et résout la congruence linéaire k fois y congruent à ce logarithme modulo p moins un. Chaque racine renvoyée est vérifiée par exponentiation modulaire avant l’émission de la réponse.
Les valeurs absolues de a et k sont bornées par un billion et le premier p près d’un milliard pour que la mémoire baby-step giant-step reste pratique ; si d dépassait dix mille racines la requête est refusée plutôt que d’inonder le client.
Cas d’usage
Cryptographie et laboratoires de corps finis
Enseignants et étudiants peuvent lister chaque racine carrée ou d’ordre supérieur modulo un petit premier, vérifier les critères d’existence et inspecter gcd(k, p−1) lorsqu’un résidu d’exemple n’a pas de racine k-ième.
Programmation compétitive et algèbre modulaire
Les programmeurs compétitifs peuvent vérifier les solutions de x^k ≡ a (mod p) contre un oracle déterministe au lieu d’un Tonelli–Shanks artisanal ou de boucles de force brute.
Questions fréquentes
Que se passe-t-il si p n’est pas premier ?
Ce calculateur exige un module premier pour que le groupe multiplicatif soit cyclique et le critère d’existence exact. Une validation échouée n’est pas facturée.
Et s’il n’existe pas de racine k-ième ?
Une liste vide de succès n’est jamais renvoyée en cas de non-existence.
Quels algorithmes utilise le calculateur de racine n-ième modulaire ?
Miller–Rabin pour la primalité, exposants via inverse modulaire lorsque gcd(k,p−1)=1 ; sinon racine primitive, logarithme discret baby-step giant-step et résolution de congruences linéaires. Tous les chemins sont déterministes.
Quelles sont les racines carrées de 2 modulo 17 ?
Ce sont 6 et 11. En élevant l'une ou l'autre au carré puis en divisant par 17, il reste 2. Le calculateur les affiche par ordre croissant, avec le nombre de racines.
Combien de racines peut-il y avoir ?
Quand des racines existent, il y en a exactement autant que le plus grand diviseur commun de k et de p − 1 : deux racines carrées de 2 modulo 17. Zéro a pour seule racine zéro, et plus de dix mille racines sont refusées.
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
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/modular-nth-root \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"k":2,"p":17}'const res = await fetch("https://api.kit.forhosting.com/numth/modular-nth-root", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"k": 2,
"p": 17
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/modular-nth-root",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"k": 2,
"p": 17
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/modular-nth-root", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"k":2,"p":17}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"k":2,"p":17}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/modular-nth-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
{
"a": 2,
"k": 2,
"p": 17
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.modular_nth_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
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
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
Lorsque p est composé la requête échoue avec invalid_input ; lorsque le critère d’existence a élevé à (p moins un) sur le pgcd de k et p moins un n’est pas un modulo p, la requête échoue aussi au lieu de renvoyer une liste vide de succès. Le même module pur et déterministe alimente l’outil gratuit du navigateur et le chemin API prépayé, de sorte que les démos de cours et les correcteurs automatiques ne divergent jamais sur une racine.
Ce que sont les racines k-ièmes modulaires et quand elles existent
Renvoyer un invalid_input ferme en cas de non-existence rejoint le langage des textes de théorie des nombres qui disent sans solution, plutôt qu’une liste vide qu’un système de facturation pourrait traiter comme un succès.
Comment ce calculateur trouve chaque racine
Chaque solution y donne une racine g à la y, et les racines distinctes sont triées par ordre croissant pour un contrat d’API stable.
Usage pratique, limites, tarification et livraison
Utilisez l’outil navigateur lorsque vous voulez chaque racine carrée ou d’ordre supérieur en lisant une note de crypto, en vérifiant une sortie de programmation compétitive ou en notant un devoir de corps finis. Les entrées acceptées sont des entiers a de valeur absolue au plus un billion, des exposants k de un à un billion, et des premiers p de deux jusqu’à environ un milliard, sous le plafond de sécurité du nombre de racines. Utilisez l’API lorsqu’un script, un plugin LMS ou un carnet de recherche a besoin de nombreuses requêtes de racines modulaires sans intégrer Tonelli–Shanks ni un logarithme discret. Chaque requête réussie est un élément facturable à $0.002 ; les échecs de validation, les modules composés et la non-existence prouvée ne consomment pas de solde. La réponse renvoie a, k, p, le a_mod réduit, root_count, le tableau roots croissant, gcd_k_phi égal à d, une chaîne d’équation d’affichage et une balise method nommant le chemin algorithmique. Branchez l’endpoint sur des sandboxes de cryptographie, des aides de programmation compétitive et des démos de théorie algébrique des nombres qui préfèrent déjà l’arithmétique modulaire exacte aux approximations flottantes. Comme l’unité est un seul élément et le moteur un parse pur, la latence reste faible et le canal web gratuit reflète l’API payante sans un second chemin de code qui pourrait diverger.
Cas d'intégration
Correcteurs de devoirs et carnets de recherche
Correcteurs automatiques et scripts peuvent confirmer les ensembles de racines, rejeter les modules composés via invalid_input et garder chaque produit intermédiaire dans les bornes documentées.
Questions techniques
Comment calculer des racines k-ièmes modulaires avec cette API ?
Envoyez un JSON avec les champs entiers a, k (≥ 1) et le premier p vers numth.modular_nth_root. En cas de succès la réponse renvoie roots en tableau croissant, root_count, a_mod et gcd_k_phi.
Le calculateur de racine n-ième modulaire est-il gratuit ?
L’outil navigateur s’exécute gratuitement sur votre appareil. Les appels API utilisent le solde KIT prépayé à $0.002 par élément réussi ; entrée invalide et erreurs de non-existence ne sont pas facturées.