¿Cómo resolver para raíces primitivas

Despejando raíces primitivas es una habilidad útil en la criptografía y teoría de números. Un número, "g ", es una raíz primitiva para un número dado de primera, "p ", si g (mod p ) tiene orden módulo p - 1 . Esto significa que la lista de "g ^ 1 mod p ", "g ^ 2 mod p" y hasta "g ^ ( p- 1 ) mod p " contiene todos los números enteros de 1 - (p - 1 ) . No existe un algoritmo conocido para calcular de manera eficiente raíces primitivas . El método sencillo para el cálculo de raíces primitivas es tratar cada número posible de 2 hasta ( p - 1 ) . Instrucciones Matemáticas 1

Elija un número primo , "p ", tales como 5 . Un número primo no tiene divisores distintos de uno mismo y 1. Por ejemplo , 4 no es un número primo , porque " 4/2 = 2 "; por lo que tiene 2 como divisor
2

Calcular " 2 ^ n mod p" para cada número entero "n " de 1 - . ( p- 1 ) . Usando el ejemplo , "p" es 5 , por lo que se calcula " 2 ^ n mod 5" para 1-4. Esto produce la lista:

2 ^ 1 = 2 mod 5 = 2 Foto

2 ^ 2 = 4 mod 5 = 4 personas

2 ^ 3 = 8 mod 5 = 3

2 ^ 4 = 16 mod 5 = 1
3

Compruebe si la lista de números contiene todos los posibles restos de mod 5 . la lista 2 , 4 , 3 ​​y 1 califica , por lo que 2 es una raíz primitiva módulo 5 . Si la lista en lugar había sido 2 , 1, 4 y 1, que es para 4 personas, entonces no sería una raíz primitiva porque falta el número 3 .
Página 4

Repita el paso anterior para todos los enteros menores de 5 el número 3 es también una raíz primitiva módulo 5 , pero 4 no lo es.; así que 2 y 3 son las raíces primitivas de 5 .