Arithmetik

Modulare Multiplikation

 aufwärts

Schulmethode der Division

Seien x, m Element natürliche Zahlen. 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 beispielsweise wird 72 durch 13 geteilt; es verbleibt der Rest r = 7. Bild 1 zeigt das ent­sprechende Schema der Schulmethode für die Division.

 1001000:1101=0101
0000
 10010
 1101
   1010
  0000
   10100
   1101
     111
Bild 1: Schulmethode der Division

Die Schwierig­keit bei der Division besteht darin, dass jedesmal 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 2k
  2. da nicht 2k subtrahiert werden sollte, sondern nur m, wird der Korrektur­wert 2k mod m addiert

Beispiel:  Die Zahl 1 0 0 1 0 ist um ein Bit länger als 1 1 0 1. Daher kann 1 1 0 1 sicher subtrahiert werden:

 

 10010
 1101
   101

Die Subtraktion wird realisiert, indem das vorne überstehende Bit weggelassen wird – dies entspricht hier einer Subtraktion von 16. Da aber nicht 16, sondern 13 subtrahiert werden sollte, wird der Korrektur­wert 16 mod 13 = 3 addiert:

 

  0010
+   11
   101

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.

 1001000:1101
+   11
  01010
+     0
   10100
+     11
     111
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 ent­sprechender 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.

 1111100:1101=101
+   11
 100100
+   110
   10100
+     11
     111
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: 2k mod m, 2·2k mod m und 3·2k 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.

  1000·1001
  1000
+  0000
+   0000
+    1000
= 1001000
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.

 1000·1001:1101=0101
 1000
0000
 1000
+ 0000
 1101
  0011
+  0000
  0000
   0110
+   1000
   1101
    0111
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 auftretenden Zahlen. Es zeigt sich, dass nicht mehr als zwei überstehende Bits auftreten 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 ent­sprechenden Korrektur­wertes durchgeführt.

 

Algorithmus ModulareMultiplikation
Eingabe:Zahlen  x = xn-1, ..., x0  und  y = yn-1, ..., y0
Ausgabe:Zahl  z = x·y mod m
Methode:
  1. s = 0    // len(s)kleiner gleichn

    c = 0    // len(c)kleiner gleichn

    für i = n-1 abwärts bis 0 wiederhole

    1. s = s·2     // len(s)kleiner gleichn+1

      c = c·2     // len(c)kleiner gleichn+2

      p = x·yi    // len(p)kleiner gleichn

      (s, c) = carrySaveAdd(s, c, p)

      // len(s)kleiner gleichn+2

      // len(c)kleiner gleichn+2

      a = correctionValue(s, c)

      // len(a)kleiner gleichn

      s = s mod 2n    // len(s)kleiner gleichn

      c = c mod 2n    // len(c)kleiner gleichn

      (s, c) = carrySaveAdd(s, c, a)

      // len(s)kleiner gleichn

      // len(c)kleiner gleichn+1

    z = s+c    // konventionelle Addition

    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 2n 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·2n mod m, ..., 5·2n 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(vertikaler Abstand) Themen des Buches: Sortieren, Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  

 

Weiter mit:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 30.03.2002   Updated: 20.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik