Contenido
Calcular las raíces primitivas es una habilidad útil en la encriptación y la teoría de los números. Un número "g" es una raíz primitiva para un dado número primo "p" si g mod p tiene módulo de orden p-1. Esto significa que la lista de "g1 mod p", "g2 mod p" hasta "g (p-1) mod p" contiene todos los enteros de 1 a (p-1). No existe ningún algoritmo conocido para calcular las raíces primitivas con eficiencia. El método más simple es intentar cada número posible de 2 hasta (p-1).
instrucciones
-
Seleccione un número primo, "p", como cinco. Un número primo no tiene divisores más allá de uno mismo y uno. Por ejemplo, cuatro no es un número primo porque "4/2 = 2", tiene 2 como uno de sus divisores.
-
Calcule "2 ^ n mod p" para cada entero "n" de 1 hasta (p-1). Utilizando el ejemplo, "p" es 5, entonces calcule "2 ^ n mod 5" a "n" de 1 a 4. Esto produce la lista:
2 ^ 1 = 2 mod 2 ^ 5 = 2 2 = 4 mod 5 = 4 = 2 ^ 3 = 8 mod 5 3 2 ^ 4 = 16 mod 5 = 1
-
Compruebe que la lista de números contiene todos los posibles restos de cinco. La lista 2, 4, 3 y 1 se califica, entonces 2 es una raíz primitiva con resto 5. Si, en lugar de eso, la lista fuera 2,1,4 y 1, que es la lista para 4, entonces 4 no sería una raíz primitiva porque en la lista falta el número 3.
-
Repita el paso anterior para todos los enteros menores de cinco. El número tres también es una raíz primitiva de cinco, pero cuatro no es; entonces dos y cinco son las raíces primitivas para cinco.