www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Krypto,Kodierungstheorie,Computeralgebra" - Pohlig-Hellmann-Algorithmus
Pohlig-Hellmann-Algorithmus < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Pohlig-Hellmann-Algorithmus: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 13:15 Mo 16.05.2011
Autor: Hanz

Hallo,
ich versuche mir gerade den Pohlig-Hellmann-Algorithmus anzueignen mittels dieses pdf's:

http://www.wi.uni-muenster.de/pi/lehre/ws0708/seminar/Abgaben/Diskrete%20Logarithmen.pdf

Auf der Seite 19 werden dort [mm] \alpha_0, \alpha_1 [/mm] und [mm] \alpha_2 [/mm] berechnet. Ich kann es aber nicht nachvollziehen, wie man darauf kommt...

Könnte mir jemand erklären, wie man auf [mm] \alpha_2 [/mm] = 1579 + 2017 [mm] \IZ [/mm] kommt?


Danke.





Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Pohlig-Hellmann-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:08 Di 17.05.2011
Autor: Hanz

Niemand eine Idee?   :(

Bezug
                
Bezug
Pohlig-Hellmann-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:15 Di 17.05.2011
Autor: felixf

Moin!

> Niemand eine Idee?   :(

Doch, schon, aber gerade nicht so viel Zeit. Und das PDF ist ein wenig verwirrend, so dass ich mich da etwas durchlesen muss um deine Frage beantworten zu koennen.

LG Felix




Bezug
                        
Bezug
Pohlig-Hellmann-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:03 Do 19.05.2011
Autor: Hanz

Hi, wäre echt nett, wenn du mir da weiterhelfen könntest.

Vllt. würde ja das hier helfen:

http://www.cs.uni-potsdam.de/ti/lehre/09ws-Kryptographie/slides/slides-5.3.pdf

(Hier die Folien 9-11) Handelt sich um dasselbe Beispiel, aber wie man diese [mm] a_i [/mm] bestimmt, will mir nicht einleuchten :<

Bezug
                                
Bezug
Pohlig-Hellmann-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:52 Do 19.05.2011
Autor: felixf

Moin!

> Hi, wäre echt nett, wenn du mir da weiterhelfen
> könntest.
>  
> Vllt. würde ja das hier helfen:
>  
> http://www.cs.uni-potsdam.de/ti/lehre/09ws-Kryptographie/slides/slides-5.3.pdf
>  
> (Hier die Folien 9-11) Handelt sich um dasselbe Beispiel,
> aber wie man diese [mm]a_i[/mm] bestimmt, will mir nicht einleuchten
> :<

Das Beispiel ist schonmal viel leserlicher.

Versuch das ganze doch mal anhand der Rechnung auf Folie 11 nachzuvollziehen. Wenn du dazu eine Frage hast, sag genau zu welchem Gleichheitszeichen du eine Frage hast und stell sie hier.

LG Felix





Bezug
                                        
Bezug
Pohlig-Hellmann-Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:28 Do 19.05.2011
Autor: Hanz

Der Schritt den ich da nicht verstehe, ist wie man die y berechnet (auf Folie 11).

Wie kommt man da auf: [mm] y_{2,2} [/mm] = [mm] 1579^4? [/mm]

Was muss ich genau rechnen, um auf die 1579 zu kommen?


Bezug
                                                
Bezug
Pohlig-Hellmann-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 11:34 Fr 20.05.2011
Autor: felixf

Moin!

> Der Schritt den ich da nicht verstehe, ist wie man die y
> berechnet (auf Folie 11).

Du suchst $x$ mit [mm] $5^x \equiv [/mm] 3 [mm] \pmod{2017}$. [/mm] Da die Gruppenordnung $2016 = [mm] 2^5 \cdot (3^2 \cdot [/mm] 7) = [mm] 2^5 \cdot [/mm] 63$ ist, musst du [mm] $5^{63}$ [/mm] und [mm] $3^{63}$ [/mm] modulo 2017 ausrechnen. Es ist [mm] $g_2 [/mm] = [mm] 5^{63} \mod [/mm] 2017 = 500$ und [mm] $y_2 [/mm] = [mm] 3^{63} \mod [/mm] 2017 = 913$ (Notation von Folie 9). (Dieses [mm] $y_2$ [/mm] ist nachher [mm] $y_{2,0}$.) [/mm]

Um jetzt [mm] $\log_5 [/mm] 3 [mm] \mod 2^5$ [/mm] auszurechnen, berechnet man erst [mm] $g_\ast [/mm] = [mm] 500^{2^{5 - 1}} \mod [/mm] 2017 = 2016$; dieses Element hat die Ordnung 2 (was nicht ueberraschend ist, da $2016 [mm] \equiv [/mm] -1 [mm] \pmod{2017}$) [/mm] in der multiplikativen Gruppe.

Wir schreiben [mm] $\log_5 [/mm] 3 [mm] \mod 2^5 [/mm] = [mm] x_{2,0} [/mm] + 2 [mm] x_{2,1} [/mm] + 4 [mm] x_{2,2} [/mm] + 8 [mm] x_{2,3} [/mm] + 16 [mm] x_{2,4}$. [/mm]

Angenommen, es sind nun [mm] $x_{2,0}, \dots, x_{2,k-1}$ [/mm] bestimmt. Nach der Formel auf Folie 10 gilt nun [mm] $y_{2,k} [/mm] = [mm] (y_2 \cdot g_2^{-\sum_{i
Fangen wir also mit $k = 0$ an. Es ist [mm] $y_{2,0} [/mm] = [mm] (y_2 \cdot g_2^0)^{2^{5 - 0 - 1}} [/mm] = [mm] y_2^{2^4} [/mm] = [mm] y_2^{16} [/mm] = [mm] 913^{16} \equiv [/mm] 1 [mm] \pmod{2017}$, [/mm] also haben wir das DLP [mm] $2016^{x_{2,0}} \equiv [/mm] 1 [mm] \pmod{2017}$. [/mm] Hier sieht man, dass [mm] $x_{2,0} [/mm] = 0$ sein muss.

Jetzt zu $k = 1$. Es ist [mm] $y_{2,1} [/mm] = [mm] (y_2 \cdot g_2^{-x_{2,0} \cdot 2^0})^{2^{5 - 1 - 1}} [/mm] = [mm] (y_2 \cdot 1)^{2^3} [/mm] = [mm] 913^8 \equiv [/mm] 2016 [mm] \pmod{2017}$. [/mm] Also haben wir das DLP [mm] $2016^{x_{2,1}} \equiv [/mm] 2016 [mm] \pmod{2017}$, [/mm] und somit ist [mm] $x_{2,1} [/mm] = 1$.

Zu $k = 2$: es ist [mm] $y_{2,2} [/mm] = [mm] (y_2 \cdot g_2^{-x_{2,0} - 2 x_{2,1}})^{2^{5 - 2 - 1}} [/mm] = [mm] (y_2 \cdot g_2^{-2})^{2^2} [/mm] = (913 [mm] \cdot 500^{-2})^4 \equiv [/mm] (913 [mm] \cdot 593^2)^4 \equiv 1579^4 \equiv [/mm] 2016 [mm] \pmod{2017}$ [/mm] (da [mm] $500^{-1} \equiv [/mm] 593 [mm] \pmod{2017}$). [/mm] Also haben wir das DLP [mm] $2016^{x_{2,2}} \equiv [/mm] 2016 [mm] \pmod{2017}$ [/mm] und somit wieder [mm] $x_{2,2} [/mm] = 1$.

Zu $k = 3$: es ist [mm] $y_{2,3} [/mm] = [mm] (y_2 \cdot g_2^{-x_{2,0} - 2 x_{2,1} - 4 x_{2,2}})^{2^{5 - 3 - 1}} [/mm] = [mm] (y_2 \cdot g_2^{-6})^{2^1} \equiv [/mm] (913 [mm] \cdot 593^6)^2 \equiv 1^2 [/mm] = 1 [mm] \pmod{2017}$. [/mm] Damit haben wir das DLP [mm] $2016^{x_{2,3}} \equiv [/mm] 1 [mm] \pmod{2017}$ [/mm] und somit [mm] $x_{2,3} [/mm] = 0$.

Fuer $k = 4$ haben wir dann [mm] $y_{2,4} [/mm] = [mm] (y_2 \cdot 2^{-6})^{2^0} \equiv [/mm] 1 [mm] \pmod{2017}$ [/mm] und mittels [mm] $2016^{x_{2,4}} \equiv [/mm] 1 [mm] \pmod{2017}$ [/mm] schliesslich [mm] $x_{2,4} [/mm] = 0$.

Also ist [mm] $\log_5 [/mm] 3 [mm] \mod 2^5 [/mm] = [mm] x_2 [/mm] = 6$.

Ich hoffe, das ist jetzt besser nachvollziehbar...

LG Felix


Bezug
                                                        
Bezug
Pohlig-Hellmann-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:42 Mo 23.05.2011
Autor: Hanz

Vielen Dank für die sehr ausführliche Antwort. Habe das Verfahren jetzt auch ganz verstanden.


DANKE!!!

Bezug
                                                        
Bezug
Pohlig-Hellmann-Algorithmus: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:40 Di 14.06.2011
Autor: Hanz

Hi,

mir ist gerade noch etwas aufgefallen, was ich im theoretischen nicht ganz nachvollziehen kann und zwar:

(handelt sich um das selbe pdf oben Seite 10/11)

Man reduziert doch die Gruppen auf Primzahlpotenzordnungen, warum aber rechnet man in den Rechnungen immer mod 2017 und nicht modulo die Primzahl?

Bezug
                                                                
Bezug
Pohlig-Hellmann-Algorithmus: Antwort
Status: (Antwort) fertig Status 
Datum: 23:22 Di 14.06.2011
Autor: felixf

Moin!

> mir ist gerade noch etwas aufgefallen, was ich im
> theoretischen nicht ganz nachvollziehen kann und zwar:
>  
> (handelt sich um das selbe pdf oben Seite 10/11)
>  
> Man reduziert doch die Gruppen auf Primzahlpotenzordnungen,
> warum aber rechnet man in den Rechnungen immer mod 2017 und
> nicht modulo die Primzahl?

Du rechnest in einer Untergruppe der urspruenglichen Gruppe.

Die urspruengliche Gruppe ist hier [mm] $(\IZ/2017\IZ)^\ast$. [/mm] Die Untergruppe hat Ordnung $p$.

Die Untergruppe ist jetzt nicht gleich [mm] $(\IZ/p\IZ)^\ast$ [/mm] (die haett auch nur $p - 1$ Elemente).

LG Felix




Bezug
        
Bezug
Pohlig-Hellmann-Algorithmus: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:20 Do 19.05.2011
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]