Raiz n-ésima modular

Uma raiz k-ésima modular de um inteiro a módulo um primo p é qualquer resíduo x tal que x elevado a k é congruente a a módulo p. Raízes quadradas módulo primos aparecem em tutoriais de Tonelli–Shanks, raízes cúbicas e superiores na álgebra de corpos finitos, e cursos de criptografia precisam de um oráculo confiável que liste todas as raízes ou recuse com clareza quando nenhuma existe. Esta calculadora aceita a, um expoente positivo k e um módulo primo p, reduz a ao intervalo canônico de zero a p menos um e devolve a lista ordenada completa de soluções nesse corpo.

O que são raízes k-ésimas modulares e quando existem

No grupo multiplicativo de um corpo primo todo resíduo não nulo tem uma ordem bem definida que divide p menos um. Elevar x a k produz um mapa cuja imagem é o conjunto dos resíduos potência k-ésima. Para um alvo a não nulo a congruência x a k congruente a a módulo p tem soluções se e somente se a elevado a (p menos um) dividido por d for congruente a um, onde d é o máximo divisor comum de k e p menos um.

Quando esse critério vale há exatamente d raízes não nulas distintas. O resíduo zero é especial: zero a qualquer potência positiva é zero, logo a congruente a zero tem a única raiz zero. Módulos compostos ficam fora desse quadro de grupo cíclico e são rejeitados para que o solver nunca finja que um produto pelo teorema chinês dos restos é uma resposta de corpo primo.

Estudantes encontram raízes quadradas ao checar símbolos de Legendre à mão, raízes superiores ao estudar cosets ciclotômicos ou logaritmos discretos, e falhas de existência quando um exercício pede a raiz cúbica de um não resíduo cúbico.

Como esta calculadora encontra cada raiz

Chame a capacidade com os campos inteiros a, k e p. A implementação primeiro verifica que k é um inteiro positivo e que p é um primo dentro do limite publicado com um teste de Miller–Rabin determinístico. Após reduzir a módulo p, o caso de resíduo zero devolve a única raiz zero.

Para a não nulo calcula d igual ao mdc de k e p menos um e aplica o teste de existência acima. Quando d vale um há uma raiz única obtida elevando a ao inverso modular de k módulo p menos um, o caminho rápido para expoentes coprimos.

Quando d é maior que um o solver encontra uma raiz primitiva g módulo p, recupera o logaritmo discreto de a na base g com baby-step giant-step e resolve a congruência linear k vezes y congruente a esse logaritmo módulo p menos um. Cada raiz devolvida é verificada por exponenciação modular antes da resposta.

Os valores absolutos de a e k estão limitados a um trilhão e o primo p perto de um bilhão para a memória de baby-step giant-step permanecer prática; se d ultrapassar dez mil raízes a requisição é recusada em vez de inundar o cliente.