Calculadora de raiz primitiva

Digite um módulo n para encontrar sua menor raiz primitiva.

Como usar

  1. Insira os valores necessários nos campos.
  2. Clique em “Calcular” para ver o resultado.
  3. Copie ou compartilhe o resultado com o botão “Compartilhar”.

Sobre esta calculadora

Um número g é uma raiz primitiva módulo n se suas potências — g¹, g², g³ e assim por diante — percorrem todos os números coprimos com n antes de se repetir, o que significa que o menor expoente k para o qual g^k ≡ 1 (mod n) é exatamente φ(n), a função totiente de Euler. Em outras palavras, uma única raiz primitiva gera sozinha todo o grupo multiplicativo módulo n. As raízes primitivas não existem para todo módulo: a teoria dos números clássica (desde Gauss) mostra que elas existem apenas quando n é 1 (trivialmente), 2, 4, uma potência de um primo ímpar ou o dobro de uma potência de um primo ímpar.

As raízes primitivas são uma ferramenta de trabalho na criptografia, e não apenas uma curiosidade: a troca de chaves de Diffie–Hellman e o criptossistema ElGamal se apoiam na dificuldade do problema do logaritmo discreto em um grupo gerado por uma raiz primitiva, e as transformadas teóricas dos números usadas na multiplicação rápida e exata de polinômios (relevantes para alguns esquemas criptográficos e de correção de erros modernos) também dependem de encontrar raízes primitivas adequadas de um módulo.

Informe um módulo inteiro n de 2 a 100.000 e esta calculadora encontra a sua menor raiz primitiva, junto com φ(n) e o número de raízes primitivas. Se não existir raiz primitiva para esse n, ela não devolve resultado.

Isto foi útil?

Pode escolher até 3 reações.

Comentários

  • Seja o primeiro a comentar.

Calculadoras populares

Todas as calculadoras