Einführung

Die modulare Arithmetik (oder „Rechnen mit Uhren“, bzw. auch „Rechnen mit Resten“ genannt) wurde erstmals von Carl Friedrich von Gauß entwickelt. Viele Mathematiker halten Carl Friedrich von Gauß für den größten Mathematiker aller Zeiten. Ich könnte viel über die Vita des „Fürsten der Mathematik“ (so wurde er zu Lebzeiten genannt) erzählen, aber ich denke, dass eine Anekdote aus seiner Kindheit ihn sehr gut beschreibt:

Gauß war neun Jahre alt als sein Mathematiklehrer den Schülern die Aufgabe gab, alle Zahlen von 1 bis 100 zu addieren. Dem kleinen Gauß war dies wohl eine viel zu stupide Aufgabe und deshalb bildete er die Summe so, dass er 50 Paare mit der 101 multiplizierte (1+100=101, 2+99=101, 3+98=101 und da macht man 50-mal) und 5050 als Ergebnis bekam. Er legte sein Resultat auf den Tisch und sagte angeblich „Ligget se!“ (Plattdeutsch für „Hier liegt es“). Sein Lehrer Begriff sofort, dass dieser kleine Junge vor ihm „nicht von dieser Welt sein konnte“ und förderte sein Talent, so dass Gauß das Gymnasium besuchen konnte.

Doch kommen wir zur modularen Arithmetik zurück. Die modulare Arithmetik beschreibt das Rechnen mit Zahlen. Und zwar so, wie diese auch heutzutage in Rechnern angewendet wird. Kein Algorithmus und keine Verschlüsselung können heutzutage ohne modulare Arithmetik auskommen. Sie ist das Gerüst wie wir Menschen und Maschinen mit Zahlen rechnen und offenbaren etwas etwas sehr Fundamentales in der „Natur“ der Mathematik.

In diesem Blogartikel werde ich nicht in die Beweise eintauchen, sondern einen praktischen Zugang zu dieser Art des Rechnens geben und erklären, wie diese in Python implementiert ist.

Die Modulare Arithmetik wird auch „Kongruenz“ genannt. Der Begriff wurde noch vor Gauß vom Mathematiker Christian Goldbach verwendete, jedoch hat er sich nicht so tief damit beschäftigt (ein wenig wie wir hier in diesem Blog 😉 ). Erwähnen muss ich aber auch, dass sich noch viel früher (1247) der chinesische Mathematiker Qin Jiushao (秦九韶) ebenfalls mit Kongruenzen beschäftigte.

Warum und wozu „Rechnen mit Uhren“?

Ja – warum eigentlich und was bedeutet „Rechnen mit Uhren“? Schauen wir uns die Ziffer einer Uhr an. Sie hat 12 Ziffern und wenn wir z.B. eine Stunde auf neun Uhr hinzurechnen, kommen wir auf zehn Uhr. So weit ist alles klar. Was aber wenn wir z.B. auf 11 Uhr zwei weitere Stunden hinzurechnen wollen? Dann kommen wir auf 13 oder 1 Uhr und das ist nicht Weiter als modulares Rechnen. Wir addieren und subtrahieren Stunden auf unsere Uhrzeit hinzu und drehen uns dabei im Kreis.

Doch was bringt uns das, bzw. was ist so toll an dieser Rechenmethodik? Als erstes ist diese Art von Arithmetik irrsinnig effizient, so dass man sie sehr gut von Maschinen durchführen lassen kann. Angenommen wir möchten folgende Berechnung tätigen:

325 Uhr + 27 Uhr = 352 Uhr

Wir wissen, dass es so etwas wie 325 Uhr nicht gibt und deshalb rechnen wir:

325 Uhr = 27*12 + 1 Uhr und 27 Uhr = 2*12 + 3 Uhr, also erhalten wir 1 Uhr + 3 Uhr = 4 Uhr und müssen uns nicht wie bekloppt beim Rechnen im Kreis drehen, bis uns schwindelig wird.

Wir operieren in einem endlichen Zahlenraum {0,1,…,11} von 12 „Ziffern“ und sagen, dass wir „modulo 12“ rechnen.

Es klingt einfach und doch befremdlich. Warum rechnen wir nicht ganz normal wie wir es mit ganzen Zahlen gewohnt sind? Weil unsere Rechner nur mit einem festen Satz von Zahlen rechnen können, was wiederum bedeutet, dass wir notgedrungen irgendwann auf eine feste Zahlengröße zurück müssen. Es bleibt uns keine andere Wahl und aus dieser Not müssen wir das beste machen.

Betrachten wir unsere heutige Rechnerarchitektur. So gut wie alle PCs sind heute 64Bit-Rechner. Mit 64-Bit lässt sich ein Zahlenraum von 0 bis 2^{64}-1= 18446744073709551615 abdecken. Das ist zwar eine sehr große Zahl aber immer noch zu klein. Wenn wir diese Zahl nehmen und nur eine 1 dazu addieren, passiert genau das Gleiche wie mit unserer Uhr welche 12 Ziffern hat. Wir landen bei 0 bzw. 12 Uhr. Hinzu kommt auch, dass wir es bei den meisten Algorithmen und Verschlüsselungsverfahren mit wesentlich größeren Zahlenbereichen zu tun haben, so dass wir diese als SW-Objekte auslagern müssen. Hier ein Bespiel von zwei Primzahlen, welche von einem RSA-Verschlüsselungsverfahren benutzt werden könnte.

Wir sehen, dass die Zahlen wesentlich größer sind als mit unseren 64-Bit Registern aufzufüllen wären. Die Mathematik dahinter basiert ebenfalls auf unserer modularen Arithmetik. Wie RSA funktioniert, werde ich in meinem nächsten Blogbeitrag erklären.

Was ist mit der Multiplikation und der Division? Diese funktioniert wie sonst auch, nur mit einem kleinen Unterschied. Kommen wir zu unserem Bespiel mit den Uhren zurück. Angenommen wir möchten die 47 mit der 23 multiplizieren. Das können wir auf zwei Weisen wie folgt machen:

(47*23) mod 12 = (1081) mod 12 = 1 mod 12

oder

(9*12+11)*(1*12+11) mod 12 = (11*11) mod 12 =121 mod 12 = (10*12+1) mod 12 = 1 mod 12

Wir sehen am letzten Beispiel, dass die letztere Art zu rechnen wesentlich effizienter ist, da wir nicht so oft mit unserem „Urzeigerpropeller“ rotieren müssen (wir sparen Zeit und Energie).

Ich möchte auch hier nicht zu tief in die Mathematik einsteigen, da ich diese Art von Rechnen mit Zahlen im Uhrzeigersinn in den folgenden Algorithmen der nächsten Blogartikelreihe anwenden werde. Wer tiefer einsteigen möchte, dem empfehle ich die folgenden Bücher (hier kommt ein Link zu den Büchern).

Ausgestattet mit der Addition und Multiplikation (das Subtrahieren und Dividieren sind die gleichen Operationen nur umgekehrt), sowie einem neutralen Element (Null für die Addition und Eins für die Multiplikation), nennen die Mathematiker solche Gebilde „Ringe“ (genauer genommen Restklassenringe) und schreiben (Z/mZ), wobei m das Modulo ist, welches wir gebrauchen (In unserem Uhrzeigerbeispiel war dies die 12).

Wie in meinem Blogartikel über die Geschichte der Algorithmen habe ich erwähnt, dass Leibniz der Erfinder des binären Zahlensystems gewesen ist und damit den Grundstein für die heutige digitale Welt gelegt hat. Die Zahlensysteme auf Rechnern basieren nicht auf dem Dezimalsystem wie es der Mensch mit den arabischen Zahlen (0,1,2, … 9) gewohnt ist, sondern auf binären Zahlen (0 und 1). Hier stellt sich jetzt die Frage: Wie rechnen die Computer mit dem binären Zahlensystem bzw. wie sehen binäre Uhren aus?

Nehmen wir als Beispiel die Zahl „Dreizehn“ (ich schreibe diese Zahl mit Absicht als ein Wort). Klar ist, dass wir diese Zahl nicht mit nur einer Uhr darstellen können. Warum? Weil wir bei der dezimalen Uhr nur arabische Zahlensymbole von Null bis Neun (also Zehn Stellen) haben. Es fehlen uns noch vier Stellen. Eine Möglichkeit wäre, eine weitere Uhr zu benutzen, die sich merkt, wie oft wir uns bei der ersten Uhr im Kreis gedreht haben, um auf die „Dreizehn“ zu kommen. Auf diese Art und Weise können wir Zahlen von 0 bis 99 darstellen.

Was aber, wenn wir die Zahl „Einhundertunddreizehn“ darstellen wollen. Ganz einfach. Wir nehmen uns eine dritte „Zehneruhr“ zur Hilfe und merken uns den Übertrag der zweiten Uhr. Ich glaube Ihr ahnt schon, wo wir hinsteuern. Jede weitere Stelle sieht eine weitere Zehnerpotenz vor und so stellen wir unsere heutigen Zahlen dar. Das folgende Bild verdeutlicht dies:

Jetzt haben wir es bei Maschinen mit „Null“ und „Eins“ zu tun. Wie stelle ich dort die Zahl „Dreizehn“ und wie die Zahl „Einhundertunddreizehn“ dar? Genau so, nur dass es mehr Stellen gibt, da die „binäre Uhr“ nur zwei Stellen im Ziffernblatt hat.

Interessant wird jetzt das Potenzieren und Dividieren sein. Wenn wir eine Zahl im Dezimalsystem mit 10 multiplizieren oder dividieren, geht dies sehr einfach. Wir müssen nur die Kommastelle nach rechts oder links schieben. Wie machen wir das Ganze mit Binärzahlen? Auch hier „bewegen“ (shiften) wir die Binärzahl nach links oder rechts, nur dass dies einer Multiplikation bzw. Division mit einer „Zwei“ entspricht. Das „Shiften“ wird uns sehr oft bei vielen Algorithmen begegnen. Die Operationen sind in der beiliegenden Bild kurz zusammengefasst:

Zu guter Letzt möchte ich etwas über „Hexadezimalzahlen“ sagen und erläutern, warum es oft praktisch ist diese Zahlenschreibweise, anstatt der Binären zu verwenden (was in 99% der Fälle auf dem Rechner so gemacht wird).

Wenn wir nur drei binäre Stellen benutzen, dann können wir nur Zahlen von 0 bis 7 darstellen (2^3=8) und bei vier binären Stellen Zahlen von 0 bis 15 (2^4=16). Das bedeutet, dass wir unser dezimales Zahlensystem irgendwo zwischen zwei und drei Binärstellen unterbringen müssten. Das macht es sehr aufwändig und ineffizient, wenn es um das Rechnen auf Maschinen geht. Aus diesem Grund erweitert man das Zahlensystem so, dass es genau mit vier Binärstellen abgedeckt ist. Da dieses Zahlensystem 16 Symbole benötigt, nennt man dieses auch „Hexadezimalsystem“ und sieht wie folgt aus:

Wir sehen hier, dass wir die Symbole vollständig innerhalb vier Bit unterbringen können und damit jetzt für die verschiedenen Bit-Architekturen die folgende Struktur vorliegen haben:

Jetzt sind wir mithilfe unserer hexadezimalen Bit-Architektur in der Lage, äusserst effizient Modulare Arithmetik mit sehr großen Zahlen zu betreiben.

Zusammenfassung

Wir haben gelernt, wie man modulare Arithmetik anwendet und wie das Hexadezimalsystem aufgebaut ist. Das was, wir in diesem Blogartikel aber auch gelernt haben, dient uns zusammen mit der Erkenntnis rund um den euklidischen Algorithmus dazu, die „Mutter aller Verschlüsselungen“ anzugehen. Dies ist das RSA-Verfahren!

Referenzen

[1] Peter Bundschuh – Einführung in die Zahlentheorie, Springer-Verlag Berlin Heidelberg, 2008, ISBN 978-3-540-76490-8

[2] Edmund Weitz – Konkrete Mathematik (nicht nur) für Informatiker – Springer Spektrum, 2018, ISBN 978-3-658-21564-4

[3] Berthold Vöcking · Helmut Alt Martin Dietzfelbinger · Rüdiger Reischuk · Christian Scheideler · Heribert Vollmer · Dorothea Wagner – Taschenbuch der Algorithmen, Springer-Verlag Berlin Heidelberg, 2008, ISBN 978-3-540-76393-2