ForHosting KIT · Mathématiques

Racine carrée modulaire de Cipolla

L’algorithme de Cipolla vous donne la racine carrée elle-même modulo un premier impair, pas seulement un oui ou un non : pour 2 modulo 7, il renvoie 3 et 4, car 3 au carré vaut 9, soit 2 modulo 7. 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

A: 2
Puissance (W): 7

Vous obtenez

A modulo: 2
Racines: 3, 4
Racine: 3
Oméga: 0

L'algorithme de Cipolla est une méthode classique de théorie des nombres pour extraire des racines carrées modulo un nombre premier impair. Étant donnés un entier a et un premier impair p, il renvoie un entier x tel que x au carré est congruent à a modulo p lorsque a est un résidu quadratique. Les devoirs de cryptographie, la programmation de concours et les tutoriels d'arithmétique modulaire ont souvent besoin de la racine explicite — pas seulement du test oui ou non de résiduosité du symbole de Legendre.

Qu'est-ce qu'une racine carrée modulaire et quand Cipolla s'applique

En arithmétique modulaire la congruence x au carré congruent à a modulo p demande un entier x dont le carré tombe dans la même classe de résidu que a. Lorsque p est un premier impair la réponse théorique est nette : soit a est divisible par p et la seule racine est zéro, soit exactement la moitié des classes non nulles sont des résidus quadratiques et chaque résidu a exactement deux racines r et p moins r.

Le symbole de Legendre indique dans quel cas vous vous trouvez, mais ne construit pas r. L'algorithme de Cipolla comble ce vide en travaillant dans une extension quadratique choisie du corps à p éléments. On choisit un entier auxiliaire omega tel que omega au carré moins a soit un non-résidu quadratique modulo p ; alors l'élément omega plus une racine carrée formelle de ce non-résidu, élevé à la puissance (p plus un) divisée par deux, retombe dans le corps de base et égale une racine carrée de a.

Elle échoue aussi lorsque p est composé ou pair, car l'algorithme classique et le critère d'Euler supposent un module premier impair. Par rapport à Tonelli–Shanks, Cipolla est souvent plus court à implémenter pour des démonstrations pédagogiques et des premiers de taille moyenne, et n'exige pas de factoriser p moins un. Cette capacité s'adresse donc aux étudiants, enseignants et scripts qui veulent un chemin Cipolla transparent avec des racines ordonnées stables et un contrat d'erreur documenté.

Où les racines carrées modulaires de Cipolla apportent de la valeur

Les salles de classe qui traitent des résidus quadratiques peuvent montrer que la résiduosité seule ne suffit pas, puis appeler ce point d'accès pour exhiber les vraies racines de nombreux résidus sans calculer à la main des puissances dans le corps d'extension. Les plateformes de concours et les correcteurs LMS ont besoin d'un oracle déterministe qui rejette non-résidus et modules composés au lieu de renvoyer des tableaux vides qu'un client bogué pourrait traiter comme succès.

Les notes de cryptographie qui introduisent le chiffrement Rabin ou la décompression de points sur des corps premiers veulent souvent un parcours Cipolla à côté de Tonelli–Shanks ; un module pur partagé garde les démos navigateur et les contrôles serveur identiques. Gardez p dans la borne première publiée, figez le tableau de racines ordonnées dans les tests, et vous obtenez des racines carrées modulaires reproductibles pour l'enseignement, l'automatisation et les edge workers sans embarquer une pile complète d'algèbre computationnelle.

Cas d’usage

Cours et devoirs de théorie des nombres

Les élèves envoient a et un premier impair p et comparent les racines ordonnées renvoyées aux étapes de Cipolla faites à la main ou aux tables du manuel.

Démos pédagogiques de crypto et carnets

Illustrez Cipolla à côté des contrôles de Legendre dans des notes style Rabin ou de courbes elliptiques sans importer une bibliothèque algébrique lourde.

Questions fréquentes

Comment calculer une racine carrée modulaire avec l'algorithme de Cipolla ?

Envoyez les entiers a et un premier impair p.

Que se passe-t-il si a n'est pas un résidu quadratique modulo p ?

Aucune racine n'est inventée et l'appel n'est pas facturé.

Pourquoi p doit-il être un premier impair ?

L'algorithme de Cipolla et le critère d'Euler sont définis pour les premiers impairs. Les modules pairs ou composés sont rejetés pour que la réponse ne prétende jamais qu'un corps non premier se comporte comme F_p.

En quoi cela diffère-t-il d'un calculateur du symbole de Legendre ?

Legendre ne rapporte que la résiduosité (−1, 0 ou 1). Cette capacité construit les racines carrées explicites lorsqu'elles existent, via la puissance dans le corps d'extension de Cipolla.

Quelle différence entre l’algorithme de Cipolla et celui de Tonelli–Shanks ?

Les deux trouvent les mêmes racines. Celui de Cipolla est souvent plus court à suivre en cours et n’exige pas de factoriser p moins un : il travaille dans une extension du corps à p éléments et élève un élément à la puissance p plus un sur deux.

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/cipolla-algorithm

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/cipolla-algorithm \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":2,"p":7}'

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

import os, requests

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

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

body := bytes.NewBufferString(`{"a":2,"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/cipolla-algorithm", 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,
  "p": 7
}

Exemple de réponse

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.cipolla_algorithm",
  "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.

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

Cette capacité vérifie que p est un premier impair, rejette les non-résidus avec une erreur invalid_input claire, exécute une construction de Cipolla entièrement déterministe (sans tirages aléatoires d'omega) et renvoie les deux racines lorsqu'elles existent.

Qu'est-ce qu'une racine carrée modulaire et quand Cipolla s'applique

La construction échoue précisément lorsque a est un non-résidu, ce que ce point d'accès signale par invalid_input plutôt que d'inventer une fausse racine.

Contrat d'entrée, étapes de l'algorithme et forme de la réponse

La valeur absolue de a ne doit pas dépasser un billion. Il multiplie ensuite dans l'anneau des éléments x plus y fois racine de w, en élevant omega plus racine de w à la puissance (p plus un) sur deux avec des multiplications modulaires exactes BigInt. Exemple : a égal à deux et p égal à sept donne les racines trois et quatre, car trois au carré vaut neuf, soit deux modulo sept. Envoyez un corps JSON avec deux champs entiers obligatoires : a, le nombre dont vous voulez la racine carrée modulo p, et p, un premier impair entre trois et un billion inclus. Chaque champ peut arriver comme nombre JSON ou comme chaîne de chiffres avec signe optionnel. Champs manquants, non entiers, hors plage, p pair et p composé échouent avec invalid_input et ne sont pas facturés. Lorsque p est accepté, le gestionnaire réduit a en a_mod de zéro à p moins un. Si a_mod est zéro la réponse est la racine triviale zéro avec method trivial_zero et omega null. Sinon le symbole de Legendre de a_mod modulo p est calculé via le critère d'Euler ; la valeur moins un signifie que a est un non-résidu quadratique et la tâche échoue avec un message qui nomme la classe de résidu. Lorsque le symbole vaut plus un l'algorithme parcourt le plus petit omega non négatif tel que le Legendre de omega au carré moins a_mod vaille moins un — ce balayage est déterministe, donc la même paire utilise toujours le même témoin. La composante dans le corps est une racine carrée ; l'API renvoie les deux racines ordonnées, la racine primaire plus petite préférée, le témoin omega, method égal à cipolla et verified true après une vérification interne du carré.

Où les racines carrées modulaires de Cipolla apportent de la valeur

Les carnets de recherche qui calculent déjà les symboles de Legendre ou de Jacobi peuvent demander la racine seulement lorsque le symbole vaut un, en payant $0.002 par élément réussi et rien en cas d'échec de validation.

Cas d'intégration

Programmation de concours et notation LMS

Les correcteurs vérifient les réponses de racine carrée modulaire, rejettent non-résidus et modules composés avec invalid_input et gardent omega déterministe d'une exécution à l'autre.

Questions techniques

Combien coûte l'outil de racine carrée modulaire de Cipolla ?

L'outil navigateur est gratuit. Les requêtes API utilisent le solde prépayé KIT à $0.002 par appel réussi ; une entrée invalide n'est pas facturée.

Consulter la documentation complète du KIT →

Lancer gratuitement

Exemple résolu

Qu'est-ce qu'une racine carrée modulaire et quand Cipolla s'applique

Où les racines carrées modulaires de Cipolla apportent de la valeur

Cas d’usage

Cours et devoirs de théorie des nombres

Démos pédagogiques de crypto et carnets

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

Erreurs

Notes techniques

Qu'est-ce qu'une racine carrée modulaire et quand Cipolla s'applique

Contrat d'entrée, étapes de l'algorithme et forme de la réponse

Où les racines carrées modulaires de Cipolla apportent de la valeur

Cas d'intégration

Programmation de concours et notation LMS

Questions techniques

merci