Logarithmus in nicht zyklischer Gruppe |
30.05.2013, 14:34 | Karamuto | Auf diesen Beitrag antworten » | ||
Logarithmus in nicht zyklischer Gruppe 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 >.< |
||||
30.05.2013, 15:08 | watcher | Auf diesen Beitrag antworten » | ||
Hallo Karamuto,
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 |
||||
30.05.2013, 15:33 | 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 |
||||
30.05.2013, 15:59 | 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 |
||||
30.05.2013, 16:06 | 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. |
||||
30.05.2013, 16:34 | 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? |
||||
Anzeige | ||||
|
||||
30.05.2013, 16:41 | 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? |
||||
30.05.2013, 16:46 | 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 |
||||
30.05.2013, 16:53 | watcher | Auf diesen Beitrag antworten » | ||
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? |
||||
30.05.2013, 16:57 | 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 |
||||
30.05.2013, 17:05 | watcher | Auf diesen Beitrag antworten » | ||
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. |
||||
31.05.2013, 00:29 | 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 |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|