Vérificateur de résidu quadratique
Indique si un nombre a une racine carrée modulo m et liste toutes les racines : 2 est un carré modulo 7, car 3 au carré vaut 9, qui laisse 2, et les racines sont 3 et 4. 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
- Module m
- 7
- A modulo
- 2
- Racines
- 3, 4
- Nombre de racines
- 2
Un entier a est un résidu quadratique modulo m lorsqu'un entier x satisfait x au carré congruent à a modulo m — autrement dit, a admet une racine carrée modulaire. Cette question oui-ou-non apparaît dans les devoirs de cryptographie, la théorie des nombres de concours et tout flux qui doit savoir si une congruence est un carré parfait avant d'investir un effort dans un solveur plus large. Cette capacité prend a et un module m (au moins deux), réduit a dans la plage canonique de zéro à m moins un, parcourt chaque racine dans cette plage et peut optionnellement renvoyer la liste complète des classes de résidus quadratiques modulo m.
Ce que signifie la résiduosité quadratique pour des modules généraux
En théorie élémentaire des nombres un résidu quadratique modulo un premier p signifie en général un entier a non divisible par p pour lequel la congruence x au carré égale a modulo p a une solution ; zéro est souvent traité à part comme le carré trivial. Pour un module composite m la même définition s'étend proprement : a est un résidu quadratique modulo m lorsqu'il existe au moins un entier x avec x au carré congruent à a modulo m, y compris le cas a congruent à zéro.
Les solutions suivent des motifs qui dépendent de la factorisation en puissances de premiers de m ; par exemple modulo un premier il y a zéro ou deux racines non nulles pour chaque classe de résidu non nulle qui est un carré, tandis que des modules composites peuvent admettre plus de racines.
Des outils classiques tels que les symboles de Legendre et Jacobi donnent des tests rapides lorsque m est un premier impair ou lorsque vous n'avez besoin que d'un caractère multiplicatif, mais ils n'énumèrent pas à eux seuls chaque racine pour un m arbitraire. Un balayage direct de x de zéro à m moins un évalue chaque classe de carré exactement une fois et répond donc à la fois à l'existence et à l'énumération pour tout module dans une borne de taille fixe.
Où les contrôles de carrés modulaires apparaissent dans le travail réel
Les programmeurs de concours ont souvent besoin d'un oracle rapide avant d'invoquer Tonelli–Shanks ou une combinaison CRT de racines en puissances de premiers : si le bit de résidu est faux, il est inutile de construire une racine carrée. Les étudiants en cryptographie vérifient des exemples de chiffres de type Rabin, des exercices de réciprocité quadratique et des variantes jouet de Diffie–Hellman qui mentionnent des symboles de résidu.
Les ingénieurs qui réconcilient des plannings périodiques ou des expériences de seaux de hachage demandent parfois si un pas est une classe de carré modulo une période composite. Si vous n'avez besoin que d'un oui-ou-non style symbole de Legendre pour un grand premier au-delà de la limite de balayage, factorisez ou réduisez d'abord ; dans le plafond cette page est la réponse constructive complète.
Cas d’usage
Contrôles de devoirs et de concours
Décidez si a est un carré modulo m et lisez chaque racine dans 0..m-1 pour des exercices de théorie des nombres sans construire un solveur CRT complet.
Préfiltre avant extraction de racines
Rejetez tôt les non-résidus dans un pipeline qui tenterait sinon des algorithmes de racine carrée modulaire sur des modules composites ou premiers.
Questions fréquentes
Qu'est-ce qu'un résidu quadratique modulo m ?
Un entier a est un résidu quadratique modulo m s'il existe un entier x tel que x² ≡ a (mod m). Cet outil rapporte ce fait et liste chaque tel x dans 0..m-1.
Pourquoi m doit-il être au moins 2 ?
Le module 0 est indéfini pour les congruences sur cette surface produit, et le module 1 effondre tout entier en une seule classe.
Quelle taille de module est prise en charge ?
m doit être un entier de 2 à 1,000,000 inclus. Le candidat a peut être tout entier sûr ; il est réduit modulo m avant le balayage.
Quel est le coût ?
L'outil navigateur est gratuit et s'exécute en local.
3 est-il un résidu quadratique modulo 7 ?
Non. En élevant au carré chaque reste modulo 7, on n'obtient que 0, 1, 2 ou 4 : aucun entier au carré ne laisse 3, et la liste des racines revient vide.
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/quadratic-residue \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"m":7}'const res = await fetch("https://api.kit.forhosting.com/numth/quadratic-residue", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"m": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/quadratic-residue",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"m": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/quadratic-residue", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"m":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"m":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/quadratic-residue", 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,
"m": 7
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.quadratic_residue",
"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.
Limites
min_m | 2 |
max_m | 1000000 |
max_abs_a | 9007199254740991 |
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 que signifie la résiduosité quadratique pour des modules généraux
Cette approche exhaustive est ce que ce point de terminaison implémente : arithmétique entière déterministe uniquement, pas d'arrondi en virgule flottante, et une forme JSON stable que vous pouvez affirmer dans des tests.
Contrat d'entrée, limites et champs de réponse
Envoyez les entiers a et m. Contrôles de cours typiques : deux est un résidu quadratique modulo sept car trois au carré vaut neuf qui est deux mod sept, et les racines sont trois et quatre ; trois n'est pas un résidu quadratique modulo sept. Les non-entiers, les champs requis vides et les modules au-dessus du plafond échouent la validation avec un message clair nommant le champ. Le module m doit être au moins deux et au plus un million ; les valeurs sous deux sont rejetées avec invalid_input et ne sont pas facturées, car l'arithmétique modulaire avec module zéro ou un n'est pas une surface produit prise en charge. Le candidat a peut être négatif ou plus grand que m ; il est réduit en a_mod dans l'intervalle semi-ouvert de zéro inclus à m exclus avant la recherche de carrés. Le booléen optionnel list_residues (alias list_all et all_residues) demande chaque valeur distincte de x au carré modulo m, triée croissante, avec residue_count. En cas de succès la charge utile inclut toujours a, m, a_mod, is_quadratic_residue, roots comme la liste complète des solutions de zéro à m moins un, et root_count. Lorsque list_residues est vrai pour m égal à sept vous obtenez les classes triées zéro, un, deux et quatre — l'image de l'application de mise au carré sur l'anneau des entiers modulo sept.
Où les contrôles de carrés modulaires apparaissent dans le travail réel
Les enseignants assignent des problèmes tels que lister tous les résidus quadratiques modulo vingt-et-un ou décider si cinq est un carré modulo treize et veulent une réponse JSON déterministe plutôt qu'un tableau manuscrit qui peut contenir des erreurs d'un. Comme la capacité est un moteur de parse pur il n'y a pas de dérive de modèle, pas de clé API externe et pas d'état stocké : la même paire produit toujours les mêmes racines et la même liste optionnelle de résidus. Le tarif API est la base publiée de $0.002 par élément réussi ; l'échec de validation ne consomme pas de solde.
Cas d'intégration
Énumérer les classes de résidus
Activez list_residues pour obtenir l'image triée de l'application de mise au carré modulo m pour tableaux, diapositives pédagogiques ou tests basés sur des propriétés.
Questions techniques
0 est-il considéré comme un résidu quadratique ?
Oui. 0² ≡ 0 (mod m), donc a_mod = 0 est toujours un résidu et inclut la racine 0 (et éventuellement d'autres pour m composite).