Ein kurzer Ausflug in die Mathematik

Im letzten Kapitel wurden einige Bildungsvorschriften benutzt, in denen das Wort mod vorkam. Hierbei handelt es sich um die sogenannte Modulo-Funktion, die nachfolgend ein wenig genauer unter die Lupe genommen wird. Die Modulo-Arithmetik, manchmal auch Uhren-Arithmetik genannt, ist ein Gebiet der Mathematik, auf dem sich reichlich Einwegfunktionen finden, diese werden ausführlicher im Abschnitt zu der Public-Key-Chiffrierung beschrieben.. In der Modulo-Arithmetik werden endliche Gruppen von Zahlen untersucht, die auf einer Schleife angeordnet sind, ähnlich wie die Ziffern einer Uhr. Denken wir uns beispielsweise eine Uhr für modulo 7 (oder mod 7), die nur 7 Zahlen von 0 bis 6 besitzt. Um die Aufgabe 2+3 zu lösen, beginnen wir bei 2, gehen drei Schritte im Kreis und landen bei 5, erhalten also dieselbe Antwort wie in der üblichen Arithmetik. Um 2+6 zu lösen, beginnen wir bei 2 und gehen sechs Schritte im Kreis, doch diesmal überschreiten wir die 0 und landen bei 1, was wir in der normalen Arithmetik nicht erhalten würden. Die Rechnungen können wie folgt dargestellt werden:

2 + 3 = 5 (mod 7) und 2 + 6= 1 (mod 7)

Die Modul-Arithmetik ist relativ einfach, und tatsächlich betreiben wir sie jeden Tag, wenn wir über die Zeit reden. Wenn es jetzt 9 Uhr ist und wir in 8 Stunden ein Date haben, können wir auch sagen, das Treffen ist um 5 Uhr. Wir haben im Kopf 9+8 (mod 12) ausgerechnet. Stellen wir uns eine Uhr vor, schauen wir auf die 9 und gehen 8 Ziffern weit im Kreis, dann landen wir bei 5:

9 + 8 = 5 (mod 12)

Anstelle von Uhren nehmen die Mathematiker eine Abkürzung und führen Moduloberechnungen nach der folgenden Regel aus. Erstens wird das Ergebnis in der normalen Arithmetik berechnet. Wenn wir zweitens die Antwort (mod x) wissen wollen, teilen wir das normale Ergebnis durch x und notieren den Rest. Dieser Rest ist die Antwort (mod x). Um die Antwort auf

11 x 9(mod 13) zu finden, tun wir folgendes:

11 x 9 = 99
               99 / 13 = 7, Rest 8 daraus folgt 11 x 9 = 8 (mod 13)

Funktionen in der Modulo-Arithmetik verhalten sich oft unstet, was sie in manchen Fällen zu den bereits oben erwähnten Einwegfunktionen macht. Dies wird deutlich, wenn wir eine einfache Funktion in der gewöhnlichen Arithmetik mit der gleichen einfachen Funktion in der Modul-Arithmetik vergleichen. Im ersten Fall haben wir es mit einer Zweiwegfunktion zu tun, die leicht umzukehren ist; in der Modul-Arithmetik jedoch ist sie eine Einwegfunktion. Nehmen wir beispielsweise die Funktion 3^x. Das heißt, wir nehmen ein Zahl x, multiplizieren dann die 3 x-mal mit sich selbst und erhalten eine neue Zahl. Wenn x=2 ist und wir die Funktion ausführen, dann erhalten wir:

3^x = 3² = 3 x 3 = 9

Die Funktion verwandelt also 2 in 9. In der normalen Arithmetik erhöht sich mit dem Wert von x auch das Ergebnis der Funktion. Wenn man uns also das Ergebnis der Funktion lieferte, wäre es recht einfach, sie umzukehren und die Ausgangszahl zu erschließen. Wenn das Resultat beispielsweise 81 lautet, können wir schließen, dass x den Wert 4 hat, denn 3⁴ = 81. Wenn wir nur raten und annehmen, x habe den Wert 5, können wir 3⁵ = 243 berechnen und feststellen, dass wir zu hoch angesetzt haben. Dann können wir den Wert von x auf 4 senken und bekommen die richtige Antwort. Selbst wenn wir also falsch raten, können wir uns auf den richtigen Wert von x einpendeln und damit die Funktion umkehren.
In der Modulo-Arithmetik verhält sich dieselbe Funktion jedoch nicht so vernünftig. Nehmen wir an, man sagt uns, dass 3^x (mod 7) = 1 ist und fordert uns auf, den Wert von x zu finden. Auf Anhieb fällt uns kein Wert ein, weil wir mit der Modul-Arithmetik nicht vertraut sind. Wir könnten versuchsweise annehmen, dass x = 5 und das Ergebnis von 3⁵ (mod 7) ausrechnen. Die Antwort lautet 5, und das ist zu groß, denn wir suchen nach 1 als Ergebnis. Wenn wir dann den Wert von x verringern, vielleicht auf 4, und es erneut probieren, würden wir in die falsche Richtung gehen, denn die Antwort lautet x = 6. In der normalen Arithmetik können wir Zahlenwerte ausprobieren und feststellen, ob die Spur heißer oder kälter wird. Auf dem Feld der Modulo-Arithmetik gibt es keine nützlichen Hinweise, und die Umkehrung der Funktionen ist viel schwieriger. Oft besteht der einzige Weg darin, die Funktion für viele Werte von x zu berechnen und eine Tabelle zu erstellen, bis die richtige Antwort gefunden ist. Tabelle 4 zeigt die Ergebnisse mehrerer Werte von x für die Funktion 3^x in der gewöhnlichen Arithmetik und in der Modulo-Arithmetik. Sie zeigt deutlich das unstete Verhalten der Funktion, wenn sie in der Modulo-Arithmetik berechnet wird. Eine solche Tabelle mit relativ kleinen Zahlen zu erstellen ist zwar ein wenig mühselig, doch wäre es unglaublich schwer, eine Tabelle für Funktionen wie 453^x (mod 21997) zu erstellen. Dies ist ein klassisches Beispiel für eine Einwegfunktion, weil ich einen Wert für x wählen und das Ergebnis der Funktion berechnen könnte, doch wenn ich Ihnen ein Resultat geben würde, sagen wir 5787, hätten Sie enorme Schwierigkeiten, die Funktion umzukehren und auf das ursprüglich gewählte x zu schließen. Für die Berechnung von 5787 braucht man lediglich ein paar Sekunden, doch Sie würden Stunden brauchen, um die Tabelle zu erstellen und das gewählte x herauszufinden.