[Pagina principale]

Rechnerlexikon

Die große Enzyklopädie des mechanischen Rechnens

3.93.74.227 | Log in | Aiuto

  DE  EN  FR  IT 
Pagina principale
Tutte le pagine
Ultime modifiche

Versione stampabile
Discussione !!!

Articolo
Immagine
Brevetto



Pagine speciali

Diskrete Logarithmen


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 zur Konstruktion eines Multiplikationsmechanismus vorgeschlagen und von Schumacher in seinem Rechenschieber umgesetzt wurden, dargestellt werden.

Indice

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
+ 0123456
00123456
11234560
22345601
33456012
44560123
55601234
66012345
  
* 0123456
00000000
10123456
20246135
30362514
40415263
40531642
40654321

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 Primzahlhat die Primitivwurzeln
21
32
52, 3
73, 5
112, 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 012345678910
Exp_2(x) = 2^x 124851097361

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 12345678910
Log_2(x) 0182497365

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 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

Er stellt schließlich merere solcher Abbildungen vor.

6.2 Der Rechenschieber von Schumacher

Schumacher beschreibt in Schumacher 1909 einen Rechenschieber, der wie andere Rechenschieber auch, die Multiplikation auf die Addition von Logarithmen zurückführt. Im Gegensatz zu herkömmlichen Rechenschiebern, die sich des Natürlichen Logarithmus bedienen, verwendet der Schumacher Rechenschieber Diskrete Logarithmen in \mathbb{Z} / 101 \mathbb{Z}.

In base alla licenza d'uso è permesso citare testualmente parti di rechnerlexikon.de purché se ne citi la fonte.