Prime Restklassengruppe

Zahlengruppe
(Weitergeleitet von Prime Restklasse)

Die prime Restklassengruppe ist die Gruppe der primen Restklassen bezüglich eines Moduls . Sie wird als oder notiert. Die primen Restklassen sind genau die multiplikativ invertierbaren Elemente im Restklassenring. Die primen Restklassengruppen sind daher endliche abelsche Gruppen bezüglich der Multiplikation. Sie spielen in der Kryptographie eine bedeutende Rolle.

Die Gruppe besteht aus den Restklassen , deren Elemente zu teilerfremd sind. Gleichwertig dazu muss für den Repräsentanten der Restklasse gelten, wobei ggT den größten gemeinsamen Teiler bezeichnet. Darauf weist die Bezeichnung „prime Restklasse“ hin, für teilerfremd sagt man auch relativ prim. Die Gruppenordnung von ist durch den Wert der eulerschen φ-Funktion gegeben.

Struktur

Bearbeiten

Bezeichnet   die  -Bewertung von   (die Vielfachheit des Primfaktors   in  ), ist also

 

die Primfaktorzerlegung von  , dann gilt:

 
 
oder mithilfe von   und der Schreibweise   für eine zyklische Gruppe ausgedrückt:
 

Die erste Isomorphieaussage (Zerlegung des Moduls   in seine Primfaktoren) folgt aus dem chinesischen Restsatz. Die zweite Isomorphieaussage (Struktur der primen Restklassengruppe modulo Primzahlpotenz) folgt aus der Existenz gewisser Primitivwurzeln[1] (siehe auch den zugehörigen Hauptartikel Primitivwurzel).

Beachte: Mit den Gruppen ohne hochgestelltes   sind die additiven Gruppen   etc. gemeint!

  ist genau dann zyklisch, wenn   gleich   oder   ist mit einer ungeraden Primzahl   und einer positiven Ganzzahl  . Genau dann existieren auch Primitivwurzeln modulo  , also Ganzzahlen  , deren Restklasse   ein Erzeuger von   ist.

Sonderfall: Modul ist Primzahl

Bearbeiten

Wenn   eine Primzahl ist, wird für den (genau dann) ausgebildeten Körper (engl. Field)   meist   geschrieben; es ist dann  ; insbesondere ist die Gruppenordnung  .

Berechnung der inversen Elemente

Bearbeiten

Zu jeder primen Restklasse   existiert eine prime Restklasse  , sodass gilt:

 

Die prime Restklasse   ist also das inverse Element zu   bezüglich der Multiplikation in der primen Restklassengruppe  . Ein Repräsentant von   lässt sich mit Hilfe des erweiterten euklidischen Algorithmus bestimmen. Der Algorithmus wird auf   und   angewendet und liefert ganze Zahlen   und  , die folgende Gleichung erfüllen:

 .

Daraus folgt  , das heißt,   ist ein Repräsentant der zu   multiplikativ inversen Restklasse  .

Literatur

Bearbeiten

Die Disquisitiones Arithmeticae wurden von Carl Friedrich Gauß auf Latein veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst alle seine Schriften zur Zahlentheorie:

  • Armin Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. 1. Auflage. Springer Verlag, 1996, Berlin Heidelberg New York. ISBN 3-540-58791-8.

Einzelnachweise

Bearbeiten
  1. A. Leutbecher: Zahlentheorie - Eine Einführung in die Algebra, S. 53–54.