Como resolver de raízes primitivas

Resolvendo para raízes primitivas é uma habilidade útil em criptografia e teoria dos números. Um número, “g “, é uma raiz primitiva para um determinado número primo , ” p “, se g (mod p ) tem ordem módulo p -1. Isto significa que a lista de ” g ^ 1 mod p “, ” g ^ 2 mod p ” e até ” g ^ ( p – 1 ) mod p ” contém todos os números inteiros de 1 – ( p – 1 ) . Não há nenhum algoritmo conhecido para calcular eficientemente raízes primitivas . O método simples para o cálculo de raízes primitivas é tentar cada número possível de 2 até (p- 1). Instruções

1

Escolha um número primo , ” p “, como 5 . Um número primo não tem outros do que em si divisores e 1. , Por exemplo, 4 não é um número primo , porque ” 4/2 = 2 “; por isso tem 2 como um divisor

2

Calcular ” 2 ^ n mod p” para cada inteiro ” n” a partir de 1 – . (p- 1). Usando o exemplo , “p” é de 5 , de modo a calcular ” 2 ^ n mod 5″ para 1-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

Verifique se a lista de números contém todos os possíveis restos mod 5 . a lista 2, 4, 3 e 1 qualifica , então 2 é uma raiz primitiva módulo 5 . Se a lista tinha sido em vez de 2 , 1, 4 e 1 , que é para 4, então não seria uma raiz primitiva porque está faltando o número 3.

4

Repita o passo anterior para todos os inteiros com menos de 5 o número 3 também é uma raiz primitiva módulo 5, mas 4 não é.; então 2 e 3 são as raízes primitivas para 5 .