www.wikidata.de-de.nina.az

Prime Restklassengruppe Die prime Restklassengruppe ist die Gruppe der primen Restklassen bezüglich eines Moduls n displ

Prime Restklassengruppe

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:

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 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die prime Restklassengruppe ist die Gruppe der primen Restklassen bezuglich eines Moduls n displaystyle n Sie wird als Z n Z displaystyle mathbb Z n mathbb Z times oder Z n displaystyle mathbb Z n notiert Die primen Restklassen sind genau die multiplikativ invertierbaren Elemente im Restklassenring Die primen Restklassengruppen sind daher endliche abelsche Gruppen bezuglich der Multiplikation Sie spielen in der Kryptographie eine bedeutende Rolle Die Gruppe besteht aus den Restklassen a n Z displaystyle a n mathbb Z deren Elemente zu n displaystyle n teilerfremd sind Gleichwertig dazu muss fur den Reprasentanten a displaystyle a der Restklasse ggT a n 1 displaystyle operatorname ggT a n 1 gelten wobei ggT den grossten gemeinsamen Teiler bezeichnet Darauf weist die Bezeichnung prime Restklasse hin fur teilerfremd sagt man auch relativ prim Die Gruppenordnung von Z n displaystyle mathbb Z n ist durch den Wert f n displaystyle varphi n der eulerschen f Funktion gegeben Inhaltsverzeichnis 1 Struktur 2 Sonderfall Modul ist Primzahl 3 Berechnung der inversen Elemente 4 Literatur 5 EinzelnachweiseStruktur BearbeitenBezeichnet v p displaystyle v p nbsp die p displaystyle p nbsp Bewertung von n displaystyle n nbsp die Vielfachheit des Primfaktors p displaystyle p nbsp in n displaystyle n nbsp ist also n p p v p displaystyle n prod p p v p nbsp die Primfaktorzerlegung von n displaystyle n nbsp dann gilt Z n Z p Z p v p Z displaystyle mathbb Z n mathbb Z times cong prod p mathbb Z p v p mathbb Z times nbsp Z 2 Z Z 2 v 2 2 Z p 2 Z p 1 p v p 1 Z f a l l s 8 n p Z p 1 p v p 1 Z s o n s t 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 amp mathrm falls 8 mid n prod p mathbb Z p 1 p v p 1 mathbb Z amp mathrm sonst end cases nbsp oder mithilfe von f displaystyle varphi nbsp und der Schreibweise C n displaystyle C n nbsp fur eine zyklische Gruppe ausgedruckt C 2 C 2 v 2 2 p 2 C f p v p f a l l s 8 n p C f p v p s o n s t displaystyle cong begin cases C 2 times C 2 v 2 2 times prod p neq 2 C varphi p v p amp mathrm falls 8 mid n prod p C varphi p v p amp mathrm sonst end cases nbsp dd Die erste Isomorphieaussage Zerlegung des Moduls n displaystyle n nbsp 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 zugehorigen Hauptartikel Primitivwurzel Beachte Mit den Gruppen ohne hochgestelltes displaystyle times nbsp sind die additiven Gruppen Z p 1 p v p 1 Z displaystyle mathbb Z p 1 p v p 1 mathbb Z nbsp etc gemeint Z n Z displaystyle mathbb Z n mathbb Z times nbsp ist genau dann zyklisch wenn n displaystyle n nbsp gleich 1 2 4 p r displaystyle 1 2 4 p r nbsp oder 2 p r displaystyle 2p r nbsp ist mit einer ungeraden Primzahl p displaystyle p nbsp und einer positiven Ganzzahl r displaystyle r nbsp Genau dann existieren auch Primitivwurzeln modulo n displaystyle n nbsp also Ganzzahlen a displaystyle a nbsp deren Restklasse a n Z displaystyle a n mathbb Z nbsp ein Erzeuger von Z n Z displaystyle mathbb Z n mathbb Z times nbsp ist Sonderfall Modul ist Primzahl BearbeitenWenn n p displaystyle n p nbsp eine Primzahl ist wird fur den genau dann ausgebildeten Korper engl Field Z p Z displaystyle mathbb Z p mathbb Z nbsp meist F p displaystyle mathbb F p nbsp geschrieben es ist dann F p F p 0 displaystyle mathbb F p times mathbb F p setminus bar 0 nbsp insbesondere ist die Gruppenordnung F p f p p 1 displaystyle mathbb F p times varphi p p 1 nbsp Berechnung der inversen Elemente BearbeitenZu jeder primen Restklasse a n Z displaystyle a n mathbb Z nbsp existiert eine prime Restklasse b n Z displaystyle b n mathbb Z nbsp sodass gilt a b 1 mod n displaystyle ab equiv 1 pmod n nbsp Die prime Restklasse b n Z displaystyle b n mathbb Z nbsp ist also das inverse Element zu a n Z displaystyle a n mathbb Z nbsp bezuglich der Multiplikation in der primen Restklassengruppe Z n displaystyle mathbb Z n nbsp Ein Reprasentant von b n Z displaystyle b n mathbb Z nbsp lasst sich mit Hilfe des erweiterten euklidischen Algorithmus bestimmen Der Algorithmus wird auf a displaystyle a nbsp und n displaystyle n nbsp angewendet und liefert ganze Zahlen s displaystyle s nbsp und t displaystyle t nbsp die folgende Gleichung erfullen ggT a n 1 s a t n displaystyle operatorname ggT a n 1 s cdot a t cdot n nbsp Daraus folgt 1 s a mod n displaystyle 1 equiv sa pmod n nbsp das heisst s displaystyle s nbsp ist ein Reprasentant der zu a n Z displaystyle a n mathbb Z nbsp multiplikativ inversen Restklasse b n Z displaystyle b n mathbb Z nbsp Literatur BearbeitenDie Disquisitiones Arithmeticae wurden von Carl Friedrich Gauss auf Latein veroffentlicht Die zeitgenossische deutsche Ubersetzung umfasst alle seine Schriften zur Zahlentheorie Carl Friedrich Gauss Untersuchungen uber hohere Arithmetik deutsche Ubersetzung Original Leipzig 1801 Armin Leutbecher Zahlentheorie Eine Einfuhrung in die Algebra 1 Auflage Springer Verlag 1996 Berlin Heidelberg New York ISBN 3 540 58791 8 Einzelnachweise Bearbeiten A Leutbecher Zahlentheorie Eine Einfuhrung in die Algebra S 53 54 Abgerufen von https de wikipedia org w index php title Prime Restklassengruppe amp oldid 225144478