O que é uma raiz primitiva módulo n?

É um inteiro g tal que todo número coprimo com n pode ser escrito como alguma potência de g módulo n — g 'gera' todo o grupo multiplicativo módulo n.

Todo n tem uma raiz primitiva?

Não — raízes primitivas só existem para n = 1, 2, 4, pᵏ (uma potência prima ímpar), ou 2pᵏ. Para outros valores, como n = 8 ou n = 15, nenhuma raiz primitiva existe.

Como se testa se g é uma raiz primitiva?

Compute φ(n) e seus fatores primos distintos q₁, q₂, .... Então g é uma raiz primitiva se e somente se mdc(g, n) = 1 e g^(φ(n)/qᵢ) mod n ≠ 1 para cada fator primo qᵢ.

Por que esse teste funciona?

A ordem de g deve dividir φ(n) pelo teorema de Lagrange. Se a ordem de g fosse um divisor próprio de φ(n), ela dividiria φ(n)/q para algum fator primo q, fazendo g^(φ(n)/q) ≡ 1. Descartar isso para cada fator primo confirma que a ordem é exatamente φ(n).

A raiz primitiva é única?

Não — se g é uma raiz primitiva mod n, existem exatamente φ(φ(n)) raízes primitivas no total. Esta calculadora retorna a menor.

Quão grande pode ser o valor de n que esta calculadora consegue processar?

Esta calculadora suporta valores de n até 1.000.000, o que mantém tanto a fatoração de n quanto a busca pela raiz primitiva rápidas usando divisão de teste.

Onde as raízes primitivas são usadas na vida real?

São fundamentais para a troca de chaves Diffie-Hellman e o criptossistema ElGamal, ambos dependentes de um gerador público de um grande grupo multiplicativo de ordem prima.

Como isso se relaciona com a Calculadora da Função Totiente de Euler?

Encontrar raízes primitivas requer computar φ(n) e fatorá-lo — esta calculadora usa a mesma abordagem de fatoração que a Calculadora da Função Totiente de Euler do site como etapa central.

Calculadora de Raiz Primitiva — Encontre a Menor Raiz Primitiva Módulo n

Nossa Calculadora de Raiz Primitiva encontra a menor raiz primitiva módulo n — um inteiro g cujas potências g¹, g², g³, ... percorrem cada unidade módulo n antes de se repetir. Primeiro verifica se existe uma raiz primitiva (elas só existem para n = 1, 2, 4, pᵏ, ou 2pᵏ para um primo ímpar p), depois busca usando a função totiente de Euler e sua fatoração em primos para testar cada candidato eficientemente.

Resposta rápida

Uma raiz primitiva g mod n gera cada unidade módulo n por meio de suas potências. Insira n abaixo para encontrar a menor, com uma verificação automática de se existe alguma raiz primitiva.

Digite n, depois clique em Calcular.

Como usar Calculadora de Raiz Primitiva — Encontre um Gerador mod n

1
Insira um número inteiro positivo n (até 1.000.000).
2
Clique em 'Calcular' para encontrar a menor raiz primitiva módulo n, se existir alguma.
3
Revise φ(n) e os fatores primos de φ(n) usados na verificação.

Por que usar Calculadora de Raiz Primitiva — Encontre um Gerador mod n?

Uma raiz primitiva módulo n é um gerador do grupo de inteiros coprimos com n sob multiplicação: suas potências sucessivas produzem cada unidade módulo n exatamente uma vez antes de voltar a 1, em exatamente φ(n) passos. Nem todo n tem uma — raízes primitivas só existem para n = 1, 2, 4, uma potência prima ímpar pᵏ, ou o dobro de uma potência prima ímpar 2pᵏ, um resultado clássico em teoria dos números. Esta calculadora verifica essa condição primeiro, depois verifica eficientemente cada candidato g testando g^(φ(n)/q) mod n para cada fator primo q de φ(n) — g é uma raiz primitiva exatamente quando nenhum desses testes é igual a 1.

Perguntas frequentes

Ferramentas relacionadas

Calculadora da Função Totiente de Euler — φ(n) Online

Calcule a função totiente de Euler φ(n) — a contagem de inteiros de 1 a n coprimos com n — via fatoração em primos. Calculadora gratuita que mostra a fatoração completa.

Calculadora de Exponenciação Modular — bᵉ mod m Rápido Online

Calcule bᵉ mod m para expoentes arbitrariamente grandes usando exponenciação rápida por quadrado-e-multiplicação. Calculadora gratuita com precisão BigInt, essencial para criptografia.

Calculadora de Inverso Multiplicativo Modular — Resolva ax ≡ 1 (mod m)

Encontre o inverso multiplicativo modular de a módulo m usando o algoritmo de Euclides estendido. Calculadora gratuita com precisão BigInt e verificação de existência.

Calculadora de Ordem em Teoria de Grupos — Ordem de Elemento em ℤₙ Online

Encontre a ordem de um elemento em (ℤₙ, +) ou (ℤ/nℤ)ˣ, com uma verificação de divisibilidade do teorema de Lagrange mostrada como etapa. Calculadora gratuita, resultados instantâneos.