Diskreter Logarithmus |
| 10.12.2017, 23:33 | Hahais | Auf diesen Beitrag antworten » | ||
| Diskreter Logarithmus Hallo in einem Buch steht das der Diskrete Logarithmus von 3 zur Basis 5 durch ausprobieren gleich 1030 ist.... meine frage ist wie kann man sowas durch ausprobieren rauskriegen ? Achja IN MODULO 2017 Meine Ideen: Der diskrete Log von 5 zur basis 2 in modulo 11 ist 4 leicht durch ausprobieren: 2^4=16 16:11= 1 Also 5 mod 11 |
||||
| 10.12.2017, 23:47 | sibelius84 | Auf diesen Beitrag antworten » | ||
Hi,
Quelle: https://de.wikipedia.org/wiki/Diskreter_Logarithmus Ich meine sogar gelesen zu haben, dass das DL-Problem NP-vollständig ist, bin mir hier aber nicht mehr sicher. Effiziente Algorithmen sind hier jedenfalls Mangelware. Eine evtl. noch am ehesten vertretbare Alternative ist der sog. "Babystep-Giantstep-Algorithmus". LG sibelius84 |
||||
| 11.12.2017, 00:09 | Hahais | Auf diesen Beitrag antworten » | ||
Was heißt das denn nun. 
Im Buch Stand das wirklich so 
Ich weiß nicht wie man das durch ausprobieren rausbekommt... |
||||
| 11.12.2017, 00:16 | Hahaid | Auf diesen Beitrag antworten » | ||
Guck |
||||
| 11.12.2017, 00:22 | sibelius84 | Auf diesen Beitrag antworten » | ||
Sorry, aber es fällt mir gerade echt schwer, die Frage "Wie bekommt man das durch Ausprobieren raus?" zu beantworten. Wenn ich "durch Ausprobieren" sage, bist du vermutlich unzufrieden. edit: alle möglichen Zahlen nacheinander einsetzen und rechnen, rechnen, rechnen, bis beim fünften Versuch oder so zufällig mal das Ergebnis rauskommt, was du haben willst. |
||||
| 11.12.2017, 07:51 | Hahais | Auf diesen Beitrag antworten » | ||
Da steht ja das x= 1030 ist.. kann ich dann daraus folgern das gilt : 5^1030 = 3 mod 2017 ? dann muss ich ja in die gleichung 5^x=3 so oft eine Zahl einsetzen bis eine Zahl raus kommt. Wobei 5^1030 nicht mal im taschen darstellbar isr |
||||
| Anzeige | ||||
|
|
||||
| 11.12.2017, 11:04 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ok, also dann die noch ausführlichere Probieranleitung: Berechne rekursiv , und zwar über sowie Iteration . In jedem Iterationsschritt überprüfst du dabei, ob Wert 3 oder Wert 1 erreicht wurde. Trifft man zuerst auf Wert mit dann , dann hat die Gleichung keine Lösung und 5 ist zudem gar nicht primitive Wurzel mod 2017 (wollen wir mal nicht annehmen, dass dieser Fall hier eintritt). Andernfalls gelangt man zu und das zugehörige ist der gesuchte diskrete Logarithmus. Mit einem kleinen Skript (in welcher Programmiersprache auch immer) sollte das rasch erledigt sein. 1 5 25 125 625 1108 1506 ... |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
