Inhalt
Das Berechnen primitiver Wurzeln ist eine nützliche Fähigkeit in der Kryptographie und der Zahlentheorie. Eine Zahl "g" ist eine primitive Wurzel für eine gegebene Primzahl "p", wenn g mod p den Ordnungsmodul p-1 hat. Dies bedeutet, dass die Liste von "g1 mod p", "g2 mod p" bis "g (p-1) mod p" alle ganzen Zahlen von 1 bis (p-1) enthält. Es ist kein Algorithmus bekannt, um primitive Wurzeln effizient zu berechnen. Die einfachste Methode besteht darin, jede mögliche Zahl von 2 bis (p-1) auszuprobieren.
Anweisungen
-
Wählen Sie eine Primzahl "p" wie fünf. Eine Primzahl hat keine Divisoren außer sich und einer. Zum Beispiel ist vier keine Primzahl, weil "4/2 = 2" 2 als einer seiner Divisoren hat.
-
Berechne "2 ^ n mod p" für jede ganze Zahl "n" von 1 bis (p-1). Anhand des Beispiels ist "p" 5, dann berechnen Sie "2 ^ n mod 5" für "n" von 1 bis 4. Dies erzeugt die Liste:
2 ^ 1 = 2 mod 5 = 2 2 ^ 2 = 4 mod 5 = 4 2 ^ 3 = 8 mod 5 = 3 2 ^ 4 = 16 mod 5 = 1
-
Stellen Sie sicher, dass die Liste der Zahlen alle möglichen Spuren von fünf enthält. Liste 2, 4, 3 und 1 qualifiziert, also ist 2 eine primitive Wurzel mit Rest 5. Wenn stattdessen die Liste 2,1,4 und 1 wäre, was die Liste für 4 ist, dann wäre 4 nicht der Fall eine primitive Wurzel, weil die Nummer 3 in der Liste fehlt.
-
Wiederholen Sie den vorherigen Schritt für alle ganzen Zahlen unter fünf. Nummer drei ist auch eine primitive Wurzel von Rest fünf, aber vier nicht. dann sind zwei und fünf die primitiven wurzeln für fünf.