J
muhi schrieb:
Wieso werden gerade diese Zahlentypen ausgewählt? (Primitivwurzeln etc) bzw warum gerade prime Restklassen? (bei Diffie-Hellman)
Weil es damit halt funktioniert. Restklassen sind überaus beliebt, weil man darüber ziemlich viel weiß. Mit denen kann man relativ gut rechnen, trotzdem ist für manche Operationen eben nicht bekannt wie man sie schnell rückgängig machen kann. (Und immer wenn etwas hat von dem man nicht weiß wie man's schnell lösen kann, dann baut man ein krypto-system draus ;)).
Prime Restklassen haben den Vorteil, dass sie auch noch invertierbar sind. Das gibt noch mehr Struktur.
plus: was ist eine Primitivwurzel?
x ist d-te wurzel von a, wenn x^d = a. x ist primitive d-te wurzel, wenn zusätzlich x^i != a für 1<=i<d. Wenn man also wirklich hoch d nehmen muß und nicht schon vorher das gewünschte element rauskommt.
Betrachte zum Beispiel die 4. Wurzeln aus 1 (achtung wurzel im algebraischen sinne, d.h. nullstellen von x^4-1). Da gibt's genau 4 Stück: 1,-1,i,-i.
Für jede davon ist die 4. Potenz 1. Aber es gilt sogar schon 1^1 =1 und (-1)^2 = 1, die sind also nicht primitiv. Du kannst ja mal nachprüfen, dass i und (-i) primitiv sind. Wenn man mal eine primitive Wurzel d-te Wurzel von 1 hat, nennen wir sie x, dann kriegt man alle anderen Wurzeln von 1 als x1,x2,x3,...,xd.
Und mit denen wiederum kriegt man, wenn man eine Wurzel aus a hat dann auch alle Wurzeln von a. Deshalb sind primitive Wurzeln recht praktisch.