Lista de não resíduos quadráticos mod p
Lista cada resto que nunca é um quadrado módulo um primo ímpar: módulo 7 os quadrados são 1, 2 e 4, então os não resíduos são 3, 5 e 6. O total sempre é (p − 1)/2, uma conferência embutida. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- Potência (W)
- 7
- Não resíduos
- 3, 5, 6
- Quantidade
- 3
- Quantidade de resíduos
- 3
- Quantidade esperada
- 3
Um não resíduo quadrático módulo um primo ímpar p é uma classe de resíduo não nula a para a qual a congruência x ao quadrado congruente com a módulo p não possui solução inteira. Para todo primo ímpar há exatamente metade das classes não nulas que são resíduos e metade que são não resíduos, de modo que listar os não resíduos é uma resposta construtiva completa e não um simples sim ou não. Estudantes, programadores de competições e quem estuda criptografia costumam precisar do conjunto inteiro para tabelas, verificações pontuais do símbolo de Legendre e exemplos didáticos antes de invocar algoritmos mais pesados de raiz quadrada modular. Esta capacidade aceita um único primo ímpar p, verifica a primalidade, marca cada classe quadrada com uma varredura determinística e devolve a lista ordenada de não resíduos de um até p menos um junto com as contagens teóricas.
Não resíduos quadráticos e por que a lista é metade de 1..p−1
Fixe um primo ímpar p. Para cada inteiro a não divisível por p, o polinômio X ao quadrado menos a tem ou duas raízes ou nenhuma no corpo dos inteiros módulo p. As classes com raízes são os resíduos quadráticos não nulos; as classes sem raízes são os não resíduos quadráticos.
O zero é sempre um quadrado (zero ao quadrado) e os manuais costumam tratá-lo à parte da partição entre resíduos e não resíduos não nulos. A estrutura multiplicativa impõe um equilíbrio perfeito: o mapa que envia x para x ao quadrado no grupo multiplicativo de ordem p menos um é dois para um sobre um subgrupo de índice dois, de modo que há exatamente (p menos um) sobre dois resíduos e o mesmo número de não resíduos.
Tabelas clássicas confirmam a contagem: módulo sete os quadrados não nulos são um, dois e quatro, logo os não resíduos são três, cinco e seis; módulo onze os não resíduos são dois, seis, sete, oito e dez. O símbolo de Legendre codifica a mesma partição como mais um ou menos um, mas um único símbolo não enumera o conjunto completo.
Onde listas completas de não resíduos aparecem no trabalho real
Programadores de competições usam o conjunto como oráculo ao construir geradores que amostram não resíduos para testes de hash ou contraexemplos a conjecturas ingênuas de raiz quadrada. Estudantes de criptografia verificam as afirmações do manual sobre o tamanho do conjunto de não resíduos antes de estudar a reciprocidade quadrática, o critério de Euler ou cifras no estilo Rabin que dependem da estrutura de resíduos.
Engenheiros que escrevem testes de propriedades para auxiliares de aritmética modular podem afirmar que o complemento do seu buscador de resíduos coincide com esta lista para todo primo ímpar até um limite modesto. Se você só precisa de um símbolo de Legendre ou de um sim ou não para um a módulo um módulo geral, prefira as ferramentas irmãs de resíduo e símbolo; esta página dedica-se à lista completa de não resíduos de um primo ímpar.
Casos de uso
Chaves de exercícios e tabelas
Gere a lista ordenada completa de não resíduos quadráticos módulo um primo ímpar pequeno para exercícios, slides e chaves de correção sem construir um solucionador CRT.
Oráculos de competição e testes de propriedades
Afirme que um buscador local de resíduos e esta lista de não resíduos formam uma partição de 1..p-1 para todo primo ímpar em um intervalo de teste.
Exemplos de cursos de criptografia
Amostre não resíduos para demonstrações didáticas de Rabin ou de reciprocidade quadrática quando precisar de classes concretas, e não apenas do sinal do símbolo de Legendre.
Perguntas frequentes
O que é um não resíduo quadrático módulo p?
Para um primo ímpar p, um inteiro a não divisível por p é um não resíduo quadrático módulo p quando nenhum inteiro x satisfaz x² ≡ a (mod p). Esta ferramenta devolve todos esses a em 1..p-1, ordenados de forma ascendente.
Por que p deve ser um primo ímpar?
A partição clássica entre resíduos e não resíduos não nulos de tamanho (p−1)/2 cada um é enunciada para primos ímpares.
Qual tamanho de p é suportado?
p deve ser um inteiro de 3 até 100,000 inclusive e deve ser um primo ímpar.
Quanto custa?
A ferramenta do navegador é gratuita e roda localmente.
Quais são os não resíduos quadráticos módulo 11?
São 2, 6, 7, 8 e 10. São cinco, exatamente a metade dos dez restos diferentes de zero, como acontece com todo primo ímpar.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
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)Exemplo de requisição
{
"p": 7
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.quadratic_nonresidues_list",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Limites
min_p | 3 |
max_p | 100000 |
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
Não resíduos quadráticos e por que a lista é metade de 1..p−1
É isso que este endpoint implementa: aritmética inteira pura, chaves JSON estáveis e sem depender de bibliotecas externas nem de primalidade probabilística além da divisão de teste determinística dentro do limite de tamanho documentado.
Contrato de entrada, limites e campos de resposta
Envie um único campo inteiro p, o módulo primo ímpar. Exemplo: para p igual a sete o arranjo nonresidues é três, cinco, seis e count é três. Objetos vazios, cadeias decimais e valores acima do máximo documentado são rejeitados com uma mensagem em inglês que nomeia o campo. Os aliases opcionais prime, modulus e mod são aceitos com o mesmo significado. O valor deve estar entre três e cem mil inclusive e deve ser de fato um primo ímpar; números pares, compostos como nove ou quinze, o primo dois, não inteiros e entrada ausente falham a validação com invalid_input e não são cobrados. Em caso de sucesso o payload inclui p, nonresidues como a lista ascendente de todo a em um até p menos um que não é quadrado módulo p, count igual ao comprimento dessa lista, residue_count igual ao número de resíduos quadráticos não nulos e expected_count igual a (p menos um) sobre dois. Para um primo ímpar correto, count, residue_count e expected_count coincidem com essa identidade da metade, o que é uma auto-verificação útil quando você consome a API a partir de scripts.
Onde listas completas de não resíduos aparecem no trabalho real
Cursos de teoria dos números propõem problemas do tipo liste todos os não resíduos quadráticos módulo dezessete ou compare tabelas de resíduos entre primos pequenos; uma lista JSON determinística elimina erros de deslocamento em grades feitas à mão. Como a capacidade é um motor parse puro não há deriva de modelo, nem chave de API externa nem estado armazenado: o mesmo p produz sempre o mesmo arranjo nonresidues. O preço da API é a base publicada de US$ 0,002 por item bem-sucedido; a validação falha não consome saldo.
Perguntas técnicas
Quantos não resíduos existem?
Exatamente (p−1)/2. Os campos de resposta count e expected_count reportam esse valor; residue_count também o coincide para os resíduos não nulos.