Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


36. Arithmetik



Rechenoperationen mit großen ganzen Zahlen

Eine große ganze Zahl kann wie ein Polynom behandelt werden, mit gewissen Einschränkungen bezüglich der Koeffizienten. Zum Beispiel könnte die aus 28 Ziffern bestehende ganze Zahl

0120200103110001200004012314

dem Polynom

x26 + 2x25 + 2x23 + x20 + 3x18 + x17 + x16 + x12 + 2x11 + 4x6 + x4 + 2x3 + 3x2 + x + 4

entsprechen. Das heißt, die Zahl ist gleich dem Wert des Polynoms im Punkt x = 10. Umgekehrt entspricht jedes Polynom vom Grad N - 1 mit positiven ganzen Koeffizienten, die kleiner als 10 sind, genau einer N-stelligen ganzen Zahl.

Demzufolge können wir Polynom-Operationen benutzen, um mit großen ganzen Zahlen zu rechnen. Das heißt, daß wir ganze Zahlen einfach mit Hilfe von Feldern darstellen und dann die soeben entwickelten Routinen für das Operieren mit Polynomen anwenden, als ob die Felder Polynome darstellen würden. Um zum Beispiel zwei 100-stellige Zahlen zu multiplizieren, könnten wir den obigen Algorithmus verwenden, um ein 200-stelliges Ergebnis zu berechnen. Die Schwierigkeit bei dieser Strategie besteht darin, daß die Koeffizienten im Ergebnis nicht unbedingt kleiner als 10 sind. Dies läßt sich in einem einzigen Durchlauf korrigieren: Mit i=0 beginnend, addiere man p[i] div 10 zu p[i+1], ersetze p[i] durch p[i] mod 10 und inkrementiere i, womit fortzufahren ist, bis keine von null verschiedenen Koeffizienten übrig sind.

Es könnte auch eine größere Wurzel als 10 verwendet werden; zum Beispiel könnte die obige 28-stellige Zahl auch dem Polynom

120x6 + 2001x5 + 311x4 + x3 + 2000x2 + 401x + 2314

entsprechen. Die Auswertung dieses Polynoms für x = 10000 würde die ganze Zahl ergeben. Dies ermöglicht es, die ganze Zahl mit weniger Speicherplatz darzustellen (im vorliegenden Beispiel mit einem Viertel), eröffnet jedoch die Möglichkeit eines Überlaufs in den Koeffizienten während irgendeiner Zwischenrechnung. Die Frage, wie groß eine Basis sein kann, damit man sie verwenden kann, ist sorgfältig mathematisch untersucht worden, doch in der Praxis entstehen kaum Nachteile, wenn man den konservativen Ansatz der Benutzung einer kleinen Basis wählt.

Bei dem RSA-Kryptosystem (Kapitel 23) müssen wir nicht nur große ganze Zahlen multiplizieren, sondern auch potenzieren und dividieren. Insbesondere müssen wir Mp mod N berechnen, wobei sowohl M als auch p als auch N große ganze Zahlen sind. Dies ist keine leicht auszuführende Auswertung, doch wir können ein Verfahren dafür skizzieren. Zunächst kann das Potenzieren mit Hilfe sukzessiver Multiplikationen in der oben beschriebenen Weise ausgeführt werden, so daß es genügt, sich zu überlegen, wie M1M2 mod N zu berechnen ist, wenn M1, M2 und N große ganze Zahlen sind. Der Schlüssel für die Ausführung der Auswertung des Rests ist die Auswertung von 10i mod N für alle 10i, die kleiner sind als die größte ganze Zahl, die auftreten kann. Danach ergibt sich jeder spezielle Rest als eine Linearkombination dieser Werte. Eine größere Basis verringert den erforderlichen Rechenaufwand. Mathematisch ausgedrückt, entspricht diese Methode der Auswertung von beispielsweise

0120200103110001200004012314 mod N

mittels Auswertung von

120(x6 mod N) + 2001(x5 mod N) + 311(x4 mod N) + (x3 mod N) + 2000(x2 mod N) + 401(x mod N) + 2314

für x = 10000. Die Werte von 10000i mod N können im voraus berechnet und in einer Tabelle gespeichert werden, oder nach Bedarf inkrementell berechnet werden, wie im Falle des Algorithmus zur Suche in Zeichenfolgen von Rabin-Karp aus Kapitel 19.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]