Diskrete Logarithmus berechnen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:56 So 10.11.2013 | | Autor: | mathstat |
| Aufgabe | | Sei N = 21495809. Löse den diskreten Logarithmus Problem [mm] 7^x=14750571 [/mm] in [mm] Z_n. [/mm] (Ohne Brute-Force) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich habe schon verschiedene Algorithmus ausprobiert, aber mein Rechner (verwende Mathematica) stürzt immer ab.
Wie kann ich das Problem am effizientesten lösen?
Ich will keine Musterlösung sondern nur ein Tipp, diese Aufgabe zu lösen, so dass ich ein explizites "x" bekomme.
Wäre froh um eure Hilfe!
Danke!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:11 So 10.11.2013 | | Autor: | reverend |
Hallo mathstat, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Sei N = 21495809. Löse den diskreten Logarithmus Problem
> [mm]7^x=14750571[/mm] in [mm]Z_n.[/mm] (Ohne Brute-Force)
ohne brute force? Dann müsstet Ihr dazu etwas gehabt haben. Auf die wenigen nützlichen Algorithmen kommt man m.E. nicht so leicht selbst, wenn überhaupt.
> Ich habe schon verschiedene Algorithmus ausprobiert,
Welche?
> aber
> mein Rechner (verwende Mathematica) stürzt immer ab.
>
> Wie kann ich das Problem am effizientesten lösen?
Das wüsste ich auch gern.
> Ich will keine Musterlösung sondern nur ein Tipp, diese
> Aufgabe zu lösen, so dass ich ein explizites "x" bekomme.
Dass N prim ist, hast Du wahrscheinlich schon überprüft.
Die brute-force-Lösung (zur Kontrolle) ist übrigens $x=1312$.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:22 So 10.11.2013 | | Autor: | mathstat |
Das ist es ja. Wir wissen dass 14750571=3*11*443*1009 ist und dass N prim ist.
Wir kennen nur die zwei Rechengesetze [mm] log(a^b) [/mm] = b*log(a) und log(a*b) = log(a) + log(b). Jeweils noch modulo N.
Wir haben den naiven Verfahren und den Pohlig-Hellmann Verfahren ausprobiert. Aber das Programm stürzt immer ab.
Wir sind am verzweifeln.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:57 So 10.11.2013 | | Autor: | felixf |
Moin!
> Das ist es ja. Wir wissen dass 14750571=3*11*443*1009 ist
> und dass N prim ist.
Die Faktorisierung von $14750571$ ist recht egal. Interessanter ist die von $N - 1$.
> Wir kennen nur die zwei Rechengesetze [mm]log(a^b)[/mm] = b*log(a)
> und log(a*b) = log(a) + log(b). Jeweils noch modulo N.
Immerhin.
> Wir haben den naiven Verfahren und den Pohlig-Hellmann
> Verfahren ausprobiert. Aber das Programm stürzt immer ab.
Das liegt aber wohl an deinem Programm, nicht an den Algorithmen selber. Pohlig-Hellman ist hier eine sehr gute Wahl (wenn du dir die Faktorisierung von $N - 1$ anschaust).
Warum deine Implementation abstuerzt kann ich nur vermuten, aber mir faellt da ein sehr guter Kandidat ein: kann es sein, dass du [mm] $a^b \bmod [/mm] N$ so ausrechnest, indem du zuerst [mm] $a^b$ [/mm] berechnest (als ganze Zahl) und dann das Ergebnis modulo $N$ rechnest? Das ist eine sehr, sehr, sehr schlechte Idee.
(In Mathematica verwende dafuer die PowerMod-Funktion.)
LG Felix
|
|
|
| |
|
Eine effektive Berechnung geht im Allgemeinen nicht. Glücklicherweise!!!
Der baby-step giant-step alias Shank's Algorithmus funktioniert bei mir auf die Werte angewendet prima.
Mir würde noch (ungetestet) der Pollard's rho Algorithmus einfallen.
Insgesamt ist das alles Bruteforce. Wenn es doch auch cleveres Bruteforce ist.
|
|
|
|
