HÜ 4 b Generator Z 47

neoatlant
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 14. Okt 2010 22:16

HÜ 4 b Generator Z 47

Beitrag von neoatlant »

Hi,

Gibt es ein Verfahren das man anwenden kann um den Generator zu bestimmen, oder geht es nur durch trial & error ?

Gruß

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: HÜ 4 b Generator Z 47

Beitrag von R_Egert »

Naja schau dir vielleicht mal an wie die Gruppenübung 4 bearbeitet wurde. Dort sollte man ja einen Generator bestimmen ;)

mfg Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

neoatlant
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 14. Okt 2010 22:16

Re: HÜ 4 b Generator Z 47

Beitrag von neoatlant »

leider war ich in dieser Übung nicht anwesend, und einen Lösungsvorschlag gibt's nicht :(

ElGamal
Nichts ist wie es scheint
Beiträge: 23
Registriert: 19. Dez 2011 20:56

Re: HÜ 4 b Generator Z 47

Beitrag von ElGamal »

neoatlant hat geschrieben:leider war ich in dieser Übung nicht anwesend, und einen Lösungsvorschlag gibt's nicht :(
Schau dir doch mal das Übungsblatt an :wink:

neoatlant
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 14. Okt 2010 22:16

Re: HÜ 4 b Generator Z 47

Beitrag von neoatlant »

kann mir denn jemand verraten wie das also gelöst wurde, ein generator hab ich gefunden, aber zeigen dass es einer ist
hab ich von der Übungsblatt nicht ganz verstanden

Danke Im Voraus

Steven
Kernelcompilierer
Kernelcompilierer
Beiträge: 425
Registriert: 2. Sep 2008 10:00
Wohnort: Frankfurt am Main

Re: HÜ 4 b Generator Z 47

Beitrag von Steven »

Komm' mal in meine Sprechstunde. Heute um 15:00 Uhr in S202 / E102.

Benutzeravatar
Domac
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 160
Registriert: 4. Okt 2010 16:11

Re: HÜ 4 b Generator Z 47

Beitrag von Domac »

Kann man nicht auch \(x = p - 1 = 47 - 1 = 46\) wählen... dann würde ja mit dem Satz von Fermat gelten, dass jedes \(g \in G\) ein Generator wäre. Das wäre zumindest nach den Richtlinien bzgl. der vierten Übung konform... und so wie ich das hier sehe, haben wir das damals auch so umgesetzt und hatten in der Übung 4 den Generator g = 2. Jedoch bin ich nachträglich von dieser Tatsache verwirrt. Kann mich da vielleicht jemand aufklären... ich steh aufm Schlauch? :? Danke!

Gruß,
domac
Extend my dropbox space (here).
Thanks!

Benutzeravatar
McLovin
Erstie
Erstie
Beiträge: 13
Registriert: 26. Sep 2010 23:43
Wohnort: Mainz

Re: HÜ 4 b Generator Z 47

Beitrag von McLovin »

Bist du dir sicher, dass 2 ein Generator der Gruppe ist? Mit der 2 kann man nur eine Untergruppe mit 23 Elementen erzeugen, denn für den Teiler 23 von 46 gilt:

2^23 mod 47 = 1

Schau am Besten nochmal das 4. Übungsblatt an und nutze die Hinweise. Noch ein Tipp: Überlege dir alle Teiler von \(\phi(47)\)

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: HÜ 4 b Generator Z 47

Beitrag von philipp_m »

Also mit beiden mir bekannten Kriterien (dem aus der Übung und einem allgemeinen) konnte ich mit einem selbst geschriebenen Java Programm keinen Generator kleiner 100.000 finden, also entweder meine Kriterien sind falsch oder hier ist etwas faul :O

Benutzeravatar
McLovin
Erstie
Erstie
Beiträge: 13
Registriert: 26. Sep 2010 23:43
Wohnort: Mainz

Re: HÜ 4 b Generator Z 47

Beitrag von McLovin »

Du brauchst kein Java Programm, um einen Generator herauszufinden.

Die Ordnung dieser Gruppe ist doch 46. Falls für eine ganze positive Zahl x g^x mod 47 = 1 ist, muss x die Ordnung der Gruppe teilen. Also ist
\(x \in \lbrace 1, 2, 23, 46\rbrace\)

Der zweite Satz besagt, dass die Ordnung dieser Gruppe die kleinste positive Zahl ist, für die g^x mod 47 = 1.

Also musst du einen Generator g finden, für den gilt, dass g^x mod 47 = 1 genau dann, wenn x = 46 aber z.B. g^2 mod 47 ≠ 1.

Ich habe es ja fast schon verraten, wie man vorgehen muss :-)

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: HÜ 4 b Generator Z 47

Beitrag von philipp_m »

McLovin hat geschrieben:Du brauchst kein Java Programm, um einen Generator herauszufinden.

Die Ordnung dieser Gruppe ist doch 46. Falls für eine ganze positive Zahl x g^x mod 47 = 1 ist, muss x die Ordnung der Gruppe teilen. Also ist
\(x \in \lbrace 1, 2, 23, 46\rbrace\)

Der zweite Satz besagt, dass die Ordnung dieser Gruppe die kleinste positive Zahl ist, für die g^x mod 47 = 1.

Also musst du einen Generator g finden, für den gilt, dass g^x mod 47 = 1 genau dann, wenn x = 46 aber z.B. g^2 mod 47 ≠ 1.

Ich habe es ja fast schon verraten, wie man vorgehen muss :-)
Das hatte ich schon alles verstanden, aber danke, dass du bestätigt hast, dass ich richtig gesucht habe :)
Dass g<47 wusste ich bereits, aber selbst bei nur wenigen Zahlen finde ich, geht es mit einem 5 Minuten Java Programm schneller als da von Hand durchzuprobieren - habe inzwischen auch das Ergebnis, hatte in meinem Programm nur einen dummen Tippfehler, durch den ich bis x=46 nach g^x=1 mod 47 gesucht habe anstatt bis x=45.
Genügt es, die Bedingungen anzugeben, die gelten, oder muss man auch noch vorrechnen, dass sie gelten? Weiß das irgendwer?

Antworten

Zurück zu „Archiv“