Non residui quadratici mod p
Elenca ogni resto che non è mai un quadrato modulo un primo dispari: modulo 7 i quadrati sono 1, 2 e 4, quindi i non residui sono 3, 5 e 6. Il totale è sempre (p − 1)/2, una verifica incorporata. Gratis nel suo browser.
- Gratis
- Funziona nel suo browser
- Senza registrazione
- I suoi dati restano sul dispositivo
Esegui gratis nel browser
Esempio risolto
- Potenza (W)
- 7
- Non residui
- 3, 5, 6
- Quantità
- 3
- Numero di residui
- 3
- Numero atteso
- 3
Un non residuo quadratico modulo un primo dispari p è una classe di residuo non nulla a per la quale la congruenza x al quadrato congruente ad a modulo p non ammette soluzione intera. Per ogni primo dispari esattamente metà delle classi non nulle sono residui e metà sono non residui, quindi elencare i non residui è una risposta costruttiva completa e non un semplice sì o no. Studenti, programmatori di gare e chi studia crittografia spesso necessitano dell'insieme intero per tabelle, controlli puntuali del simbolo di Legendre ed esempi didattici prima di invocare algoritmi più pesanti di radice quadrata modulare. Questa capacità accetta un unico primo dispari p, verifica la primalità, marca ogni classe quadrata con una scansione deterministica e restituisce l'elenco ordinato dei non residui da uno a p meno uno insieme ai conteggi teorici.
Non residui quadratici e perché l'elenco è la metà di 1..p−1
Fissi un primo dispari p. Per ogni intero a non divisibile per p, il polinomio X al quadrato meno a ha due radici oppure nessuna nel campo degli interi modulo p. Le classi con radici sono i residui quadratici non nulli; le classi senza radici sono i non residui quadratici.
Lo zero è sempre un quadrato (zero al quadrato) e i manuali lo trattano di solito a parte rispetto alla partizione tra residui e non residui non nulli. La struttura moltiplicativa impone un equilibrio perfetto: l'applicazione che manda x in x al quadrato sul gruppo moltiplicativo di ordine p meno uno è due a uno su un sottogruppo di indice due, quindi ci sono esattamente (p meno uno) su due residui e lo stesso numero di non residui.
Le tabelle classiche lo confermano: modulo sette i quadrati non nulli sono uno, due e quattro, quindi i non residui sono tre, cinque e sei; modulo undici i non residui sono due, sei, sette, otto e dieci. Il simbolo di Legendre codifica la stessa partizione come più uno o meno uno, ma un solo simbolo non enumera l'insieme completo.
Dove compaiono gli elenchi completi di non residui nel lavoro reale
I programmatori di gare usano l'insieme come oracolo quando costruiscono generatori che campionano non residui per test di hash o controesempi a congetture ingenue di radice quadrata. Gli studenti di crittografia verificano le affermazioni del manuale sulla dimensione dell'insieme dei non residui prima di studiare la reciprocità quadratica, il criterio di Eulero o cifrari in stile Rabin che dipendono dalla struttura dei residui.
Gli ingegneri che scrivono test di proprietà per ausili di aritmetica modulare possono affermare che il complemento del loro cercatore di residui coincide con questo elenco per ogni primo dispari fino a un limite modesto. Se serve solo un simbolo di Legendre o un sì o no per un a modulo un modulo generale, preferisca gli strumenti fratelli di residuo e simbolo; questa pagina è dedicata all'elenco completo dei non residui di un primo dispari.
Casi d'uso
Chiavi di compiti e tabelle
Generi l'elenco ordinato completo dei non residui quadratici modulo un piccolo primo dispari per esercizi, diapositive e chiavi di valutazione senza costruire un risolutore CRT.
Oracoli di gara e test di proprietà
Affermi che un cercatore locale di residui e questo elenco di non residui formano una partizione di 1..p-1 per ogni primo dispari in un intervallo di test.
Esempi di corsi di crittografia
Campioni non residui per dimostrazioni didattiche di tipo Rabin o di reciprocità quadratica quando servono classi concrete, non solo il segno del simbolo di Legendre.
Domande frequenti
Che cos'è un non residuo quadratico modulo p?
Per un primo dispari p, un intero a non divisibile per p è un non residuo quadratico modulo p quando nessun intero x soddisfa x² ≡ a (mod p). Questo strumento restituisce tutti tali a in 1..p-1, ordinati in modo crescente.
Perché p deve essere un primo dispari?
La partizione classica residui / non residui non nulli di dimensione (p−1)/2 ciascuno è enunciata per i primi dispari.
Quale dimensione di p è supportata?
p deve essere un intero da 3 a 100,000 inclusi e deve essere un primo dispari.
Quanto costa?
Lo strumento del browser è gratuito e viene eseguito in locale.
Quali sono i non residui quadratici modulo 11?
Sono 2, 6, 7, 8 e 10. Sono cinque, esattamente la metà dei dieci resti diversi da zero, come accade per ogni primo dispari.
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-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)Esempio di richiesta
{
"p": 7
}Esempio di risposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.quadratic_nonresidues_list",
"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_p | 3 |
max_p | 100000 |
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
Non residui quadratici e perché l'elenco è la metà di 1..p−1
È ciò che questo endpoint implementa: aritmetica intera pura, chiavi JSON stabili e nessuna dipendenza da librerie esterne né da primalità probabilistica oltre alla divisione di prova deterministica entro il limite di dimensione documentato.
Contratto di ingresso, limiti e campi di risposta
Invii un unico campo intero p, il modulo primo dispari. Esempio: per p uguale a sette l'array nonresidues è tre, cinque, sei e count è tre. Oggetti vuoti, stringhe decimali e valori oltre il massimo documentato vengono rifiutati con un messaggio in inglese che nomina il campo. Gli alias opzionali prime, modulus e mod sono accettati con lo stesso significato. Il valore deve stare tra tre e centomila inclusi e deve essere davvero un primo dispari; i pari, i composti come nove o quindici, il primo due, i non interi e l'ingresso assente falliscono la validazione con invalid_input e non vengono addebitati. In caso di successo il payload include p, nonresidues come l'elenco crescente di ogni a da uno a p meno uno che non è un quadrato modulo p, count uguale alla lunghezza di tale elenco, residue_count uguale al numero di residui quadratici non nulli e expected_count uguale a (p meno uno) su due. Per un primo dispari corretto, count, residue_count e expected_count coincidono con tale identità della metà, utile come auto-controllo quando Lei consuma l'API da script.
Dove compaiono gli elenchi completi di non residui nel lavoro reale
I corsi di teoria dei numeri assegnano problemi del tipo elenchi tutti i non residui quadratici modulo diciassette o confronti tabelle di residui tra primi piccoli; un elenco JSON deterministico elimina errori di scarto nelle griglie scritte a mano. Poiché la capacità è un motore parse puro non c'è deriva di modello, né chiave API esterna né stato memorizzato: lo stesso p produce sempre lo stesso array nonresidues. Il prezzo API è la base pubblicata di $0.002 per elemento riuscito; la validazione fallita non consuma saldo.
Domande tecniche
Quanti non residui ci sono?
Esattamente (p−1)/2. I campi di risposta count e expected_count riportano quel valore; residue_count coincide pure per i residui non nulli.