Calculadora de Raiz Primitiva

Bem-vindo à Calculadora de Raiz Primitiva, uma poderosa ferramenta online gratuita que encontra todas as raízes primitivas módulo qualquer número inteiro positivo n. Esta calculadora fornece verificação passo a passo, tabelas de potências e uma visualização animada do grupo cíclico para ajudá-lo a entender como as raízes primitivas geram grupos multiplicativos. Quer você esteja estudando teoria dos números, preparando-se para exames de criptografia ou trabalhando com aritmética modular em programação competitiva, esta ferramenta fornece resultados instantâneos e precisos com insights educacionais.

O Que é uma Raiz Primitiva?

Uma raiz primitiva módulo n é um número inteiro g cujas potências geram todos os números inteiros que são coprimos com n. Formalmente, g é uma raiz primitiva mod n se a ordem multiplicativa de g módulo n for igual ao totiente de Euler \(\varphi(n)\). Isso significa que o conjunto

contém exatamente todos os \(\varphi(n)\) inteiros de 1 a n-1 que são coprimos com n. Uma raiz primitiva é essencialmente um gerador do grupo cíclico \((\mathbb{Z}/n\mathbb{Z})^*\).

Exemplo Rápido

Considere n = 7. Como 7 é primo, \(\varphi(7) = 6\). Vamos verificar se g = 3 é uma raiz primitiva:

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

As potências produzem {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}, que são todos os inteiros coprimos com 7. Portanto, 3 é uma raiz primitiva módulo 7.

Quando Existem Raízes Primitivas?

Raízes primitivas módulo n existem se e somente se n tiver uma destas formas:

• n = 1, 2 ou 4
• n = p^k onde p é um primo ímpar e k ≥ 1
• n = 2p^k onde p é um primo ímpar e k ≥ 1

Por exemplo, raízes primitivas existem para 7, 9, 11, 13, 14, 18, 23, 25, 27, 46, mas não para 8, 12, 15, 16, 20, 21, 24.

Como Encontrar Raízes Primitivas

1. Insira o módulo: Digite um número inteiro positivo n (de 2 a 100.000) no campo de entrada.
2. Calcular: Clique em "Encontrar Raízes Primitivas" ou pressione Enter.
3. Ver todas as raízes: Veja a lista completa de raízes primitivas, junto com o totiente de Euler e estatísticas.
4. Estude a tabela de potências: Examine como a menor raiz primitiva gera todos os resíduos coprimos.
5. Visualize o grupo cíclico: Para módulos pequenos, veja a roda animada mostrando a estrutura cíclica.

Quantas Raízes Primitivas n Possui?

Se existirem raízes primitivas módulo n, a contagem é igual a:

Por exemplo, para n = 13: \(\varphi(13) = 12\) e \(\varphi(12) = 4\), portanto existem exatamente 4 raízes primitivas módulo 13 (que são 2, 6, 7, 11).

O Algoritmo de Verificação

Para verificar se g é uma raiz primitiva módulo n de forma eficiente:

1. Calcule \(\varphi(n)\) usando a fatoração prima de n
2. Encontre todos os fatores primos distintos \(p_1, p_2, \ldots, p_k\) de \(\varphi(n)\)
3. Para cada fator primo \(p_i\), verifique: \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. Se TODOS os testes passarem, então g é uma raiz primitiva

Este método é muito mais rápido do que calcular todas as potências de g, pois precisamos testar apenas \(k\) exponenciações em vez de \(\varphi(n)\) delas.

Raízes Primitivas na Criptografia

Troca de Chaves Diffie-Hellman

O protocolo Diffie-Hellman usa um grande primo p e uma raiz primitiva g módulo p. Alice escolhe um segredo a, envia \(g^a \bmod p\). Bob escolhe um segredo b, envia \(g^b \bmod p\). Ambos calculam o segredo compartilhado \(g^{ab} \bmod p\). A segurança baseia-se no fato de o problema do logaritmo discreto ser computacionalmente difícil.

Criptografia ElGamal

ElGamal também usa uma raiz primitiva como geradora. A chave pública é \((p, g, g^x \bmod p)\) onde x é privado. O fato de g gerar todos os elementos garante que cada mensagem possa ser criptografada.

Assinaturas Digitais

O DSA (Digital Signature Algorithm) e esquemas relacionados usam raízes primitivas em subgrupos de \((\mathbb{Z}/p\mathbb{Z})^*\) para criar e verificar assinaturas digitais.

Tabela de Referência: Menores Raízes Primitivas

Perguntas Frequentes

O que é uma raiz primitiva módulo n?

Uma raiz primitiva módulo n é um número inteiro g tal que as potências \(g^1, g^2, \ldots, g^{\varphi(n)}\) produzem todos os números inteiros coprimos com n quando tomados módulo n. Em outras palavras, g gera todo o grupo multiplicativo \((\mathbb{Z}/n\mathbb{Z})^*\). A ordem multiplicativa de g módulo n é igual ao totiente de Euler \(\varphi(n)\).

Para quais valores de n existem raízes primitivas?

Raízes primitivas existem módulo n se e somente se n for 1, 2, 4, p^k ou 2p^k, onde p é um primo ímpar e k ≥ 1. Por exemplo, raízes primitivas existem para n = 7 (primo), n = 9 (3²), n = 14 (2×7), mas NÃO para n = 8, 12, 15 ou 16.

Quantas raízes primitivas n possui?

Se existirem raízes primitivas módulo n, o número de raízes primitivas é igual a \(\varphi(\varphi(n))\), onde \(\varphi\) é a função totiente de Euler. Por exemplo, para n = 13 (primo), \(\varphi(13) = 12\) e \(\varphi(12) = 4\), portanto existem exatamente 4 raízes primitivas módulo 13.

Por que as raízes primitivas são importantes na criptografia?

As raízes primitivas são fundamentais para o protocolo de troca de chaves Diffie-Hellman e para o sistema de criptografia ElGamal. Nesses protocolos criptográficos, uma raiz primitiva g módulo um grande primo p é usada como geradora. A segurança baseia-se na dificuldade do problema do logaritmo discreto: dado \(g^x \bmod p\), é computacionalmente difícil encontrar x.

Como você verifica se g é uma raiz primitiva módulo n?

Para verificar se g é uma raiz primitiva mod n: (1) Calcule \(\varphi(n)\). (2) Encontre todos os fatores primos \(p_1, p_2, \ldots, p_k\) de \(\varphi(n)\). (3) Verifique se \(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) para cada fator primo \(p_i\). Se todos os testes passarem, g é uma raiz primitiva. Isso é muito mais rápido do que calcular todas as potências de g.

Ferramentas Relacionadas