Arithmetik

Schulmethode der Division

Seien x, m ∈ ℕ. Um r = x mod m zu berechnen, wird x durch m geteilt und der Rest r ermittelt. Die Schulmethode der Division liefert den Rest zum Schluss, wenn der Divisor nicht mehr subtrahiert werden kann.

Für die Berechnung von 72 mod 13 beispiels­weise wird 72 durch 13 geteilt; es verbleibt der Rest r = 7. Bild 1 zeigt das entsprechende Schema der Schulmethode für die Division.

Bild 1: Schulmethode der Division

Die Schwierig­keit bei der Division besteht darin, dass jedes Mal ein Vergleich notwendig ist, um zu entscheiden, ob der Divisor subtrahiert werden kann oder ob 0 subtrahiert werden muss.

Ein Vergleich kann durch eine Subtraktion realisiert werden. D.h. der Divisor wird in jedem Fall subtrahiert. Es wird dann mit dem Wert vor der Subtraktion oder mit dem Wert nach der Subtraktion fortgefahren, je nach dem, ob das Ergebnis der Subtraktion negativ oder nichtnegativ ist.

Ob das Ergebnis negativ ist, lässt sich anhand des entstehenden Übertrags­bits erkennen. Ist dieses 1, so ist das Ergebnis negativ.

Das Divisions­verfahren benötigt n – d Subtraktionen, wobei n die Länge des Dividenden und d die Länge des Divisors ist. Es bietet sich an, diese Subtraktionen mit einem Carry-Save-Addierer jeweils in konstanter Zeit durch­zuführen. Die bei der Carry-Save-Addition verwendete redundante Zahlen­darstellung ermöglicht jedoch leider nicht, in konstanter Zeit zu erkennen, ob eine Zahl negativ ist, ebenso wenig ermöglicht sie einen Vergleich zwischen zwei Zahlen in konstanter Zeit.

Sichere Subtraktion

Das folgende Verfahren für Berechnungen modulo m ist auch für die Carry-Save-Addition geeignet.

Die Idee ist, den Divisor nur dann zu subtrahieren, wenn er sich sicher subtrahieren lässt. Dies ist dann der Fall, wenn die Zahl, von der er subtrahiert wird, um ein Bit länger ist. Die Tatsache, ob eine Zahl länger ist als eine andere, lässt sich auch bei redundanter Zahlen­darstellung feststellen.

Statt den Divisor m direkt zu subtrahieren, werden zwei Schritte ausgeführt:

1. das vorne überstehende Bit wird weggelassen, dies entspricht der Subtraktion einer bestimmten Zweierpotenz 2^k
2. da nicht 2^k subtrahiert werden sollte, sondern nur m, wird der Korrektur­wert 2^k mod m addiert

Folgendes Bild zeigt das Divisions­verfahren nach dieser Methode. Der Divisor wird nur dann subtrahiert, wenn er sich sicher subtrahieren lässt. Die jeweils weg­gelassenen Bits sind grün dargestellt.

Bild 2: Berechnung  72 mod 13 = 7

Es kann vorkommen, dass im Verlauf dieses Verfahrens zwei Bits vorne überstehen, wie in folgendem Bild zu sehen ist. Dann muss beim Weglassen dieser Bits ein entsprechender anderer Korrektur­wert addiert werden. Hier entsprechen die weg­gelassenen Bits 1 0 dem Wert 32, der Korrektur­wert ist somit 32 mod 13 = 6.

Bild 3: Berechnung  124 mod 13 = 7

Mehr als zwei Bits können vorne nicht überstehen. Denn nach der Addition des Korrektur­wertes kann höchstens ein Bit überstehen. Nach dem Schieben können daher höchstens zwei Bits überstehen.

In einem Vorlauf des Verfahrens werden also drei Korrektur­werte bestimmt: 2^k mod m, 2·2^k mod m und 3·2^k mod m. Der Aufwand hierfür ist natürlich nur dann gerecht­fertigt, wenn der Modul m feststeht und viele Berechnungen modulo m durchgeführt werden sollen.

Der Vorteil dieses Verfahrens besteht darin, dass es sich für die Carry-Save-Addition eignet.

Multiplikation modulo m

Bild 4 zeigt das Schema der Schulmethode für die Multi­plikation zweier Binärzahlen. In diesem Beispiel werden die Zahlen 8 und 9 multi­pliziert, das Ergebnis ist 72.

Bild 4: Schulmethode der Multiplikation  8·9 = 72

Für die Multi­plikation modulo m bietet es sich an, das Schema für die Multi­plikation und das Schema für die Division ineinander zu verschränken, d.h. jeweils nach einer Addition des Multi­plikationsschemas eine Subtraktion des Divisions­schemas auszuführen (Bild 5). Der Rechen­aufwand verringert sich dadurch nicht, allerdings wird nicht erst ein Ergebnis der Länge 2n erzeugt.

Bild 5: Verschränkte Multiplikation und Division  8 · 9 : 13  =  5 Rest 7

Das folgende Verfahren realisiert die Multi­plikation modulo m durch verschränkte Multi­plikation und Division unter Benutzung der Carry-Save-Addition [BS 03].

Die durch Kommentare dar­gestellten Zusicherungen betreffen die Länge der auf­tretenden Zahlen. Es zeigt sich, dass nicht mehr als zwei überstehende Bits auf­treten können.

Der Subtraktions­schritt bei der ver­schränkten Multi­plikation und Division wird jeweils durch Weglassen der über­stehenden Bits und Addition eines entsprechenden Korrektur­wertes durchgeführt.

Algorithmus ModulareMultiplikation

Eingabe:

Zahlen  x = x_n-1, ..., x₀  und  y = y_n-1, ..., y₀

Ausgabe:

Zahl  z = x·y mod m

Methode:

1. s = 0    // len(s) ≤ n
2. c = 0    // len(c) ≤ n
3. für i = n-1 abwärts bis 0 wiederhole
1. s = s·2     // len(s) ≤ n+1
2. c = c·2     // len(c) ≤ n+2
3. p = x·y_i    // len(p) ≤ n
4. (s, c) = carrySaveAdd(s, c, p)
5. // len(s) ≤ n+2
6. // len(c) ≤ n+2
7. a = correctionValue(s, c)
8. // len(a) ≤ n
9. s = s mod 2ⁿ    // len(s) ≤ n
10. c = c mod 2ⁿ    // len(c) ≤ n
11. (s, c) = carrySaveAdd(s, c, a)
12. // len(s) ≤ n
13. // len(c) ≤ n+1
4. z = s+c    // konventionelle Addition
5. z = z mod m    // höchstens 3 konventionelle Subtraktionen

Analyse

Die Schleife wird n-mal durchlaufen. Alle Operationen in der Schleife lassen sich bit-parallel in konstanter Zeit ausführen. Die Operation ·2 entspricht einem Links­schieben um 1; die Operation mod 2ⁿ entspricht einem Weglassen der Bits n und n+1.

Der Korrektur­wert a wird aus einer Tabelle in Abhängigkeit von den beiden, jeweils bei s und c über­stehenden Bits abgelesen. Die Summe dieser Bits kann einem Wert zwischen 0 und 5 entsprechen (der Wert 6 ist nicht möglich). Dem­entsprechend müssen in einem Vorlauf die fünf Korrektur­werte

1·2ⁿ mod m, ..., 5·2ⁿ mod m

berechnet und in die Tabelle eingetragen werden. Dies kann in Zeit O(n) geschehen.

Die Addition am Schluss des Algorithmus kann mit einem Ripple-Carry-Addierer in O(n) Schritten durchgeführt werden. Ebenso kann die abschließende mod-m-Berechnung mit der Schulmethode der Division ausgeführt werden; es sind hierbei höchstens 3 Subtraktionen zu je O(n) Schritten erforderlich. Damit bleibt das gesamte Verfahren in Zeit O(n).

Literatur

[BS 03]   V. Bunimov, M. Schimmler: Area and Time Efficient Modular Multiplication of Large Integers. Proceedings of the IEEE Int. Conf. on Application-Specific Systems, Architectures, and Processors (ASAP'03), 400-411 (2003)

[Lan 12]   H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Den Algorithmus zur modularen Multiplikation finden Sie auch in meinem Buch über Algorithmen.
Weitere Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]