Resíduo potência n-ésima

Um inteiro a é resíduo de potência k-ésima módulo um primo p quando existe um inteiro x tal que x elevado a k é congruente a a módulo p. Essa pergunta generaliza a residualidade quadrática (o caso k igual a dois) para cubos, potências superiores e expoentes positivos arbitrários usados em teoria dos números de competições e criptografia introdutória. Esta capacidade recebe um candidato a, um expoente positivo k e um módulo primo p, reduz a ao intervalo de zero a p menos um, verifica se p é primo e aplica o critério padrão do grupo cíclico no grupo multiplicativo do corpo com p elementos. Quando a é divisível por p a resposta é sempre sim para k pelo menos um, porque zero a qualquer potência positiva é zero.

O que significa um resíduo de potência k-ésima módulo um primo

Fixe um módulo primo p e um inteiro positivo k. As classes de resíduo módulo p formam um corpo, e seus elementos não nulos formam um grupo multiplicativo cíclico de ordem p menos um. Um inteiro a não divisível por p é resíduo de potência k-ésima módulo p precisamente quando a pertence à imagem da aplicação que envia cada classe não nula x para x elevado a k.

Como o grupo é cíclico, essa imagem é o único subgrupo de índice igual ao máximo divisor comum d de k e p menos um, e a pertence a esse subgrupo se e somente se a elevado à potência (p menos um) dividida por d é congruente a um módulo p. Essa única exponenciação modular é o procedimento de decisão usado aqui.

Quando a é divisível por p, a congruência x à k congruente a a tem a solução trivial x congruente a zero para todo k pelo menos um, de modo que zero sempre é tratado como resíduo de potência k-ésima. Casos especiais recuperam ferramentas conhecidas: para k igual a dois e p primo ímpar o critério é o de Euler para residualidade quadrática, a mesma informação do símbolo de Legendre, enquanto para k igual a p menos um todo a não nulo é resíduo pelo pequeno teorema de Fermat.

Contrato de entrada, verificação de primalidade e campos de resposta

Envie os inteiros a, k e p. O expoente k deve ser pelo menos um e no máximo um trilhão. Nomes de campos opcionais nunca são preenchidos com null: o par de critério é simplesmente omitido no caso de resíduo zero.

Checagens clássicas que você pode reproduzir à mão: para a igual a dois, k igual a três e p igual a sete, o gcd de três e seis é três, então o expoente de critério é dois e dois ao quadrado é quatro módulo sete, não um; portanto dois não é resíduo cúbico módulo sete; em contraste, um sempre é resíduo de potência k-ésima para todo primo porque um a qualquer potência é um.

Não inteiros, campos obrigatórios ausentes e expoentes abaixo de um falham a validação com mensagem clara em inglês.

Onde as checagens de resíduo de potência superior aparecem no trabalho real

Programadores de competição precisam de um oráculo rápido antes de tentar extrair raízes cúbicas modulares ou de ordem superior: se o bit de resíduo for falso não faz sentido procurar x. Estudantes de criptografia verificam exercícios sobre a imagem do mapa de potência em corpos finitos, exemplos de cálculo de índice e construções didáticas que dependem de a classe de mensagem ser potência k-ésima antes de aplicar um mapa.

Pipelines de pesquisa e lição de casa que já usam símbolos de Legendre ou Jacobi para quadrados frequentemente precisam da mesma resposta sim ou não para cubos e potências superiores sem trocar de biblioteca. Se você só precisa de residualidade quadrática, as ferramentas dedicadas de resíduo quadrático e símbolo de Legendre continuam disponíveis; esta página é a decisão geral de potência k-ésima para módulos primos.