ForHosting KIT · Mathématiques

Non-résidus quadratiques mod p

Liste chaque reste qui n'est jamais un carré modulo un premier impair : modulo 7, les carrés sont 1, 2 et 4, donc les non-résidus sont 3, 5 et 6. Le total vaut toujours (p − 1)/2, un contrôle intégré. 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

Non-résidus: 3, 5, 6
Quantité: 3
Nombre de résidus: 3
Nombre attendu: 3

Un non-résidu quadratique modulo un premier impair p est une classe de résidu non nulle a pour laquelle la congruence x au carré congruent à a modulo p n'admet aucune solution entière. Pour tout premier impair, exactement la moitié des classes non nulles sont des résidus et l'autre moitié des non-résidus, de sorte que dresser la liste des non-résidus constitue une réponse constructive complète plutôt qu'un simple oui ou non. Les étudiants, les programmeurs de concours et les personnes qui apprennent la cryptographie ont souvent besoin de l'ensemble complet pour des tableaux, des vérifications ponctuelles du symbole de Legendre et des exemples pédagogiques avant d'invoquer des algorithmes plus lourds de racine carrée modulaire. Cette capacité accepte un unique premier impair p, vérifie la primalité, marque chaque classe carrée par un parcours déterministe et renvoie la liste triée des non-résidus de un à p moins un, avec les effectifs théoriques.

Non-résidus quadratiques et pourquoi la liste fait la moitié de 1..p−1

Fixez un premier impair p. Pour chaque entier a non divisible par p, le polynôme X au carré moins a a soit deux racines, soit aucune dans le corps des entiers modulo p. Les classes avec racines sont les résidus quadratiques non nuls ; les classes sans racines sont les non-résidus quadratiques.

Zéro est toujours un carré (zéro au carré) et les manuels le traitent en général à part de la partition résidus / non-résidus non nuls. La structure multiplicative impose un équilibre parfait : l'application qui envoie x vers x au carré sur le groupe multiplicatif d'ordre p moins un est deux-à-un sur un sous-groupe d'indice deux, de sorte qu'il y a exactement (p moins un) sur deux résidus et le même nombre de non-résidus.

Les petites tables classiques le confirment : modulo sept les carrés non nuls sont un, deux et quatre, donc les non-résidus sont trois, cinq et six ; modulo onze les non-résidus sont deux, six, sept, huit et dix. Le symbole de Legendre encode la même partition comme plus un ou moins un, mais un seul symbole n'énumère pas l'ensemble complet.

Où les listes complètes de non-résidus interviennent dans le travail réel

Les programmeurs de concours utilisent l'ensemble comme oracle lorsqu'ils construisent des générateurs qui échantillonnent des non-résidus pour des tests de hachage ou des contre-exemples à des conjectures naïves de racine carrée. Les étudiants en cryptographie vérifient les affirmations du manuel sur la taille de l'ensemble des non-résidus avant d'étudier la réciprocité quadratique, le critère d'Euler ou des chiffrements de style Rabin qui dépendent de la structure des résidus.

Les ingénieurs qui écrivent des tests de propriétés pour des aides d'arithmétique modulaire peuvent affirmer que le complémentaire de leur chercheur de résidus coïncide avec cette liste pour tout premier impair jusqu'à une borne modeste. Si vous n'avez besoin que d'un symbole de Legendre ou d'un oui ou non pour un a modulo un module général, préférez les outils frères de résidu et de symbole ; cette page est consacrée à la liste complète des non-résidus d'un premier impair.

Cas d’usage

Clés de devoirs et tableaux

Générez la liste triée complète des non-résidus quadratiques modulo un petit premier impair pour exercices, diapositives et barèmes sans construire de solveur CRT.

Oracles de concours et tests de propriétés

Affirmez qu'un chercheur local de résidus et cette liste de non-résidus forment une partition de 1..p-1 pour tout premier impair dans une plage de test.

Exemples de cours de cryptographie

Échantillonnez des non-résidus pour des démonstrations pédagogiques de type Rabin ou de réciprocité quadratique lorsque vous avez besoin de classes concrètes, et non seulement du signe du symbole de Legendre.

Questions fréquentes

Qu'est-ce qu'un non-résidu quadratique modulo p ?

Pour un premier impair p, un entier a non divisible par p est un non-résidu quadratique modulo p lorsqu'aucun entier x ne satisfait x² ≡ a (mod p). Cet outil renvoie tous ces a dans 1..p-1, triés par ordre croissant.

Pourquoi p doit-il être un premier impair ?

La partition classique résidus / non-résidus non nuls de taille (p−1)/2 chacun est énoncée pour les premiers impairs.

Quelle taille de p est prise en charge ?

p doit être un entier de 3 à 100,000 inclus et doit être un premier impair.

Quels sont les non-résidus quadratiques modulo 11 ?

Ce sont 2, 6, 7, 8 et 10. Cela fait cinq, exactement la moitié des dix restes non nuls, comme pour tout nombre premier impair.

Zéro est-il un résidu ou un non-résidu ?

Zéro est toujours un carré, puisque zéro au carré vaut zéro, et il est traité à part. La liste ne porte donc que sur les restes de 1 à p − 1.

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/quadratic-nonresidues-list

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-nonresidues-list \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"p":7}'

const res = await fetch("https://api.kit.forhosting.com/numth/quadratic-nonresidues-list", {
  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/quadratic-nonresidues-list",
    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/quadratic-nonresidues-list", 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/quadratic-nonresidues-list", 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.quadratic_nonresidues_list",
  "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

`min_p`	3
`max_p`	100000

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

Non-résidus quadratiques et pourquoi la liste fait la moitié de 1..p−1

C'est ce que cet endpoint met en œuvre : arithmétique entière pure, clés JSON stables, sans dépendre de bibliothèques externes ni d'une primalité probabiliste au-delà d'une division d'essai déterministe dans la borne de taille documentée.

Contrat d'entrée, limites et champs de réponse

Envoyez un unique champ entier p, le module premier impair. Exemple : pour p égal à sept le tableau nonresidues est trois, cinq, six et count vaut trois. Les objets vides, les chaînes décimales et les valeurs au-dessus du maximum documenté sont rejetés avec un message en anglais qui nomme le champ. Les alias optionnels prime, modulus et mod sont acceptés avec le même sens. La valeur doit être comprise entre trois et cent mille inclus et doit réellement être un premier impair ; les pairs, les composés comme neuf ou quinze, le premier deux, les non-entiers et l'entrée manquante échouent la validation avec invalid_input et ne sont pas facturés. En cas de succès, la charge utile inclut p, nonresidues comme la liste croissante de tout a de un à p moins un qui n'est pas un carré modulo p, count égal à la longueur de cette liste, residue_count égal au nombre de résidus quadratiques non nuls et expected_count égal à (p moins un) sur deux. Pour un premier impair correct, count, residue_count et expected_count coïncident avec cette identité de moitié, ce qui constitue une auto-vérification utile lorsque vous consommez l'API depuis des scripts.

Où les listes complètes de non-résidus interviennent dans le travail réel

Les cours de théorie des nombres proposent des exercices du type listez tous les non-résidus quadratiques modulo dix-sept ou comparez des tables de résidus entre petits premiers ; une liste JSON déterministe élimine les erreurs de décalage dans les grilles manuscrites. Comme la capacité est un moteur parse pur, il n'y a ni dérive de modèle, ni clé d'API externe, ni état stocké : le même p produit toujours le même tableau nonresidues. Le tarif API est la base publiée de $0.002 par élément réussi ; une validation échouée ne consomme pas le solde.

Questions techniques

Combien y a-t-il de non-résidus ?

Exactement (p−1)/2. Les champs de réponse count et expected_count rapportent cette valeur ; residue_count coïncide aussi pour les résidus non nuls.

Quel est le tarif pour lister les non-résidus modulo p ?

Le widget web qui dresse la liste des non-résidus d'un premier impair tourne gratuitement dans le navigateur. Chaque appel API abouti débite $0.002 du solde prépayé KIT ; un p rejeté comme non premier n'est pas facturé.

Consulter la documentation complète du KIT →

Lancer gratuitement

Exemple résolu

Non-résidus quadratiques et pourquoi la liste fait la moitié de 1..p−1

Où les listes complètes de non-résidus interviennent dans le travail réel

Cas d’usage

Clés de devoirs et tableaux

Oracles de concours et tests de propriétés

Exemples de cours de cryptographie

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

Non-résidus quadratiques et pourquoi la liste fait la moitié de 1..p−1

Contrat d'entrée, limites et champs de réponse

Où les listes complètes de non-résidus interviennent dans le travail réel

Questions techniques

merci