In diesem Artikel soll das Konzept der diskreten Logarithmen, wie sie z.B. von Karl Hoecken in seiner Arbeit
Die Rechenmaschinen von Pascal bis zur Gegenwart (http://rechnerlexikon.de/files/HoeckMult.pdf) zur Konstruktion eines Multiplikationsmechanismus vorgeschlagen und von Schumacher in seinem Rechenschieber umgesetzt wurden, dargestellt werden.
|
1 Addition und Multiplikation in endlichen Körpern
Wenn p eine Primzahl ist, dann kann man in der Menge M = {0, 1, ... p-1} fast so, wie man es in der Menge der ganzen Zahlen gewohnt ist, addieren und multiplizieren. Man addiert bzw. multipliziert einfach zwei Zahlen aus dieser Menge, und wenn das Ergebnis nicht in der Menge liegt (weil es zu groß geworden ist), dann zieht man so oft p ab, bis man ein Ergebnis erhält, das wieder in dieser Menge liegt. Statt hinreichend oft abzuziehen, kann man auch einfach den Divisionsrest bei Division durch p bilden, was auf dasselbe herauskommt.Wenn p keine Primzahl ist, dann funktioniert es nicht so einwandfrei, darum interessiert uns im Folgenden nur der Fall, wo p eine Primzahl ist.
1.1 Beispiele zur Addition und Multiplikation in endlichen Körpern
Wir betrachten als Beispiel p=7. 7 ist eine Primzahl. Die Menge, mit der wir rechnen wollen, hat 7 Elemente: M = { 0, 1, 2, 3, 4, 5, 6}.Nun führen wir einige Additionen aus:
2 + 2 ist 4. Das liegt wieder in M, damit ist diese Addition erledigt.
Schwieriger wird es, wenn wir 5 + 4 rechnen. Wenn wir alle ganzen Zahlen zur Verfügung hätten, dann käme jetzt 9 heraus, 9 liegt aber nicht in M, also teilen wir durch p=7 und behalten den Divisionsrest. Der ist 2, also: 5 + 4 = 2.
Enstprechend erhalten wir 5 + 5 = 3, etc. Bei der Multiplikation verfahren wir analog und erhalten z.B.: 3 * 4 = 5.
Da M in unserem Beispiel nur 7 Elemente enthält, lassen sich alle möglichen Additionen und Multiplikationen in den folgenden beiden Tabellen darstellen:
| Addition | Multiplikation | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
1.2 Notation
Mathematiker bezeichnen eine endliche Menge, in der man "vernünftig" addieren und multiplizieren kann, als endlichen Körper und verwenden für den endlichen Körper mit p Elementen die Bezeichnung \mathbb{Z} / p \mathbb{Z} .
2 Potenzrechnung in endlichen Körpern
So, wie man von ganzen Zahlen höhere Potenzen ausrechnen kann, so kann man das auch in dem endlichen Körper \mathbb{Z} / p \mathbb{Z}. Man multipliziert die Basis so oft mit sich selbst, wie der Exponent angibt (und achtet darauf, dass man den endlichen Körper nicht verlässt).
2.1 Beispiel 1 zur Potenzrechnung
Wir wählen wieder, wie oben p=7, und damit \mathbb{Z} / 7 \mathbb{Z}, den endlichen Körper mit 7 Elementen. Darin wollen wir nun von der Zahl 4 höhere Potenzen berechnen.\begin{matrix} 4^0 & = & & & & & 1 \\ 4^1 & = & 4 * 4^0 & = & 4 * 1 & = & 4 \\ 4^2 & = & 4 * 4^1 & = & 4 * 4 & = & 2 \\ 4^3 & = & 4 * 4^2 & = & 4 * 2 & = & 1 \\ 4^4 & = & 4 * 4^3 & = & 4 * 1 & = & 4 \\ 4^5 & = & 4 * 4^4 & = & 4 * 4 & = & 2 \\ 4^6 & = & 4 * 4^5 & = & 4 * 2 & = & 1 \\ \end{matrix}
2.2 Beispiel 2 zur Potenzrechnung
Berechnung der Potenzen von 3 in \mathbb{Z} / 7 \mathbb{Z} :\begin{matrix} 3^0 & = & & & & & 1 \\ 3^1 & = & 3 * 3^0 & = & 3 * 1 & = & 3 \\ 3^2 & = & 3 * 3^1 & = & 3 * 3 & = & 2 \\ 3^3 & = & 3 * 3^2 & = & 3 * 2 & = & 6 \\ 3^4 & = & 3 * 3^3 & = & 3 * 6 & = & 4 \\ 3^5 & = & 3 * 3^4 & = & 3 * 4 & = & 5 \\ 3^6 & = & 3 * 3^5 & = & 3 * 5 & = & 1 \\ \end{matrix}
Bei den beiden Beispielen fällt auf, dass in M = \mathbb{Z} / 7 \mathbb{Z} die Potenzen von 3 alle Werte von M ohne Null annehmen, während die Potenzen von 4 nur die Werte 1, 2, und 4 haben können.
Das führt uns zu dem Begriff Primitivwurzel.
3 Primitivwurzeln
Eine Zahl Zahl g in \mathbb{Z} / p \mathbb{Z} heißt Primitivwurzel modulo p, wenn g^t für 0 \leq t \leq p-2 modulo p alle Werte von 1 bis p-1 annimmt.Es ist also zum Beispiel 3 eine Primitivwurzel modulo 7, während 4 keine ist.
Zu einer Primzahl p gibt es immer mindestens eine Primitivwurzel modulo p.
| Die Primzahl | hat die Primitivwurzeln |
| 2 | 1 |
| 3 | 2 |
| 5 | 2, 3 |
| 7 | 3, 5 |
| 11 | 2, 6, 7, 8 |
4 Die Diskrete Exponentialfunktion
Ist p eine Primzahl und g eine Primitivwurzel modulo p, so bezeichnet man die folgende Funktion in \mathbb{Z} / p \mathbb{Z} als Diskrete Exponentialfunktion zur Basis g:Exp_g: \left\{ \begin{matrix} \mathbb{Z} / p \mathbb{Z}& \longrightarrow & (\mathbb{Z} / p \mathbb{Z})^* \\ x & \longmapsto & g^x \mod{} p \end{matrix} \right.
Da g eine Primitivwurzel modulo p ist, werden von der Diskreten Exponentialfunktion alle Werte in (\mathbb{Z} / p \mathbb{Z})* angenommen.
4.1 Beispiele zur Diskreten Exponentialfunktion
Wir wählen p = 11, das heißt, wir rechnen in \mathbb{Z} / 11 \mathbb{Z}.Als Basis g der Diskreten Exponentialfunktion wählen wir die Primitivwurzel 2.
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Exp_2(x) = 2^x | 1 | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | 6 | 1 |
5 Diskrete Logarithmen
Da von der Diskreten Exponentialfunktion alle Werte in (\mathbb{Z} / p \mathbb{Z})^* angenommen werden, existiert eine Umkehrfunktion. Diese wird als Diskreter Logarithmus bezeichnet.Log_g: \left\{ \begin{matrix} (\mathbb{Z} / p \mathbb{Z})^* & \longrightarrow & \mathbb{Z} / p \mathbb{Z} \\ \end{matrix} \right.
5.1 Beispiele zum Diskreten Logarithmus
Abermals sei p = 11 und g= 2:
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Log_2(x) | 0 | 1 | 8 | 2 | 4 | 9 | 7 | 3 | 6 | 5 |
6 Anwendungen
Diskrete Logarithmen haben, wie der natürliche Logarithmus auch, die Eigenschaft, dass Log_g(a*b) = Log_g(a) + Log_g(b). Das heißt, man kann mit ihrer Hilfe Multiplikationsaufgaben auf Additionsaufgaben zurückführen. Man beachte, dass, im Gegensatz zum Natürlichen Logarithmus Diskrete Logarithmen nicht monoton sein müssen.
6.1 Der Multiplikationsmechanismus von Hoecken
Karl Hoecken sucht in seiner Arbeit Die Rechenmaschinen von Pascal bis zur Gegenwart (http://rechnerlexikon.de/files/HoeckMult.pdf) nach Möglichkeiten, die Multiplikation von einstelligen Zahlen auf die Addition von Strecken zurückzuführen. Die Abbildung von Zahlen auf ihren Natürlichen Logarithmus, wie es ja z.B. beim Rechenschieber gemacht wird, hält er für ungeeignet, da sich z.B. die Natürlichen Logarithmen der beiden möglichen Produkte 63 und 64 nur um sechs Tausendstel unterscheiden. Skaliert man das zu einer technisch handhabbaren Größe, so gelangt man bei dem Produkt 81 in Bereiche von mehr als einem Meter.
Hoecken schlägt nun vor, statt der Natürlichen Logarithmen diskrete zu verwenden. Die Zahlen p und g müssten dazu derart gewählt werden, dass der Diskrete Logarithmus für jedes der 36 möglichen Produkte einstelliger Zahlen einen anderen Wert annimmt. Die dafür erforderlichen Zahlen erscheinen ihm für eine mechanische Umsetzung aber immer noch zu groß, so dass er, noch allgemeiner, eine Abbildung Ind der 36 möglichen Produkte einstelliger Zahlen in eine Teilmenge der natürlichen Zahlen (er nennt sie "Indices") sucht, derart dass
- alle Werte sich unterscheiden
- Die Multiplikation einstelliger Zahlen auf Addition ihrer Indices zurückgeführt werden kann: Ind(a*b) = Ind(a) + Ind(b).