Primitivwurzeln und Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:09 Do 15.03.2007 | | Autor: | Qul-Q |
Hallo!
Ich schreibe immoment eine Facharbeit zu dem Thema Kryptographie (besonders das RSA-Verfahren) und da bin ich bei meinen Recherchen natürlich auch über den Diffie-Hellman-Schlüsselaustausch gestoßen.
Dabei wird eine Primzahl sowie eine Primitivwurzel benötigt.
Daher meine beiden Fragen:
1. Was ist überhaupt eine Primitivwurzel (ich hab schon überall nachgeguckt und nicht wirklich was gefunden, was ich verstanden hätte)
2. Wieso wird eine Primzahl benötigt, kann es nicht auch eine andere beliebige Zahl sein? (Eine primzahl wird auch bei dem RSA Verfahren benutzt)
Bei Frage 2 vermute ich, dass es etwas mit der Berechnung der Anzahl der Teilerfremden Zahlen zutun hat, wäre aber Nett, wenn mir das jemand genauer erklären könnte.
p.s. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:02 Fr 16.03.2007 | | Autor: | leduart |
Hallo Q
Die Frage ist mit deinem Vorwissen schwer zu beantworten.
Hast du schon mal was von Rechnungen "modulo" oder mod gehoert? man rechnet wie auf der Uhr, das ware mod 12. d.h. 9Uhr +8std gibt nicht 17 sondern 17-12=5
man schreibt dann 9+8=5 mod12
entsprechend mit anderen Zahlen also etwa mod 7: 6+6=5 mod 7
3+4=0mod7 usw 6*6=1mod7
du ziehst 7 solange ab, bis was unter 7 uebrig bleibt.
es gibt in dem sinn also bei 7 nur die Zahlen 1,2,3,4,5,6,7=0
mit manchen davon kann man jetzt durch Multiplikation alle anderen erzeugen. z.Bsp ist 3 so ne "primitive" Wurzel mod 7
denn [mm] 3^1=3, 3^2=2; 3^3=3^2*3=6; 3^4=(18)=4; 3^5=(12)=5;
[/mm]
[mm] 3^6=(15)=1
[/mm]
2 waere keine primitive Wurzel denn [mm] 2^1=2, 2^2=4, 2^3=1 [/mm] und mehr kriegt man nicht.
Man muss bei sowas Primzahlen nehmen, weil bei anderen Zahlen 0 rauskommen kann, wenn man 2 Zahlen miteinander multipl. die nicht 0 sind:
Beispiel mod12:
3*4=0mod12!
Diese Art der Rechnung musst du eigentlich verstehen, wenn du die Verschluesselung nach Diffie Hellmann verstehen willst.
(Das Thema gehoert zur sog. Gruppentheorie, die Zahlen mod Primzahlen bilden bei Addition UND Multiplikation eine Gruppe.
Frag nach ,was du nicht verstehst, dein Thema ist schwer.
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:56 Fr 16.03.2007 | | Autor: | Qul-Q |
vielen dank!
klar, modularer rest sagt mir was. Ich hatte nur keine ahnung was das mit den Primitivwurzeln zutun hatte.
Danke
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:09 Mo 19.03.2007 | | Autor: | Qul-Q |
das mit den primitivwurzeln versteh ich mittlerweile "einigermaßen" (was ja auch mein hauptproblem war)
ich hab zudem herausgefunden (![[]](/images/popup.gif) und zwar hier)
dass folgendes für primitiv wurzeln gilt:
0 [mm] \equiv (x^{M-1}-1) [/mm] mod M
aber nun zu meiner frage, gibt es eine art formel um primitiv wurzeln herauszufinden, oder muss man solange rumprobieren, bis man eine hat?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:21 Mo 19.03.2007 | | Autor: | leduart |
Hallo
Nein, soweit mir bekannt gibts keine formel, nur einige wie p-1 kann man gleich ausschliessen.
deine Formel heisst nix anderes, als ich schon erklaert hab: x primwurzel zu p folgt [mm] x^{p-1}=1 [/mm] modp denn aus a=1 folgt immer a-1=0
Gruss leduart
|
|
|
|
