Prime Restklassengruppe

Die prime Restklassengruppe ist die Gruppe der primen Restklassen bezüglich eines Moduls . Sie wird als $(\mathbb{Z } /n\mathbb{Z } )^{\times }$ oder $\mathbb{Z } _{n}^{*}$ 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 $a+n\mathbb{Z }$ , deren Elemente zu teilerfremd sind. Gleichwertig dazu muss für den Repräsentanten der Restklasse $\operatorname {ggT}(a,n)=1$ 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 $\mathbb{Z } _{n}^{*}$ ist durch den Wert $\varphi(n)$ der eulerschen φ-Funktion gegeben.

Struktur

Bezeichnet $v_{p}$ die -Bewertung von (die Vielfachheit des Primfaktors in ), ist also

$n=\prod _{p}p^{{v_{p}}}$

die Primfaktorzerlegung von , dann gilt:

$(\mathbb{Z } /n\mathbb{Z } )^{\times }\cong \prod _{p}(\mathbb{Z } /p^{{v_{p}}}\mathbb{Z } )^{\times }$

${}\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}}$

oder mithilfe von $\varphi$ und der Schreibweise $C_{n}$ für eine zyklische Gruppe ausgedrückt:

${}\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}}$

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 (siehe auch den zugehörigen Hauptartikel Primitivwurzel).

Beachte: Mit den Gruppen ohne hochgestelltes $\times$ sind die additiven Gruppen $\mathbb{Z } /(p-1)p^{{v_{p}-1}}\mathbb{Z }$ etc. gemeint!

$(\mathbb{Z } /n\mathbb{Z } )^{\times }$ ist genau dann zyklisch, wenn gleich $1,2,4,p^{r}$ oder $2p^{r}$ ist mit einer ungeraden Primzahl und einer positiven Ganzzahl . Genau dann existieren auch Primitivwurzeln modulo , also Ganzzahlen , deren Restklasse $a+n\mathbb{Z }$ ein Erzeuger von $(\mathbb{Z } /n\mathbb{Z } )^{\times }$ ist.

Berechnung der inversen Elemente

Zu jeder primen Restklasse $a+n\mathbb{Z }$ existiert eine prime Restklasse $b+n\mathbb{Z }$ , sodass gilt:

$ab\equiv 1{\pmod n}$

Die prime Restklasse $b+n\mathbb{Z }$ ist also das inverse Element zu $a+n\mathbb{Z }$ bezüglich der Multiplikation in der primen Restklassengruppe $\mathbb{Z } _{n}^{*}$ . Ein Repräsentant von $b+n\mathbb{Z }$ 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:

$\operatorname {ggT} (a,n)=1=s\cdot a+t\cdot n$ .

Daraus folgt $1\equiv sa{\pmod n}$ , das heißt, ist ein Repräsentant der zu $a+n\mathbb{Z }$ multiplikativ inversen Restklasse $b+n\mathbb{Z }$ .

Basierend auf einem Artikel in:

Wikipedia.de