Logarithmus in nicht zyklischer Gruppe

Neue Frage »

Karamuto Auf diesen Beitrag antworten »
Logarithmus in nicht zyklischer Gruppe
Hallo Matheboardler,

ich habe ein Problem mit der Berechnung des Diskreten Logarithmus in einer nicht unitären Gruppe.

Bzw der Berechnung der Lösungsmenge von

Es wurde zuvor bereits gezeigt, dass die Ordnung besitzt was der Ordnung von entspricht.

Nun stehe ich vor dem Problem das ich für Anwendung des Babystep-Gianstep Algorithmus eine Zyklische Gruppe benötige und die 2 in dieser Gruppe Primitivwurzel sein muss.

Habe leider keinen Ansatz wie ich hier rangehen muss >.<
watcher Auf diesen Beitrag antworten »

Hallo Karamuto,

Zitat:
Es wurde zuvor bereits gezeigt, dass die Ordnung besitzt was der Ordnung von entspricht.

Du meinst mit die Gruppe der Einheiten modulo 1961?
Diese Gruppe ist nicht zyklisch, die Ordnung von 2 kann also auch nicht die Gruppenordnung sein.

Damit so ein x überhaupt existiert muss aber 1950 in der von 2 erzeugten Untergruppe sein.
Auf die Untergruppe kann man GSBS loslassen.

P.S. Was meinst du mit unitäre Gruppe? Wohl nicht das oder?
https://de.wikipedia.org/wiki/Unit%C3%A4re_Gruppe
Karamuto Auf diesen Beitrag antworten »

zum ps: habe nirgendwo das wort unitär erwähnt ^^

zum vorigen: ja mir ist auch gerade aufgefallen das die ordnung 468 ist was das ganze schon wesentlich vereinfacht, mach mich dann erstmal ans rechnen bis vlt nachher
Karamuto Auf diesen Beitrag antworten »

okay läuft nicht so einfach wie erwartet x_X

ich meine herauszufinden ob 1950 in der von 2 aufgespannten UG liegt scheint mir auch nicht einfach wie es zunächst scheint, schon alleine weil ich gar nicht weiß wie ich in dieser UG den BSGS benutzen soll, tut mir leid aber weder in Vorlesung noch in Übung wurde es für fälle besprochen wo man keine zyklische Gruppe vorliegen hat x.x
watcher Auf diesen Beitrag antworten »

Zu zeigen, dass 1950 in der von 2 erzeugten Untergruppe ist, ist im Wesentlichen das gleiche wie den Logarithmus zu berechnen. Daher: Gehe davon aus, dass sie drin ist.
Liefert der Algorithmus kein Ergebnis, liegt 1950 nicht in der Untergruppe, d.h. es gibt kein so ein x.

Du rechnest in genauso wie in der großen Gruppe, es ist ja die selbe Multiplikation. Und sämtliche Rechenoperationen führen dich nicht aus der Untergruppe raus.

Also nochmal: Du hast eine zyklische Gruppe vorliegen.
Karamuto Auf diesen Beitrag antworten »

puh, dankeschön hätte ich mich beim ersten versuch vom BSGS nicht total verrechnet, dann hätte ich es warscheinlich schon vorher im 13. Schritt rausgehabt, vielen dank.

Habe aber nun noch eine 2. Frage, wie berechnet man den diskreten logarithmus in einem Polynomring bzw Restklassenkörper?
 
 
watcher Auf diesen Beitrag antworten »

Da kannst du auch so wie hier vorgehen.
Es gibt aber kein allgemeingültiges schnelles Verfahren um diskrete Logarithmen zu bestimmen.
Stecken konkrete Bsp. hinter den Fragen?
Karamuto Auf diesen Beitrag antworten »

ja meine konkrete Aufgabe ist:

mod , wobei

hierbei bin ich doch ein wenig verwirrt ^^

BSGS geht hier nicht da ich ja keine Wurzel ziehen kann so ohne weiteres
watcher Auf diesen Beitrag antworten »

Zitat:
mod , wobei

Steht das so in der Aufgabenstellung?
Das mod 9 macht für mich hier keinerlei Sinn.
Ist hier vielleicht die Gleichheit von Elementen von gemeint?
Karamuto Auf diesen Beitrag antworten »

naja das mod 9 steht ansich so nicht in der Aufgabe, aber da ich keine Ahnung habe wie man den Strich über Zahlen hier in Latex macht muss ich immer schaun wie ich das hier aufschreibe.

Genau genomm müsste da mod X^2+1 stehen denke ich

edit: okay jetzt hab ichs

watcher Auf diesen Beitrag antworten »

Zitat:
Genau genomm müsste da mod X^2+1 stehen denke ich

Also der Fall aus meiner letzten Zeile.

Mich dir klar dass ist.
Deine Schreibweise lässt vermuten, dass du fälschlicherweise mit identifiziert.

Möglichkeit 1:
Du nimmst 1+X als erzeugendes Element von (bzw. der davon erzeugten Untergruppe) und machst GSBS. (Warum ist die Gruppe zyklisch?)

Möglichkeit 2:
Brute-Force für alle t. Das ist hier wohl die schnellere Variante, da du z.B. 1+X nicht invertieren musst.
Karamuto Auf diesen Beitrag antworten »

joa try and error hats dann gebracht, das das polynom rechts auch noch das inverse zu x+1 war ist irgendwie dämlich :P

danke nochmal für die hilfe
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »