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
Bezeichnet
die
-Bewertung von
(die Vielfachheit des Primfaktors
in
), ist also
![{\displaystyle n=\prod _{p}p^{v_{p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9e62d6b546cc85272d13819094f2dde2b407148)
die Primfaktorzerlegung von
, dann gilt:
![{\displaystyle {}\cong {\begin{cases}\mathbb {Z} /2\mathbb {Z} \;\times \;\mathbb {Z} /2^{v_{2}-2}\mathbb {Z} \;\times \;\prod _{p\neq 2}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {falls} \ 8\mid n\\\prod _{p}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {sonst} .\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e390d9108915aa57cf835700e73592f373d3d80)
- oder mithilfe von
und der Schreibweise
für eine zyklische Gruppe ausgedrückt: ![{\displaystyle {}\cong {\begin{cases}C_{2}\;\times \;C_{2^{v_{2}-2}}\;\times \;\prod _{p\neq 2}C_{\varphi (p^{v_{p}})}&\mathrm {falls} \ 8\mid n\\\prod _{p}C_{\varphi (p^{v_{p}})}&\mathrm {sonst} .\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0864489e63898b96358b764231720ec9c494423)
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
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
Zu jeder primen Restklasse
existiert eine prime Restklasse
, sodass gilt:
![{\displaystyle ab\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20396c04a7e4cf73d06934d7848620af9252de9f)
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
Die Disquisitiones Arithmeticae wurden von Carl Friedrich Gauß auf Latein veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst alle seine Schriften zur Zahlentheorie:
- Carl Friedrich Gauß: Untersuchungen über höhere Arithmetik (deutsche Übersetzung), Original: Leipzig 1801.
- Armin Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. 1. Auflage. Springer Verlag, 1996, Berlin Heidelberg New York. ISBN 3-540-58791-8.
Einzelnachweise
- ↑ A. Leutbecher: Zahlentheorie - Eine Einführung in die Algebra, S. 53–54.