Gleichung lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:48 Di 10.05.2011 | | Autor: | katrin10 |
| Aufgabe | | Finde ein x zwischen 0 und 16 mit der Eigenschaft [mm] 3^x \equiv [/mm] 15 (mod 17). |
Hallo,
durch Ausprobieren habe ich herausgefunden, dass die Zahl 6 eine Lösung ist. Allerdings weiß ich nicht genau, wie ich dies rechnerisch zeigen kann. Zum Lösen von linearen diophantischen Gleichungen benutzt man den euklidischen Algorithmus, allerdings ist meine Gleichung nicht linear und mit der ggt-Berechnung von 3 und 17 kam ich auch nicht weiter.
Für einen Tipp wäre ich sehr dankbar.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:19 Di 10.05.2011 | | Autor: | rainerS |
Hallo Katrin!
> Finde ein x zwischen 0 und 16 mit der Eigenschaft [mm]3^x \equiv 15 \pmod{17}[/mm].
> Hallo,
> durch Ausprobieren habe ich herausgefunden, dass die Zahl 6
> eine Lösung ist. Allerdings weiß ich nicht genau, wie ich
> dies rechnerisch zeigen kann. Zum Lösen von linearen
> diophantischen Gleichungen benutzt man den euklidischen
> Algorithmus, allerdings ist meine Gleichung nicht linear
> und mit der ggt-Berechnung von 3 und 17 kam ich auch nicht
> weiter.
> Für einen Tipp wäre ich sehr dankbar.
Es gibt tatsächlich keine einfache Methode, dieses x, den sogenannten ![[]](/images/popup.gif) diskreten Logarithmus, auszurechnen. Eine einfache Lösung dieses Problems würde eine ganze Reihe wichtiger kryptografischer Methoden unsicher machen.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:22 Di 10.05.2011 | | Autor: | katrin10 |
Vielen Dank für die schnelle Antwort.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:30 Di 10.05.2011 | | Autor: | abakus |
> Finde ein x zwischen 0 und 16 mit der Eigenschaft [mm]3^x \equiv[/mm]
> 15 (mod 17).
> Hallo,
> durch Ausprobieren habe ich herausgefunden, dass die Zahl 6
> eine Lösung ist. Allerdings weiß ich nicht genau, wie ich
> dies rechnerisch zeigen kann. Zum Lösen von linearen
> diophantischen Gleichungen benutzt man den euklidischen
> Algorithmus, allerdings ist meine Gleichung nicht linear
> und mit der ggt-Berechnung von 3 und 17 kam ich auch nicht
> weiter.
> Für einen Tipp wäre ich sehr dankbar.
>
Hallo,
da 3 und 17 teilerfremd sind, kommen von [mm] 3^1 [/mm] bis [mm] 3^{16} [/mm] alle möglichen Reste von 1 bis 16 (nicht in dieser Reihenfolge) jeweils genau einmal vor.
Es ist einfach etwas Fleißarbeit in einem überschaubaren Rahmen.
Gruß Abakus
|
|
|
|
