Περιεχόμενο
Ο υπολογισμός των πρωτόγονων ριζών είναι χρήσιμη δεξιότητα στην κρυπτογραφία και τη θεωρία αριθμών. Ένας αριθμός "g" είναι μια πρωτόγονη ρίζα για έναν δεδομένο prime αριθμό "p" αν το g mod p έχει συντελεστή παραγγελίας p-1. Αυτό σημαίνει ότι ο κατάλογος των "g1 mod p", "g2 mod p" σε "g (p-1) mod p" περιέχει όλους τους ακέραιους από 1 έως (p-1). Δεν υπάρχει γνωστός αλγόριθμος για τον αποτελεσματικό υπολογισμό των πρωτόγονων ριζών. Η απλούστερη μέθοδος είναι να δοκιμάσετε κάθε πιθανό αριθμό από 2 έως (p-1).
Οδηγίες
-
Επιλέξτε έναν prime αριθμό, "p", όπως πέντε. Ένας πρωταρχικός αριθμός δεν έχει διαιρετές πέρα από τον εαυτό του και ένα. Για παράδειγμα, τέσσερα δεν είναι ένας prime number επειδή "4/2 = 2", έχει 2 ως έναν από τους διαιρέτες.
-
Υπολογίστε "2 ^ n mod p" για κάθε ακέραιο "n" από 1 έως (p-1). Χρησιμοποιώντας το παράδειγμα, το "p" είναι 5, τότε υπολογίστε το "2 ^ n mod 5" για το "n" από 1 έως 4. Αυτό παράγει τη λίστα:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Βεβαιωθείτε ότι η λίστα αριθμών περιέχει όλα τα πιθανά ίχνη των πέντε. Οι λίστες 2, 4, 3 και 1 πληρούν τις προϋποθέσεις, οπότε 2 είναι μια πρωτόγονη ρίζα με το υπόλοιπο 5. Αν, αντίθετα, ο κατάλογος ήταν 2,1,4 και 1, ο οποίος είναι ο κατάλογος για 4, τότε 4 δεν θα ήταν μια πρωτόγονη ρίζα επειδή ο αριθμός 3 λείπει από τη λίστα.
-
Επαναλάβετε το προηγούμενο βήμα για όλους τους ακέραιους αριθμούς κάτω των πέντε. Ο τρίτος αριθμός είναι επίσης μια πρωτόγονη ρίζα της ανάπαυσης πέντε, αλλά τέσσερα δεν είναι? τότε δύο και πέντε είναι οι πρωτόγονες ρίζες για πέντε.