Contenuto
Il calcolo delle radici primitive è un'abilità utile nella crittografia e nella teoria dei numeri. Un numero "g" è una radice primitiva per un dato numero primo "p" se g mod p ha il modulo ordine p-1. Ciò significa che l'elenco di "g1 mod p", "g2 mod p" a "g (p-1) mod p" contiene tutti gli interi da 1 a (p-1). Non esiste un algoritmo noto per calcolare efficientemente le radici primitive. Il metodo più semplice è provare ogni numero possibile da 2 a (p-1).
indicazioni
-
Scegli un numero primo, "p", come cinque. Un numero primo non ha divisori oltre se stesso e uno. Ad esempio, quattro non è un numero primo perché "4/2 = 2", ha 2 come uno dei suoi divisori.
-
Calcola "2 ^ n mod p" per ogni intero "n" da 1 a (p-1). Usando l'esempio, "p" è 5, quindi calcola "2 ^ n mod 5" per "n" da 1 a 4. Questo produce l'elenco:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Assicurati che l'elenco di numeri contenga tutte le tracce possibili di cinque. Lista 2, 4, 3 e 1 si qualifica, quindi 2 è una radice primitiva con resto 5. Se, invece, la lista fosse 2,1,4 e 1, che è la lista per 4, quindi 4 non sarebbe una radice primitiva perché manca il numero 3 dalla lista.
-
Ripeti il passaggio precedente per tutti gli interi meno di cinque. Il numero tre è anche una radice primitiva di riposo cinque, ma quattro non lo sono; allora due e cinque sono le radici primitive per cinque.