Verificatore di residuo quadratico
Le dice se un numero ha una radice quadrata modulo m ed elenca tutte le radici: 2 è un quadrato modulo 7, perché 3 al quadrato fa 9, che lascia 2, e le radici sono 3 e 4. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- A
- 2
- Modulo m
- 7
- A modulo
- 2
- Radici
- 3, 4
- N. di radici
- 2
Un intero a è residuo quadratico modulo m quando qualche intero x soddisfa x al quadrato congruente ad a modulo m — in altre parole, a ha una radice quadrata modulare. Quella domanda sì-o-no compare nei compiti di crittografia, nella teoria dei numeri di gara e in ogni flusso che deve sapere se una congruenza è un quadrato perfetto prima di investire sforzo in un risolutore più ampio. Questa capacità prende a e un modulo m (almeno due), riduce a nell'intervallo canonico da zero a m meno uno, scansiona ogni radice in quell'intervallo e può opzionalmente restituire l'elenco completo delle classi di residuo quadratico modulo m.
Cosa significa la residualità quadratica per moduli generali
Nella teoria elementare dei numeri un residuo quadratico modulo un primo p di solito significa un intero a non divisibile per p per cui la congruenza x al quadrato uguale ad a modulo p ha una soluzione; lo zero è spesso trattato a parte come il quadrato banale. Per un modulo composto m la stessa definizione si estende in modo pulito: a è residuo quadratico modulo m quando esiste almeno un intero x con x al quadrato congruente ad a modulo m, incluso il caso a congruente a zero.
Le soluzioni seguono schemi che dipendono dalla fattorizzazione in potenze prime di m; ad esempio modulo un primo ci sono zero o due radici non nulle per ogni classe di residuo non nulla che è un quadrato, mentre i moduli composti possono ammettere più radici. Strumenti classici come i simboli di Legendre e Jacobi danno test rapidi quando m è un primo dispari o quando serve solo un carattere moltiplicativo, ma non elencano da soli ogni radice per m arbitrario.
Una scansione diretta di x da zero a m meno uno valuta ogni classe di quadrato esattamente una volta e quindi risponde sia all'esistenza sia all'enumerazione per qualsiasi modulo entro un limite di dimensione fisso.
Dove i controlli di quadrati modulari compaiono nel lavoro reale
I programmatori di gara spesso servono un oracolo rapido prima di invocare Tonelli–Shanks o una combinazione CRT di radici in potenze prime: se il bit di residuo è falso, non ha senso costruire una radice quadrata. Gli studenti di crittografia verificano esempi di cifrari in stile Rabin, esercizi di reciprocità quadratica e varianti giocattolo di Diffie–Hellman che menzionano simboli di residuo. Gli ingegneri che riconciliano orari periodici o esperimenti di bucket hash a volte chiedono se un passo è una classe di quadrato modulo un periodo composto.
Se serve solo un sì-o-no in stile simbolo di Legendre per un primo grande oltre il limite di scansione, fattorizzi o riduca prima; entro il tetto questa pagina è la risposta costruttiva completa.
Casi d'uso
Controlli di compiti e gare
Decida se a è un quadrato modulo m e legga ogni radice in 0..m-1 per esercizi di teoria dei numeri senza costruire un risolutore CRT completo.
Pre-filtro prima dell'estrazione di radici
Rifiuti i non residui presto in una pipeline che altrimenti tenterebbe algoritmi di radice quadrata modulare su moduli composti o primi.
Domande frequenti
Che cos'è un residuo quadratico modulo m?
Un intero a è residuo quadratico modulo m se esiste un intero x tale che x² ≡ a (mod m). Questo strumento riporta quel fatto e elenca ogni tale x in 0..m-1.
Perché m deve essere almeno 2?
Il modulo 0 è indefinito per le congruenze su questa superficie di prodotto, e il modulo 1 collassa ogni intero in una sola classe.
Quale dimensione di modulo è supportata?
m deve essere un intero da 2 a 1,000,000 incluso. Il candidato a può essere qualsiasi intero sicuro; viene ridotto modulo m prima della scansione.
Quanto costa?
Lo strumento browser è gratuito e gira in locale.
3 è un residuo quadratico modulo 7?
No. Elevando al quadrato ogni resto modulo 7 si ottengono solo 0, 1, 2 o 4, quindi nessun intero al quadrato lascia 3 e l'elenco delle radici risulta vuoto.
Strumenti correlati
Per sviluppatori — accesso via API
Tutto quello che vedi in questa pagina è disponibile anche via API. Questa sezione è per i team che vogliono integrarlo nei propri sistemi; chi non ne ha bisogno può semplicemente usare lo strumento qui sopra.
Endpoint
Autenticazione con Bearer token: un POST mette in coda l'attività e il risultato arriva via webhook o link firmato.
Chiamala dal tuo 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)Esempio di richiesta
{
"a": 2,
"m": 7
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.quadratic_residue",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L'API è asincrona: ricevi subito un task_id e puoi fare polling fino a 1 richiesta al secondo.
Prezzi
Prezzo pubblicato, senza token né crediti. Se l'attività fallisce, non paghi.
Limiti
min_m | 2 |
max_m | 1000000 |
max_abs_a | 9007199254740991 |
Errori
| HTTP | Codice | Significato |
|---|---|---|
401 | unauthorized | Chiave API mancante o non valida: controlla l'header Authorization. |
402 | insufficient_balance | Credito esaurito: ricarica per continuare a eseguire attività. |
404 | unknown_type | Tipo di attività sconosciuto: controlla il campo type della richiesta. |
429 | rate_limited | Troppe richieste in poco tempo: rallenta e riprova tra qualche secondo. |
Note tecniche
Cosa significa la residualità quadratica per moduli generali
Quell'approccio esaustivo è ciò che questo endpoint implementa: solo aritmetica intera deterministica, nessun arrotondamento in virgola mobile, e una forma JSON stabile che può asserire nei test.
Contratto di ingresso, limiti e campi di risposta
Invii interi a e m. Controlli tipici di lezione: due è residuo quadratico modulo sette perché tre al quadrato è nove che è due mod sette, e le radici sono tre e quattro; tre non è residuo quadratico modulo sette. Non interi, campi obbligatori vuoti e moduli sopra il tetto falliscono la validazione con un messaggio chiaro che nomina il campo. Il modulo m deve essere almeno due e al più un milione; i valori sotto due vengono rifiutati con invalid_input e non addebitati, perché l'aritmetica modulare con modulo zero o uno non è una superficie di prodotto supportata. Il candidato a può essere negativo o maggiore di m; viene ridotto ad a_mod nell'intervallo semiaperto da zero inclusivo a m esclusivo prima della ricerca dei quadrati. Il booleano opzionale list_residues (alias list_all e all_residues) chiede ogni valore distinto di x al quadrato modulo m, ordinato in modo crescente, insieme a residue_count. In caso di successo il payload include sempre a, m, a_mod, is_quadratic_residue, roots come l'elenco completo delle soluzioni da zero a m meno uno, e root_count. Quando list_residues è vero per m uguale a sette si ottengono le classi ordinate zero, uno, due e quattro — l'immagine della mappa di elevazione al quadrato sull'anello degli interi modulo sette.
Dove i controlli di quadrati modulari compaiono nel lavoro reale
I docenti assegnano problemi come elencare tutti i residui quadratici modulo ventuno o decidere se cinque è un quadrato modulo tredici e vogliono una risposta JSON deterministica piuttosto che una tabella a mano che può contenere errori di uno. Poiché la capacità è un motore di parse puro non c'è deriva di modello, nessuna chiave API esterna e nessuno stato memorizzato: la stessa coppia produce sempre le stesse radici e lo stesso elenco opzionale di residui. Il prezzo API è la base pubblicata di $0.002 per elemento riuscito; la validazione fallita non consuma saldo.
Casi di integrazione
Enumerare le classi di residuo
Imposti list_residues a vero per ottenere l'immagine ordinata della mappa di elevazione al quadrato modulo m per tabelle, slide didattiche o test basati su proprietà.
Domande tecniche
0 è considerato un residuo quadratico?
Sì. 0² ≡ 0 (mod m), quindi a_mod = 0 è sempre un residuo e include la radice 0 (e possibilmente altre per m composto).