Contente
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).
Instruções
-
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.
-
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
-
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.
-
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.