Como calcular raízes primitivas

Escrito por sean mann | Traduzido por franciele gobi
  • Compartilhar
  • Tweetar
  • Compartilhar
  • Pin
  • E-mail
Como calcular raízes primitivas
Um uso comum da aritmética modular é o relógio de ponteiro, que usa aritmética módulo 12 (Hemera Technologies/PhotoObjects.net/Getty Images)

Calcular raízes primitivas é uma habilidade útil em criptografia e teoria dos números. Um número "g" é uma raiz primitiva para um dado número primo "p" se g mod p possui módulo de ordem p-1. Isso significa que a lista de "gˆ1 mod p", "gˆ2 mod p" até "gˆ(p-1) mod p" contém todos os inteiros de 1 até (p-1). Não existe nenhum algoritmo conhecido para calcular raízes primitivas com eficiência. O método mais simples é tentar cada número possível de 2 até (p-1).

Nível de dificuldade:
Moderadamente fácil

Outras pessoas estão lendo

Instruções

  1. 1

    Escolha um número primo, "p", como cinco. Um número primo não possui divisores além de si mesmo e um. Por exemplo, quatro não é um número primo porque "4/2 = 2", ele possui 2 como um de seus divisores.

  2. 2

    Calcule "2^n mod p" para cada inteiro "n" de 1 até (p-1). Utilizando o exemplo, "p" é 5, então calcule "2^n mod 5" para "n" de 1 a 4. Isso produz a lista:

    2^1 = 2 mod 5 = 2 2^2 = 4 mod 5 = 4 2^3 = 8 mod 5 = 3 2^4 = 16 mod 5 = 1

  3. 3

    Verifique se a lista de números contém todos os possíveis restos de cinco. A lista 2, 4, 3 e 1 se qualifica, então 2 é uma raiz primitiva com resto 5. Se, ao invés disso, a lista fosse 2,1,4 e 1, que é a lista para 4, então 4 não seria uma raiz primitiva porque na lista falta o número 3.

  4. 4

    Repita o passo anterior para todos os inteiros menores que cinco. O número três também é uma raiz primitiva de resto cinco, mas quatro não é; então dois e cinco são as raízes primitivas para cinco.

Não perca

Filtro:
  • Geral
  • Artigos
  • Slides
  • Vídeos
Mostrar:
  • Mais relevantes
  • Mais lidos
  • Mais recentes

Nenhum artigo disponível

Nenhum slide disponível

Nenhum vídeo disponível