diskreter Logarithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Betrachte die Gruppe [mm] G=\IF_{31}^x
[/mm]
g=[3]
Dies ist ein Erzeuger von G.
Wir setzen [mm] g_2:=g^{15}, g_3:=g^{10} [/mm] und [mm] g_5:=g^6
[/mm]
Die Logarithmentafel für [mm] g_5 [/mm] is:
s [mm] g_5^s
[/mm]
1 [16]
2 [8]
3 [4]
4 [2]
5 [1]
[mm] L:=Log_g([2])
[/mm]
a) Berechne von hand [mm] [2]^6 [/mm] und die Restklasse von L modulo 5.
b) Lege entsprechende Logarithmustafeln für [mm] g_2 [/mm] und [mm] g_3 [/mm] an (Tipp: [mm] g_3=[5]
[/mm]
c)Berechne von Hand die Restklasse von L modulo 2 und modulo 3
d) Bestimmen sie L mit dem Chinesischen Restsatz,
das Vorgehen soll wie beim Algorithmus von Silver-Pohling-Hellmann sein.
Es soll von hand gerechnet werden und Rechenvorgänge in kleinen gedanklichen Schritten mit angegeben werden. |
Ich habe leider gar nicht richtig verstanden wie man mit diesem Algorithmus umgeht und auch in der Vorlesung wurde dazu nicht sehr viel erwähnt.
Könnt ihr mir das vielleicht nochmal erklären? Und Tipps geben wie ich diese Aufgabe lösen kann?
Ich weiß auch nicht, wie die angegeben Logarithementafel zustande kommt.
MfG
Mathegirl
|
|
| |
|
moin Mathegirl,
Zu aller erst muss ich sagen: Den Algorithmus von Silver-Pohling-Hellmann kenn ich persönlich nicht.
Da du den ja scheinbar benutzen sollst lass ich die Frage auch mal halb offen.
Ich kann dir aber den Rest beantworten:
Die Logarithmustafel kommt durch einfaches Berechnen der Werte (mod 31) zustande.
Ich hoffe du weißt, wie mit Restklassen oder Kongruenzen gerechnet wird?
Dafür berechnen wir erstmal:
[mm] $g_5 [/mm] = [mm] g^6 [/mm] = [mm] 3^6 [/mm] = [mm] 27^2 \equiv (-4)^2 \equiv [/mm] 16$ (mod 31)
Somit ist [mm] $g_5^1$ [/mm] offensichtlich gleich 16.
Nun werden schlicht die Potenzen von 16 (jeweils modulo 31) betrachtet und beim Ausrechnen ergeben sich eben die angegeben Werte.
Zum Lösen der Aufgabe:
Wie gesagt kenne ich den Algorithmus nicht, aber die Aufgaben lassen sich auch ganz gut ohne lösen (meiner Meinung nach), also falls das nur ein Hinweis war...
a) [mm] 2^6 [/mm] (mod 31) dürftest du berechnet kriegen.
Für L stellt sich die Frage: [mm] $3^k \equiv [/mm] 2$ (mod 31), ermittle $k$.
Da 3 ein Erzeuger sein soll kannst du davon ausgehen, dass es nur ein $k$ in der Menge [mm] $\{ 1,\ldots,30\}$ [/mm] dafür gibt.
Mit dem Wissen, dass [mm] $g_5^4 \equiv [/mm] 2$ und dass [mm] $g_5 [/mm] = [mm] g^6$ [/mm] ist dürftest du das $L$ berechnen können (und zwar explizit, nicht nur mod 5).
b) Hier gehst du so vor wie ich es oben am Beispiel von [mm] $g_5$ [/mm] beschrieben hab:
Erstmal das $g$ berechnen, dann die Potenzen, das ganze jeweils mod 31 betrachten.
c) Wenn du das $L$ in a) explizit bestimmt hast dürfte das kein Problem sein.
d) Hier wird wohl davon ausgegangen, dass du $L$ noch nicht explizit hattest.
Dann kannst du es aber mit dem CRS leicht bestimmen, da $2*3*5=30$, 2,3,5 teilerfremd und $L$ eindeutig mod 30 ist.
Auch hier gibt es eine ganze Reihe Tricks, aber dazu müsste man erstmal wissen, was du schon kannst.
Alles in allem bin ich persönlich der Meinung es ist leichter das ganze von Hand zu berechnen als mit dem Algorithmus.
Da es allerdings so scheint als solltest du den lernen lasse ich die Frage wie gesagt halb offen, vielleicht findet sich ja ein Experte und Verfechter des Algorithmus.
lg
Schadow
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:09 Sa 21.01.2012 | | Autor: | felixf |
Moin,
> Alles in allem bin ich persönlich der Meinung es ist
> leichter das ganze von Hand zu berechnen als mit dem
> Algorithmus.
bei solch kleinen Werten schon. Sobald die Werte groesser werden, insbesondere der Modulus, spart man sich damit jedoch schon einiges an Arbeit.
Ein solch kleines Beispiel dient halt dazu, sich den Algorithmus von Hand anschauen zu koennen, wie er funktioniert. Beispiele, ab wann er wesentlich effizienter ist, moechte man halt nicht mehr von Hand rechnen...
> Da es allerdings so scheint als solltest du den lernen
> lasse ich die Frage wie gesagt halb offen, vielleicht
> findet sich ja ein Experte und Verfechter des Algorithmus.
Ich mag den Algorithmus 
Viel zum Algorithmus muss man hier aber nicht sagen. Die Teilaufgaben sagen ja genau was man tun muss, um mit dem Algorithmus das DLP in diesem Fall zu loesen. Es ist sozusagen eine Schritt-fuer-Schritt-Anleitung.
LG Felix
|
|
|
| |
|
Danke für eure beiden Antworten!!
Wie Schadowmaster mir das mit der Logarithmentafel gezeigt hat, wie kann ich dass mit Silver Pohling-Algorithmus zeigen? Und wie berechne ich g? Es wurde mir zwar aufgezeigt, aber wie wähle ich die Potenzen? Wie nutze ich den Algorithmus von Pohling-Silver dafür?
Felix, kannst du mir das noch einmal genauer erklären anhand der Aufgabe? In der VL wurde dazu nicht viel gesagt, ich hab ein Skript, aber auch da ist es nicht richtig erklärt.
Das mit den Restklassen berechnen habe ich noch nicht verstanden, also Teilaufgabe c) und d).
Wie soll ich L mit dem Chinesischen Restsatz berechnen?
Über Hilfe und geduldige Erklärunge wäre ich sehr dankbar!
MfG
Mathegirl
|
|
|
| |
|
Hallo,
kann mir jemand helfen diese Aufgabe mit dem geforderten Logarithmus zu lösen?
Irgendwie verstehe ich die teilaufgabe c und d nicht.
Und ich weiß nicht wie man genau das g bestimmt.
MfG
Mathegirl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Di 24.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:20 Mo 23.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:20 Mo 23.01.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
