Prime Restklassengruppe - LinkFang.de





Prime Restklassengruppe


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

Die Verknüpfung zweier primer Restklassen wird durch die Multiplikation der Elemente der Restklassen induziert.

[math](a + n \Z) \circ (b + n \Z) = (a \cdot b + n \Z)[/math]

In der Sprache der Ringtheorie ist die prime Restklassengruppe [math]\left((\Z /n\Z )^\times,\cdot\right)[/math] die Gruppe der invertierbaren Elemente in der multiplikativen Halbgruppe des Restklassenrings [math]\left({\Z /n\Z },+,\cdot\right)[/math].

Struktur

Bezeichnet [math]v_p[/math] die [math]p[/math]-Bewertung von [math]n[/math] (die Vielfachheit des Primfaktors [math]p[/math] in [math]n[/math]), ist also

[math]n=\prod_p p^{v_p}[/math]

die Primfaktorzerlegung von [math]n[/math], dann gilt:

[math](\Z/n\Z)^\times \cong \prod_p(\Z/p^{v_p}\Z)^\times[/math]
[math]\cong\begin{cases}\Z/2\Z \; \times \; \Z/2^{v_2-2}\Z \; \times \; \prod_{p \neq 2}\Z/(p-1)p^{v_p-1}\Z&\mathrm{falls}\ 4\mid n\\ \prod_p\Z/(p-1)p^{v_p-1}\Z&\mathrm{sonst}.\end{cases}[/math]

Die erste Isomorphieaussage (Zerlegung des Moduls [math]n[/math] 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 [math]\times[/math] sind die additiven Gruppen [math]\Z/(p-1)p^{v_p-1}\Z[/math] etc. gemeint!

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

Berechnung der inversen Elemente

Zu jeder primen Restklasse [math]a + n \Z[/math] existiert eine prime Restklasse [math]b + n \Z[/math], sodass gilt:

[math]ab \equiv 1 \pmod n[/math]

Die prime Restklassengruppe [math]b + n \Z[/math] ist also das inverse Element zu [math]a + n \Z[/math] bezüglich der Multiplikation in der primen Restklassengruppe [math]\Z_n^*[/math]. Ein Repräsentant von [math]b + n \Z[/math] lässt sich mit Hilfe des Erweiterten Euklidischen Algorithmus bestimmen. Der Algorithmus wird auf [math]a[/math] und [math]n[/math] angewendet und liefert ganze Zahlen [math]s[/math] und [math]t[/math], die folgende Gleichung erfüllen:

[math]ggT(a,n)= 1 = s \cdot a + t \cdot n [/math]

Daraus folgt [math] 1 \equiv sa \pmod n [/math]. [math]s[/math] ist also ein Repräsentant der zu [math]a + n \Z[/math] multiplikativ inversen Restklasse [math]b + n \Z[/math].

Literatur

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

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

Kategorien: Zahlentheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Prime Restklassengruppe (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.