Calculadora de raiz primitiva

Uma raiz primitiva módulo um primo p é um gerador do grupo multiplicativo de resíduos não nulos módulo p. Em termos simples, algum inteiro g entre 1 e p menos um tem a propriedade de que suas potências sucessivas g, g ao quadrado, g ao cubo, e assim por diante, eventualmente atingem toda classe residual coprima com p antes de repetir. Esse g é um gerador de (Z/pZ)*, e o menor g positivo desse tipo é a resposta clássica de teoria dos números que estudantes, criptógrafos, e solucionadores de concursos procuram. Esta calculadora recebe um módulo primo p, verifica que p é primo, fatora p menos um, e retorna a menor raiz primitiva junto com a ordem do grupo e a fatoração em potências primas de p menos um. O caminho é totalmente determinístico: Miller-Rabin com conjuntos de testemunhas fixos, fatoração por tentativa, e exponenciação modular sem rede, sem aleatoriedade, e sem dependência de data.

O que é uma raiz primitiva e o que a resposta contém

Para um módulo primo p, o conjunto de resíduos 1, 2, …, p menos um forma um grupo multiplicativo cíclico de ordem p menos um. Um inteiro g é uma raiz primitiva módulo p quando a ordem de g nesse grupo é exatamente p menos um: as potências g elevado a k, para k de 0 até p menos dois, são todas distintas módulo p e esgotam todo resíduo não nulo.

Nem todo inteiro é um gerador; por exemplo, módulo 7, as potências de 2 ciclam por apenas três valores antes de repetir, então 2 não é uma raiz primitiva, enquanto 3 gera todas as seis unidades e é a menor. Não há palpite probabilístico apresentado como uma raiz, nem substituto silencioso para módulos compostos, porque uma raiz primitiva no sentido clássico é definida para primos (e algumas famílias compostas especiais que esta página não cobre).

Se você precisar de fatores de um inteiro arbitrário, em vez de um gerador módulo p, use uma capacidade de fatoração; esta página responde apenas à pergunta do menor gerador módulo primo.

Como o primo é verificado e como a menor raiz é encontrada

Sinais de mais à esquerda são permitidos; espaços incorporados, prefixos hexadecimais e notação exponencial são rejeitados com uma mensagem clara, para que uma célula ruim não vire um gerador errado. Depois da análise, o mecanismo executa um teste de primalidade de Miller-Rabin determinístico, com conjuntos de testemunhas comprovadamente suficientes para todo inteiro de até quinze dígitos decimais.

Quando p é primo, o mecanismo fatora p menos um por divisão de tentativa com roda, coleta os fatores primos distintos q dessa ordem, e busca g igual a 2, 3, 4, … pelo primeiro candidato tal que g elevado a (p menos um) dividido por q não seja congruente a 1 módulo p para todo q desses. Esse critério clássico é necessário e suficiente para que g tenha ordem p menos um. O caso especial p igual a 2 retorna raiz primitiva 1, a única unidade nesse grupo.

Onde as menores raízes primitivas se encaixam no estudo, na criptografia e no código

Estudantes encontram raízes primitivas ao aprender grupos cíclicos, logaritmos discretos, e a estrutura de corpos finitos de ordem prima. Planilhas de exercícios costumam pedir o menor gerador módulo um primo pequeno; esta página retorna essa resposta com a fatoração de apoio de p menos um, para que você possa verificar os testes de ordem à mão. Problemas de concurso e enunciados de kata de programação frequentemente exigem a menor raiz primitiva como uma sub-rotina para construir polinômios primitivos, indexar tabelas de logaritmo discreto, ou alimentar demonstrações de teoria dos números.

Na criptografia aplicada, Diffie-Hellman e construções relacionadas precisam de um gerador de um subgrupo grande de ordem prima; embora sistemas de produção usem primos seguros cuidadosamente escolhidos e geradores padronizados, uma calculadora transparente para primos comuns ainda é útil quando você valida parâmetros do tamanho de tarefas de casa, escreve testes unitários para ajudantes de ordem modular, ou explica por que g igual a 2 funciona para alguns primos e não para outros. Professores podem gerar gabaritos previamente sem confiar em widgets web opacos.