DE69032811T2

DE69032811T2 - Verfahren und System zur modularen Multiplikation

Info

Publication number: DE69032811T2
Application number: DE69032811T
Authority: DE
Inventors: Hikaru Hachiohji-Shi Tokyo Morita
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1989-01-30
Filing date: 1990-01-30
Publication date: 1999-04-29
Anticipated expiration: 2010-01-31
Also published as: CA2008774A1; EP0381161A2; DE69032811D1; EP0381161B1; US5073870A; CA2008774C; EP0381161A3

Description

HINTERGRUND DER ERFINDUNG

Sachgebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf ein Verfahren zur modularen Multiplikation und auf ein System zum Ausführen einer modularen Multiplikation, wie beispielsweise A · B Modulo (bezeichnet als mod nachfolgend) N bei hoher Geschwindigkeit, wobei A einen Multiplikanden beschreibt; B einen Multiplikator bezeichnet und N einen Modulus bezeichnet. Die vorliegende Erfindung ist effektiv verfügbar für kryptographische und authentisierende Systeme oder Techniken, da eine modulare Potenzierung (Potenzmultiplikation), wie beispielsweise Me mod N (wobei e den Exponenten bezeichnet), in derselben Art, wie A · B mod N, ausgeführt werden kann.

Beschreibung des Stands der Technik

In dem herkömmlichen Verfahren einer modularen Multiplikation A · B mod N wird, wie in Fig. 1(A) dargestellt ist, nachdem A · B berechnet worden ist, das berechnete A · B durch N geteilt, um einen Rest bzw. ein Restglied als sein Berechnungsergebnis zu erhalten. In dieser Zeichnung wird die Multiplikation durch Verschieben des Multiplikanden A Bit für Bit zu der Richtung des am meisten signifikanten Bits für eine Multiplizierungs-Addition auf der Basis von Radix bzw. Basis 2 erhalten, und die Division wird in derselben Art und Weise durch Verschieben des Modulus N in der entgegengesetzten Richtung für eine Divisions-Subtraktion ausgeführt. Deshalb sind, wenn die Zahl N von Bits in einer binären Bezeichnung von A, B und N bestimmt wird, n-fache Multiplizier-Additionen von Teilprodukten (A oder O) für die Multiplikation bei deren Maximum erforderlich und weiterhin sind n-malige Divisions-Subtraktionen für modulare Subtrahierer (N oder O) für die Division bei deren Maximum erforderlich. Weiterhin stellt Fig. 1(A) ein Beispiel von 7-Bit-Binärzahlen dar, wobei A/O A oder O darstellt.
In diesem herkömmlichen Verfahren ist es, obwohl Subtraktionen für eine Division wiederholt werden, da die modularen Subtrahierer nicht zuvor bestimmt sind, notwendig geworden, jeden Teilrest mit dem Modulus N für jede Teilsubtraktions-Operation zu vergleichen, so daß die divisionsmäßige Operation nicht effektiv ist und demzufolge die Rechengeschwindigkeit langsam ist.
Weiterhin erhöht sich, wenn das herkömmliche Verfahren durch eine Computer für allgemeine Zwecke ausgeführt wird, da jede Zahl A, B oder N in die Einheits-Zahl von Bits (Ziffern) (z. B. 32 Bits) vor einem Wiederholen der Additionen und Subtraktionen unterteilt wird, die Zahl der Additionen und Subtraktionen weiter. Als eine Folge existiert dabei, wenn sich die Zahl von Bits (Ziffern) n erhöht, ein Problem dahingehend, daß die dividierten Zwischenergebnisse in einer großen Anzahl von Registern gespeichert werden müssen, so daß es schwierig geworden ist, die Berechnung (Kalkulation) bei einer hohen Geschwindigkeit auszuführen. In dieser Hinsicht existiert, obwohl es auch möglich ist, die berechnungsmäßige Geschwindigkeit durch Ausführen einer Multiplikation zu verbessern, nachdem die Bits in die Zahl einer Verarbeitungseinheit der Multiplizierer dividiert worden ist, eingebaut in dem Computer für allgemeine Zwecke, weiterhin noch ein Problem dahingehend, daß sich die Anzahl von Zugriffen zu dem Speicher erhöht und die Berechnungsgeschwindigkeit noch niedrig ist.
Weiterhin entsteht dort, wo spezialisierte Schaltkreise, die simultan viele Bits verarbeiten können, eingesetzt sind, obwohl die berechnungsmäßige Geschwindigkeit verbessert werden kann, ein anderes Problem dahingehend, daß eine Hardware von einer Länge von 2n-Bit erforderlich ist und deshalb die Hardware-Effektivität nicht hoch ist.
Um die geringe Hardware-Effektivität der herkömmlichen, divisionsmäßigen Operation zu verbessern, ist ein Verfahren zum Verringern der Anzahl der Additionen und Subtraktionen, die sich auf divisionsmäßige Operationen beziehen, in Bezug auf eine Rest-Referenz-Tabelle vorgeschlagen worden. Das vorstehend erwähnte Verfahren des Verwendens einer Rest-Referenz-Tabelle dient dazu, ein Multiplikations-Ergebnis, das durch verschiedene, höher signifikante Bits dargestellt ist, in einen Rest bzw. Restglieder zu transformieren, der durch niedriger signifikante Bits dargestellt ist, nachdem ein 2n-Bit-Multiplikations-Ergebnis erhalten worden ist. Zum Beispiel werden in dem Fall einer 4-Bit-Einheit Reste durch Divisoren oder Moduli N von 0001 · 2n, 0010 · 2n, ... 1111 · 2n zuvor in einer Rest-Referenz-Tabelle aufgelistet und das Multiplikations-Ergebnis kann durch Addieren eines Werts, der durch Entfernen von 4 höher signifikanter Bits erhalten ist, zu dem Rest, der durch die 4 höher signifikanten Bits dargestellt ist, erhalten werden, um die Zahl von Bits eins um eins zu reduzieren, und die berechnungsmäßige Verarbeitung ist abgeschlossen, wenn das n-Bit-Multiplikations-Ergebnis erhalten worden ist.
Bei diesem Verfahren wird allerdings die Geschwindigkeit der Multiplikations-Operation nicht verbessert. Weiterhin erhöht die Rest-Referenz-Tabelle unvermeidbar die Speicherkapazität, um die Tabelle zu speichern. Zusätzlich ist, da n-Bit-Rest-Tabellen-Daten zu oder von Kalkulatoren übertragen werden, die Berechnungsgeschwindigkeit nicht hoch und das Schaltkreisvolumen ist groß und die Steuerung ist ziemlich kompliziert. Mit anderen Worten existieren dabei ernsthafte Probleme mit der Berechnungsgeschwindigkeit, dem Hardware-Volumen und der Schaltkreis-Design-Komplikation.
Um die Probleme zu beseitigen, die dann vorhanden sind, wenn auf Vielfach-Bit spezialisierte Schaltkreise in dem herkömmlichen Verfahren eingeschlossen werden, hat Baker ein Verfahren einer Verwendung spezialisierter Schaltkreise durch Zwischenfügen modularer Subtrahierer zwischen zwei Vervielfachungs-Additionen vorgeschlagen, so daß die Operation durch nur auf eine n-Bit-Länge spezialisierte Schaltkreise ausgeführt werden kann, wie durch "Fast Computation of A * B Modulo N", von P. W. Baker, Electron Letter, Vol. 23, No. 15, Seiten 794-795 (1987), offenbart ist.
In diesem Verfahren von Baker werden n-Bit partielle Produkte und n-Bit partielle, modulare Subtrahierer in Sequenz beginnend von den am meisten signifikanten Bits addiert oder subtrahiert. Die partiellen Produkte werden durch Heranziehen Bit für Bit des Multiplizierers B von dem am meisten signifikanten Bit und durch Addieren von A oder O zu dem partiellen Rest bestimmt. Andererseits werden -2N, -N, O, N oder 2N modularer Subtrahierer gemäß dem Wert des partiellen Rests bestimmt und dann zu dem partiellen Rest addiert. Der partielle Rest wird ein Bit zu der Seite des am meisten signifikanten Bits verschoben und die vorstehenden Operationen werden wiederholt. In diesem Verfahren von Baker wird, obwohl die Multiplikation auf der Basis einer Radix-Zahl 2 Bit für Bit ausgeführt wird, die Division auf der Basis einer Radix- Zahl 4 innerhalb eines Bereichs von -2N bis 2N ausgeführt, um zu verhindern, daß die partiellen Reste aus dem Berechnungsbereich mit der Längen-Bits überlaufen.
Dieses Verfahren nach Baker kann das Problem lösen, das bei den spezialisierten Schaltkreisen vorhanden ist; allerdings wird die berechnungsmäßige Geschwindigkeit nicht verbessert, da die Zahl von Additionen und Subtraktionen nicht merkbar im Vergleich mit dem herkömmlichen Verfahren reduziert werden kann.
Wie vorstehend anhand der Verfahren nach dem Stand der Technik beschrieben ist, existieren verschiedene Probleme in Bezug auf die berechnungsmäßige Geschwindigkeit, das Hardware-Volumen, die Schaltkreis-Design-Komplikation, usw..

ZUSAMMENFASSUNG DER ERFINDUNG

Unter Berücksichtigung dieser Probleme ist es deshalb eine primäre Aufgabe der vorliegenden Erfindung, ein modulares Multiplikationsverfahren und das System, hoch in der Berechnungsgeschwindigkeit, klein in einer Schaltkreisskalierung, einfach in einer Schaltkreiskonfiguration und leicht in einer Schaltkreis-Design-Prozedur, zu schaffen.
Um die vorstehend erwähnte Aufgabe zu lösen, weist das modulare Multiplikationsverfahren gemäß der vorliegenden Erfindung, wie in Anspruch 1 definiert ist, von A · B Modulo N, wobei A einen Multiplikanden bezeichnet, B einen Multiplikator bezeichnet, N einen Modulus bezeichnet, die Schritte auf: (a) Transformieren A von A [0, N] zu A &epsi;[-N/2, N/2], wobei E einen Satz von ganzen Zahlen bezeichnet; (b) Einstellen der Zahl von Bits n jeder Variablen von A, B oder N; (c) Initialisieren eines Rests R; (d) Bestimmen der Zahl von wiederholten Verarbeitungsstufen k als k ← n/r' + 1, wobei r eine Radix-Zahl r 2r', (r' ≥ 2) bezeichnet; n/r' eine maximale, ganze Zahl weniger als n/r' bezeichnet; und ← eine Substitution bezeichnet; (e) Aktualisieren eines partiellen Rests R und Bilden eines partiellen Multiplikators b und eines partiellen Quotienten c, beide innerhalb eines Bereichs von -r/2 ≤ b, c ≤ r/2; (f) Fortschreiben einer momentanen Stufe (k) als k ← k - 1; (g) Prüfen, ob die momentane Stufe (k) Null ist; (h) falls die Stufe (k) nicht Null ist, Zurückkehren zu der vorstehenden Stufe (e); und (i) falls die Stufe (k) Null ist, Transformieren eines abschließenden, partiellen Rests R in eine Lösung von A · B Modulo N. Der Schritt eines Transformierens A weist die Schritte auf von: (a) Vergleichen eines absoluten Multiplikanden A mit einem halben Divisor N/2 als A ≤ N/2 oder oder A N/2; (b) falls A ≤ N/2 ist oder A N/2 ist, Übergehen zu Schritt (b) in Anspruch 1; und (c) falls A > N/2 ist, Substituieren von A-N gegen A als A ← A-N und Fortschreiten zu dem Schritt (b) in Anspruch 1. Der Schritt eines Einstellens der Zahl von Bits n jeder Variablen von A, B oder N weist den Schritt eines Einstellens von n als n ← log&sub2;N + 1 auf, wobei log&sub2;N eine maximale, ganze Zahl weniger als log&sub2; N bezeichnet.
Der partielle Multiplikator b(k) kann auf der Basis des Multiplikators B gemäß dem nachfolgenden Ausdruck gebildet werden als
wobei b(k) innerhalb eines Bereichs von -r/2 ≤ b(k) ≤ r/2 liegt und r eine Radix-Zahl bezeichnet, und x eine maximale, ganze Zahl geringer als x bezeichnet. Der partielle Quotient c(k) wird durch Definieren der folgenden, komparativen Indizes li (b(k - 1)), l-i (b(k - 1)) unmittelbar nachdem der Multiplikand A transformiert worden ist, wie folgt gebildet:
wobei b(k - 1) {-r/2, -r/2 + 1, ..., -1, 0, 1, ... r/2 - 1, r/2}
gilt,
wobei den Satz ganzer Zahlen bezeichnet und i ein i-tes Bit von dem am wenigsten signifikanten Bit bezeichnet, und Bestimmen des partiellen Quotienten c(k) der momentanen Stufe wie folgt:
c(k) = i, falls li N < R(k - 1) ≤ li+1 N
c(k) = o, falls l-i N ≤ R(k - 1) ≤ l&sub1; N
c(k) = -i, falls l&sbplus;&sub1; N ≤ R(k - 1) < l-i N.
Der Schritt eines Aktualisierens des partiellen Rests R und des Bildens des partiellen Multiplikators b und des partiellen Quotienten c weist die Schritte auf: (a) Initialisieren eines partiellen Quotienten einer vorhergehenden Stufe c(k + 1) zu Null als c(k + 1) ← 0; (b) Bilden eines partiellen Multiplikators der momentanen Stufe b(k); (c) Aktualisieren eines partiellen Rests einer darauffolgenden Stufe R(k - 1) durch einen partiellen Rest der momentanen Stufe R(k), eines partiellen Quotienten einer vorhergehenden Stufe c(k + 1) und eines partiellen Multiplikators einer momentanen Stufe b(k) als R(k - 1) ← r{R(k) - c(k + 1)N} + b(k)A; (d) Bilden eines partiellen Multiplikators einer darauffolgenden Stufe b(k - 1); (e) Bilden eines partiellen Quotienten einer momentanen Stufe c(k); (f) Fortschreiben der momentanen Stufe (k) als k ← k - 1; (g) Prüfen, ob die momentane Stufe (k) Null ist; (h) falls die momentane Stufe (k) nicht Null ist, Zurückkehren zu dem obigen Schritt (c); und (i) falls die momentane Stufe (k) Null ist, Zurückkehren zu dem Schritt (i) von Anspruch 1; und wobei in Schritt (i) von Anspruch 1 der abschließende, partielle Rest R durch den abschließenden, partiellen Rest R(0) und den partiellen Quotienten c(1) als R(0) ← R(0) - c(1)N aktualisiert wird.
In einer weiteren Ausführungsform weist eine erste Modifikation des Schritts eines Aktualisierens des partiellen Rests R und des Bildens des partiellen Multiplikators b und des partiellen Quotienten c die Schritte auf: (a) Bilden eines partiellen Multiplikators b(k) der momentanen Stufe; (b) Aktualisieren eines partiellen Rests R(k - 1) einer darauffolgenden Stufe durch den partiellen Rest R(k) der momentanen Stufe und des partiellen Multiplikators b(k) der momentanen Stufe als R(k - 1) ← rR(k) + b(k)A; (c) Bilden eines partiellen Multiplikators b(k - 1) einer darauffolgenden Stufe; (d) Bilden des partiellen Quotienten c(k) der momentanen Stufe; (e) weiterhin Aktualisieren des partiellen Rests R(k - 1) der darauffolgenden Stufe durch den Rest R(k - 1) der darauffolgenden Stufe und des modularen Subtrahierers der momentanen Stufe c(k)N als R(k - 1) ← R(k - 1) - c(k)N; und (f) Fortschreiben der momentanen Stufe (k) als k ← k - 1; (g) Prüfen, ob die momentane Stufe (k) Null ist; (h) falls die momentane Stufe (k) nicht Null ist, Zurückkehren zu dem vorstehenden Schritt (b), und (i) falls die momentane Stufe (k) Null ist, Zurückkehren zu dem Schritt (i) in Anspruch 1.
Weiterhin weist der Schritt eines Transformierens des partiellen Rests der abschließenden Stufe R in eine Lösung von A · B mod N die Schritte auf: (a) Prüfen, ob der partielle Rest der abschließenden Stufe R(0) als ein Multiplikand A für eine darauffolgende, modulare Multiplikations-Berechnung verwendet wird; (b) falls R(0) verwendet wird, Substituieren des Rests R(0) für A als A ← R(0); (c) falls R(0) nicht verwendet wird, Prüfen, ob R(0) ≥ 0 ist; (d) falls R(0) ≥ 0 ist, Beenden der Verarbeitungsstufe; und (e) falls R(0) < 0 ist, Substituieren von R(0) und den Modulus N für R(0) als R(0) ← R(0) + N, bevor die Verarbeitungsstufe endet.
Weiterhin weist, um die vorstehend erwähnte Aufgabe zu lösen, das modulare Multiplikationssystem gemäß der vorliegenden Erfindung, wie es in Anspruch 20 definiert ist, zum Ausführen einer modularen Multiplikation von A · B mod N auf der Basis einer Radix-Zahl R auf: (a) eine erste Registereinrichtung (11) zum Speichern eines Multiplikanden A; (b) eine zweite Registereinrichtung (13) zum Speichern eines Multiplikators B; (c) eine dritte Registereinrichtung (15) zum Speichern eines Modulus N; (d) eine vierte Registereinrichtung (17) zum Speichern eines partiellen Rests R; (e) eine Normalisierungseinrichtung (21), die auf die dritte Registereinrichtung zum Normalisieren des Modulus N anspricht; (f) eine Parameter-Erzeugungseinrichtung (23), die auf die erste, die zweite, die dritte und die vierte Registereinrichtung und die Normalisierungseinrichtung anspricht, zum Erzeugen partieller Multiplikatoren b(k) und eines partiellen Quotienten c(k), wobei (k) eine Zahl von Verarbeitungsstufen von (k = n/r' + 1) zu (o) bezeichnet; (g) eine ein partielles Produkt erzeugende Einrichtung (31), die auf die erste Registereinrichtung und die Parameter-Erzeugungseinrichtung anspricht, zum Erzeugen partieller Produkte b(k)A; (h) eine einen modularen Subtrahierer erzeugende Einrichtung (33), die auf die dritte Registereinrichtung und die Parameter-Erzeugungseinrichtung anspricht, zum Erzeugen modularer Subtrahierer c(k)N; (i) eine einen Rest aktualisierende Einrichtung (35), die auf die vierte Registereinrichtung anspricht, zum Aktualisieren eines Rests R(k); (j) eine Übertrag-Sicherungs-Addierer-Einrichtung (37), die auf die das partielle Produkt erzeugende Einrichtung, die Erzeugungseinrichtung des modularen Subtrahierers und die den Rest aktualiserende Einrichtung anspricht, zum Ausführen einer Übertrag-Sicherungs-Addition von Rnew ← rx(Rold - c(k)N) + b(k)A, um den Rest R(k), der in der vierten Registereinrichtung gespeichert ist, zu aktualisieren, wobei Rnew einen aktualisierten Rest bezeichnet; (k) eine Übertrag-Propagations-Addierer-Einrichtung (39), die auf die Übertrag-Sicherungs-Addierer-Einrichtung anspricht, zum Ausführen einer Übertrag-Propagations-Addition, um den Multiplikanden A, der in der ersten Registereinrichtung gespeichert ist, durch Rnew zu aktualisieren, und zum Erzeugen einer Lösung von R(0) = A · B Modulo N; und (I) eine Sequenz-Steuereinrichtung, die auf alle Einrichtungen anspricht, zum sequentiellen Steuern von berechnungsmäßigen Operationen. Die Parameter-Erzeugungsseinrichtung (23) weist auf: (a) eine einen partiellen Multiplikator erzeugende Einrichtung (23A), die auf das zweite Register anspricht, zum Erzeugen partieller Multiplikatoren b(k) innerhalb eines Bereichs von -r/2 ≤ b ≤ r/2; (b) eine einen partiellen Quotienten erzeugende Einrichtung (23B), die auf die erste, die dritte und die vierte Registereinrichtung und auf die den partiellen Multiplikator erzeugende Einrichtung anspricht, zum Erzeugen eines partiellen Quotienten c(k) innerhalb eines Bereichs von -r/2 ≤ c ≤ r/2; (c) eine einen komparativen Index erzeugende Einrichtung (23c), die auf die erste und die dritte Registereinrichtung und die den partiellen Multiplikator und den Quotienten erzeugende Einrichtung anspricht, zum Erzeugen eines komparativen Index l zum Bestimmen eines Bereichs in einem modifizierten Robertson-Diagramm; und (d) eine Komparator-Einrichtung (23D), die auf die erste und dritte Registereinrichtung anspricht, zum Vergleichen des Multiplikanden A mit dem Modulus N, um den den partiellen Multiplikator und den Quotienten erzeugenden Einrichtungen zu ermöglichen, b(k) = 1 und c(k) = -1 jeweils zu erzeugen, so daß A zu A - N über die das partielle Produkt und die den modularen Subtrahierer erzeugende Einrichtung transfomiert wird, wenn A > N/2 oder 2A - N > o ist. Weiterhin weist in einer anderen Ausführungsform das modulare Multiplikationssystem gemäß der vorliegenden Erfindung auf: (a) eine erste Einrichtung (41) zum Transformieren von Daten A zu A - N, falls A ≤ N/2 ist, und zum Verteilen von Daten A, B und N, die über einen Eingangsanschluß eingegeben sind, jeweils; (b) eine zweite Einrichtung (43), die auf die erste Einrichtung anspricht, zum Speichern der Daten A, B und N, zum Erzeugen partieller Multiplikatoren b und eines partiellen Quotienten c innerhalb eines Bereichs von -r/2 ≤ b, c ≤ r/2 und partieller Reste R, und Ausführen von Übertrag-Sicherungs-Muliplizier- und Modulo-Additionen/Subtraktionen von partiellen Produkten bA und von modularen Subtrahierern cN, um den partiellen Rest R zu erhalten, jeweils; (c) eine dritte Einrichtung (47) zum Auswählen von Ausgangs-Bits des partiellen Rests R entsprechend einer Bit-Länge des parallelen Ausgangs-Anschlusses und zum Ausgeben der ausgewählten Bits; (d) eine vierte Einrichtung (49) zum Ausführen einer Übertrag-Propagations-Addition des erhaltenen, abschließenden Rests und zum Ausgeben einer Lösung von A · B Modulo N über einen Ausgangsanschluß; und (e) eine fünfte Einrichtung (45) zum Steuern von Operationen der ersten bis vierten Einrichtung.
Das Verfahren nach Baker kann die Menge an Daten, die zwischen den berechnenden Elementen und der Speichereinheit übertragen werden, reduzieren. In diesem Verfahren nach Baker ist es allerdings, da die Radix-Zahl 2 für Multiplizier-Additionen unterschiedlich von dieser 4 für Divisions- (Modular-) Subtraktionen ist, schwierig gewesen, merkbar die Berechnungsstufen zu verringern oder die Berechnungsgeschwindigkeit zu erhöhen.
Der Gedanke der vorliegenden Erfindung liegt darin, die Zahl von Multiplizier-Additions und Divisions- (Modular-) Subtraktionen auf der Basis derselben, höheren Radix- Zahl zu reduzieren. Zum Beispiel ist es, wenn eine Radix-Zahl 4 ausgewählt wird, da partielle Produkte und modulare Subtrahierern zwei Bits für zwei Bits berechnet werden können, wie in Fig. 1(C) dargestellt ist, möglich, die Zahl von berechnungsmäßigen Stufen von Additionen/Subtraktionen herunter auf die Hälfte des herkömmlichen Verfahrens zu reduzieren. Allgemein kann, wenn eine Radix-Zahl r ausgewählt wird, die Zahl von Stufen von Additionen und Subtraktionen herunter auf 1/log&sub2; r reduziert werden.
Wenn die vorliegende Erfindung mit dem Verfahren von Baker verglichen wird, wenden die beiden Verfahren eine ähnliche Verarbeitung an, wie beispielsweise diejenige, daß der partielle Rest durch Addieren eines partiellen Produkts (das eine Multiplizier-Additions-Stufe bildet) und eines modularen Subtrahierers (der eine modulare Subtraktions-Stufe bildet) zu dem partiellen Rest, erhalten als ein Zwischenergebnis während einer Berechnungsverarbeitung, aktualisiert wird.
In dem Verfahren nach Baker ist es allerdings, gerade wenn eine höhere Radix-Zahl so angenommen ist, wie sie ist, daß die System-Konfigurationen-Skalierung so bestimmt wird, um auf die modularen Subtraktionen basierend auf einer höheren Radix-Zahl 4 anwendbar zu sein, schwierig gewesen, die Berechnungsgeschwindigkeit in Proportion zu dem Hardware-Volumen zu erhöhen. Dies kommt daher; daß das Verfahren nach Baker versucht hat, das Problem in Bezug auf einen Bit-Überlauf von einem begrenzten Berechnungsbereich durch Erhöhen der Radix-Zahl auf 4 für nur die modularen Subtraktionen ohne Erhöhen der Radix-Zahl 2, die für die Multiplizier- Additionen gehalten wird, zu lösen.
Das Merkmal der vorliegenden Erfindung ist dasjenige, dieselbe irgendeine gegebene höhere Radix-Zahl für sowohl die partiellen Produkte als auch die modularen Subtrahierer durch die nachfolgenden Verfahren anzuwenden: (1) die modularen Subtrahierer werden zuvor auf der Basis der partiellen Produkte an der darauffolgenden Stufe bestimmt, um den absoluten Wert des partiellen Rests herunter auf einen Wert geringer als einen Modulus N zu reduzieren. Zum Beispiel wird dort, wo das partielle Produkt an der darauffolgenden Stufe groß ist, der partielle Quotient groß bestimmt, um den partiellen Rest an der darauffolgenden Stufe zu reduzieren; und (2) das am meisten signifikante Bit eines Multiplikanden A wird durch Ändern des Multiplikanden A von einem Bereich von [0, N - 1] zu [-N/2, N/2] eliminiert, um den absoluten Wert der partiellen Produkte zu reduzieren.
Das vorstehende erste Merkmal dient dazu, einen Bit-Überlauf von einem begrenzten, berechnungsmäßigen Bereich zu verhindern, und das zweite Merkmal ist eine notwendige Bedingung, um dieselbe Radix-Zahl für sowohl die partiellen Produkte als auch die modularen Subtrahierer anzupassen.
Zusammenfassend ist das Merkmal der vorliegenden Erfindung dasjenige, partielle Produkte und modulare Subtrahierer auf der Basis derselben, höheren Radix-Zahl zu erweitern und weiterhin die modularen Subtrahierer in Voraussicht einer Ausführung an einer darauffolgenden Stufe zu bestimmen. Allerdings werden keine Übertrag- Propagations-Addierer in dem System während Zwischenberechnungsstufen eingesetzt.
Bei der vorliegenden Erfindung kann deshalb die Anzahl von Addition und Subtraktion nach dem Stand der Technik durch Erweitern berechnungsmäßiger Operationen auf der Basis einer höheren Radix r reduziert werden. Mit anderen Worten werden Additionen und Subtraktionen einer Vielzahl von Modulus N zwischen die zwei Additionen und/oder Subtraktionen für partielle Produkte zwischengefügt, um die modulare Multiplikation in derselben Art und Weise wie durch das Verfahren nach Baker, dargestellt in Fig. 1(B), auszuführen. Bei der vorliegenden Erfindung ist es allerdings, da die Anzahl von Bits der Zwischen-Reste während der Berechnung innerhalb eines vorbestimmten, berechnungsmäßigen Bereichs auf der Basis irgendeiner gegebenen Radix r (r 2r', wobei r' eine ganze Zahl ist) begrenzt ist, das bedeutet, da Additionen/Subtraktionen durch Verschieben der Bits zu dem LSB durch r'-Bits ausgeführt werden, was unterschiedlich zu dem Verfahren von Baker ist, bei dem Additionen/Subtraktionen durch Verschieben eines Bits zu dem MSB hin ausgeführt weren, möglich, jede Addition und Subtraktion bei jeder der irgendeinen gegebenen r'-Bit- Länge (jedes Bit in dem Verfahren nach Baker) auszuführen. Deshalb ist es möglich, die Anzahl von Additionen und Subtraktionen für eine Multiplikation herunter auf 1/r'-mal zu reduzieren; mit anderen Worten ist es möglich, die berechnungsmäßige Geschwindigkeit um r'-mal verglichen mit dem Verfahren nach dem Stand der Technik zu erhöhen. Zusätzlich kann, da das System durch die einfachen und selben Zellen konfiguriert werden kann, das System vereinfacht werden.
Weiterhin ist es, da die zwei Additionen und/oder Subtraktionen simultan ausgeführt werden, was gegenüber dem Verfahren nach Baker unterschiedlich ist, wodurch die darauffolgende Verarbeitung durch Beobachten der sequentiell ausgeführten, momentanen Additions/Subtraktions-Ergebnisse bestimmt wird, möglich, die Geschwindigkeit zweimal zu erhöhen. Weiterhin kann, wenn das gesamte System innerhalb eines einzelnen LSI gebildet wird, da keine Daten-Stand-By-Verarbeitung erforderlich ist, das System bei einem cryptographischen System ausgezeichnet geheim ebenso wie in Bezug auf eine berechnungsmäßige Geschwindigkeit angewandt werden. Weiterhin kann das System einfach auf eine größere Skalierung durch Verbindung zusätzlicher Zellen in Serie erweitert werden.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Die Merkmale und Vorteile des modularen Multiplikationsverfahrens und des Systems gemäß der vorliegenden Erfindung werden deutlicher aus der nachfolgenden Beschreibung ersichtlich werden, die in Verbindung mit den beigefügten Zeichnungen vorgenommen wird, in denen:
Fig. 1(A) zeigt ein berechnungsmäßiges Bit-Anordnungs-Diagramm zum Unterstützen bei der Erläuterung des herkömmlichen Verfahrens zum Ausführen von A · B mod N in 7-Bit binären Zahlen;
Fig. 1(B) zeigt ein ähnliches, berechnungsmäßiges Bit-Anordnungs-Diagramm zum Unterstützen bei der Erläuterung des Verfahrens nach Baker zum Ausführen von A · B mod N in 7-Bit binären Zahlen;
Fig. 1(C) zeigt das ähnliche, berechnungsmäßige Bit-Anordnungs-Diagramm zum Unterstützen bei der Erläuterung des erfindungsgemäßen Verfahrens zum Ausführen von A · B mod N in 7-Bit binären Zahlen;
Fig. 2(A) zeigt ein Blockdiagramm, das eine Basis-System-Konfiguration zum Unterstützen bei der Erläuterung des Konzepts des Verfahrens zum Ausführen von A · B mod N der vorliegenden Erfindung darstellt;
Fig. 2(B) zeigt ein Blockdiagramm, das einen Parameter-Generator darstellt, der in dem System, das in Fig. 2(A) dargestellt ist, eingesetzt ist;
Fig. 3 zeigt ein Blockdiagramm, das eine gesamte System-Konfiguration zum Unterstützen bei der Erläuterung des Verfahrens zum Ausführen einer A · B mod N Berechnung von n-Bit binären Zahlen darstellt;
Fig. 4(A) zeigt ein Blockdiagramm, das eine erste Ausführungsform einer Zellen-Konfiguration darstellt, die in dem System, dargestellt in Fig. 3, eingesetzt ist;
Fig. 4(B) zeigt ein Blockdiagramm, das eine erste Modifikation eines Übertrag-Sicherungs-Addierers darstellt, der in der Zelle eingesetzt ist, die in Fig. 4(A) dargestellt ist;
Fig. 4(C) zeigt ein Bit-Anordnungs-Diagramm zum Unterstützen bei der Erläuterung eines Beispiels von A · B mod N Berechnungs-Stufen, ausgeführt durch Zellen, die in den Fig. 4(A) und 4(B) dargestellt sind;
Fig. 5(A) zeigt ein Blockdiagramm, das eine zweite Ausführungsform der Zellen-Konfiguration darstellt, die in dem System, dargestellt in Fig. 3, eingesetzt ist;
Fig. 5(B) zeigt ein Blockdiagramm, das eine zweite Modifikation des Übertrag-Sicherungs-Addierers darstellt, eingesetzt in der Zelle, die in Fig. 5(A) dargestellt ist;
Fig. 6(A) zeigt ein basismäßiges, konzeptmäßiges Robertson-Diagramm zum Unterstützen bei der Erläuterung des Verfahrens zum Auswählen eines partiellen Quotienten;
Fig. 6(B) zeigt ein erstes Beispiel einer Berechnung von A · B mod N in 6-Bit binären Zahlen (oder dezimalen Zahlen), um ein Verständnis des Verfahrens zum Bestimmen des partiellen Quotienten an der dritten Stufe R(3) zu erleichtern;
Fig. 7(A) zeigt ein modifiziertes Robertson-Diagramm, wenn die Radix-Zahl r ist;
Fig. 7(B) zeigt ein anderes, modifiziertes Robertson-Diagramm, wenn die Radix-Zahl 4 ist;
Fig. 7(C) zeigt ein beispielhaftes, modifiziertes Robertson-Diagramm, das während einer berechnungsmäßigen Verarbeitungsstufe erhalten ist, wenn die Radix-Zahl 4 ist;
Fig. 8 zeigt eine Tabelle zum Vergleich zwischen dem Verfahren nach Baker und dem erfindungsgemäßen Verfahren in der Zahl von Stufen, die für Multiplizier- und Modular-Additionen/Subtraktionen erforderlich sind;
Fig. 9(A) zeigt ein Blockdiagramm, das eine dritte Ausführungsform der Zellenkonfiguration darstellt, die in dem System eingesetzt ist, das in Fig. 3 dargestellt ist, wobei der partielle Rest in einer redundanten Form dargestellt ist;
Fig. 9(B) zeigt ein Blockdiagramm, das eine vierte Ausführungsform der Zellenkonfiguration darstellt, die in dem System eingesetzt ist, das in Fig. 3 dargestellt ist, wobei der partielle Rest in redundanter Form so dargestellt ist, daß er für eine Ae mod N Berechnung (modulare Potenzierungsfunktion) geeignet ist;
Fig. 10 zeigt ein berechnungsmäßiges Bit-Anordnungs-Diagramm zum Unterstützen bei der Erläuterung des erfindungsgemäßen Verfahrens von A · B in 8-Bit binären Zählen;
Fig. 11 zeigt eine Referenz-Tabelle nach dem Stand der Technik zum Auswählen von zwei Funktionen (fc, fs) in Kombination, um partielle Multiplikatoren b(k) zu erzeugen;
Fig. 12 zeigt ein Blockdiagramm, das eine Basis-System-Konfiguration zum Unterstützen bei der Erläuterung des Konzepts des Verfahrens zum Ausführen von A · B der vorliegenden Erfindung darstellt;
Fig. 13 zeigt ein Bit-Anordnungs-Diagramm von zwei Multiplikatoren Bs und Bc, wenn in redundanter Form dargestellt wird;
Fig. 14 zeigt eine Referenz-Tabelle der vorliegenden Erfindung zum Auswählen von zwei Funktionen (fc, fs) in Kombination, um partielle Multiplikatoren b(k) zu erzeugen;
Fig. 15(A) zeigt ein Blockdiagramm, das eine erste Modifikation des Übertrag-Sicherungs-Addierers darstellt, der in dem System eingesetzt ist, wie es in Fig. 12 dargestellt ist, wobei das Multiplikations-Ergebnis oder der Rest R wieder für die darauffolgende Multiplikation als A · R verwendet wird;
Fig. 15(B) zeigt ein Blockdiagramm, das eine zweite Modifikation des Übertrag-Sicherungs-Addierers darstellt, eingesetzt in dem System, das in Fig. 12 dargestellt ist, wobei das Multiplikations-Ergebnis oder der Rest R wieder für die darauffolgende Multiplikation als R · R verwendet wird;
Fig. 16 zeigt ein Beispiel nach dem Stand der Technik eines Übertrag-Sicherungs- Addierers, der aus zwei Voll-Addierern aufgebaut ist;
Fig. 17 zeigt ein Flußdiagramm, das eine Basis-Prozedur des Verfahrens zum Ausführen von A · B mod N gemäß der vorliegenden Erfindung darstellt;
Fig. 18(A) zeigt ein Flußdiagramm, das eine erste Modifikation zum Transformieren eines Multiplikanden A innerhalb eines kleineren, berechnungsmäßigen Bereichs darstellt;
Fig. 18(B) zeigt ein Flußdiagramm, das eine zweite Modifikation zum Transformieren eines Multiplikanden A innerhalb eines kleineren, berechnungsmäßigen Bereichs darstellt;
Fig. 18(C) zeigt ein Flußdiagramm, das eine dritte Modifikation eines ungefähren Transformierens eines Multiplikanden A, wenn ein kleinerer, berechnungsmäßiger Bereich vorhanden ist, auf der Basis von höher signifikanten Bits von A und N darstellt;
Fig. 19(A) zeigt ein Flußdiagramm, das eine erste Modifikation eines Einstellens einer Zahl n von Bits von einem Modulus N darstellt;
Fig. 19(B) zeigt ein Flußdiagramm, das eine zweite Modifikation eines Einstellens einer Zahl n von Bits von einem Modulus N darstellt;
Fig. 20(A) zeigt ein Flußdiagramm, das eine erste Modifikation eines Initialisierens eines partiellen Rests R darstellt;
Fig. 20(B) zeigt ein Flußdiagramm, das eine zweite Modifikation eines Initialisierens eines partiellen Rests R = Rs + 2Rc darstellt, dargestellt in redundanter Form;
Fig. 21(A) zeigt ein Flußdiagramm, das eine erste Modifikation eines Aktualisierens eines partiellen Rests R und eines Bildens eines partiellen Multiplikators b und eines partiellen Quotienten c darstellt;
Fig. 21(B) zeigt ein Flußdiagramm, das eine zweite Modifikation eines Aktualisierens R und eines Bildens von b und c darstellt;
Fig. 22(A) zeigt ein Flußdiagramm, das eine erste Modifikation eines Transformierens eines abschließenden Rests R zu einer Lösung von A · B mod N darstellt;
Fig. 22(B) zeigt ein Flußdiagramm, das eine zweite Modifikation eines Transformierens eines abschließenden Rests R zu einer Lösung von A · B mod N darstellt;
Fig. 23(A) zeigt ein Flußdiagramm, das eine erste Modifikation zum Bilden eines partiellen Multiplikators b, wenn die Radix-Zahl r ist, darstellt;
Fig. 23(B) zeigt ein Flußdiagramm, das eine zweite Modifikation eines Bildens eines partiellen Multiplikators b, wenn die Radix-Zahl 4 ist, darstellt;
Fig. 23(C) zeigt ein Flußdiagramm, das eine dritte Modifikation eines Bildens eines partiellen Multiplikators b auf der Basis von zwei Funktionen fs und fc darstellt, wenn ein Multiplikator B in redundanter Form dargestellt ist und die Radix-Zahl 4 ist;
Fig. 23(D) zeigt ein Flußdiagramm, das eine vierte Modifikation eines Bildens eines partiellen Multiplikators b auf der Basis von zwei Funktionen fs und fc darstellt, ausgewählt unter Bezug auf eine Tabelle;
Fig. 23(E) zeigt ein Flußdiagramm, das eine fünfte Modifikation eines Bildens eines partiellen Multiplikators b auf der Basis von zwei Funktionen fs und fc, berechnet durch Hardware, darstellt;
Fig. 24(A) zeigt ein Flußdiagramm, das eine erste Modifikation eines Bildes eines partiellen Quotienten c auf der Basis von Grenz-Indizes l darstellt;
Fig. 24(B) zeigt ein Flußdiagramm, das eine zweite Modifikation eines Bildens eines partiellen Quotienten c auf der Basis von Grenz-Indizes darstellt, bestimmt ungefähr durch höher signifkante Bits von A, N und R; und
Fig. 24(C) zeigt ein Flußdiagramm, das eine dritte Modifikation eines Bilden eines partiellen Quotienten c auf der Basis von Grenz-Indizes darstellt.

DETAILLIERTE BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORMEN

Ausführungsformen des modularen Multiplikationsverfahrens und des Systems gemäß der vorliegenden Erfindung werden im Detail nachfolgend unter Bezugnahme auf die beigefügten Zeichnungen beschrieben werden. Die basismäßige, konzeptmäßige System-Konfiguration und das Verfahren werden nachfolgend unter Bezugnahme auf die Fig. 1(C), 2(A), 2(B) und 3 beschrieben werden.
Die modulare Multiplikation ist diejenige, A · B Modulo (mod) N zu berechnen, wobei A einen Multiplikanden bezeichnet; B einen Multiplikator bezeichnet und N einen Modulus bezeichnet. In der vorstehenden Berechnung kann grundsätzlich der abschließende Rest durch wiederholtes Ausführen der nachfolgenden Formeln erhalten werden:
Rnew ← rRold + bA - cN .... (A)
Rnew ← r(Rold - cN) + bA .... (B)
wobei Rnew den aktualisierten oder darauffolgenden, partiellen Rest bezeichnet; wobei Rold den momentanen, partiellen Rest bezeichnet; wobei ← die Substitution bezeichnet; wobei r die Radix-Zahl bezeichnet; wobei b den partiellen Multiplikator bezeichnet, der dann erhalten wird, wenn der Multiplikator B auf der Basis einer r-Notation erweitert wird; wobei c den partiellen Quotienten bezeichnet, der durch Vergleichen von Grenz-Indizes l (wird später beschrieben), erhalten durch A, N, b und r, mit dem partiellen Rest R' auf der Basis eines modifizierten Robertson-Diagramms (später beschrieben) bestimmt wird. Um es detaillierter anzugeben, wird in der ersten Formel (A), rRold + bA durch R' dargestellt; die Grenz-Indizes li werden durch den partiellen Multiplikator b der darauffolgenden Stufe bestimmt; und der partielle Quotient c wird durch li bestimmt. In der zweiten Formel (B) wird Rold durch R' dargestellt; li wird durch den momentanen, partiellen Multiplikator b bestimmt; und der partielle Quotient c ist vorbestimmt worden.
Fig. 1(C) zeigt ein Beispiel eines berechnungsmäßigen Bit-Anordnungs-Diagramms zur Unterstützung bei der Erläuterung einer Berechnung von A · B mod N (39 · 93 mod 121) durch die vorliegende Erfindung in 7-Bit binäre Zahlen und eine Radix-Zahl von 4 im Vergleich mit dem herkömmlichen Verfahren und dem Verfahren nach Baker, dargestellt in den Fig. 1(A) und 1(B). Hierbei sollte angemerkt werden, daß das herkömmliche Verfahren 7 Multiplizier-Additionen von 7 partiellen Produkten basierend auf einer Radix-Zahl 2 und 7 Divisions-Subtraktionen von 7 modularen Subtrahierern basierend auf einer Radix-Zahl von 2 erfordert; das Verfahren nach Baker erfordert 6 Multiplizier-Additionen von 6 partiellen Produkten basierend auf einer Radix-Zahl von 2 und 7 Divisions-Subtraktionen von 7 modularen Subtrahierern basierend auf einer Radix-Zahl von 4; und das erfindungsgemäße Verfahren erfordert nur 3 Multiplizier-Additionen/Subtraktionen von 3 partiellen Produkten basierend auf einer Radix-Zahl von 4 und 4 Divisions-Additionen/Subtraktionen von 4 modularen Subtrahierern basierend auf einer Radix-Zahl von 4.
Das Merkmal des erfindungsgemäßen Verfahrens ist dasjenige, dieselbe höhere Radix-Zahl r für sowohl die partiellen Multiplikatoren b als auch den partiellen Quotienten innerhalb eines Bereichs von -r/2 ≤ b, c ≤ r/2 anzupassen, um merkbar die Anzahl von Berechnungsstufen (Additionen/Subtraktionen) zu reduzieren, wie dies in weiterem Detail nachfolgend beschrieben ist.
Die Fig. 2(A) und 2(B) stellen ein konzeptmäßiges Blockdiagramm zum Ausführen des berechnungsmäßigen Verfahrens der vorliegenden Erfindung dar.
Das modulare Multiplikationssystem, das in Fig. 2(A) dargestellt ist, weist grob gesagt einen Registerblock 1, einen Steuerblock 2 und einen Operationsblock 3 auf. Der Registerblock 1 weist ein A-Register 11 zum Speichern einer Eingabe-Variablen A (Multiplikand), ein B-Register 13 zum Speichern einer Eingabe-Variablen B (Multiplikator), ein N-Register 15 zum Speichern einer Eingabe-Variablen N (Modulus) und ein R-Register 17 zum Speichern von Arbeits-Variablen R (partieller Rest) auf, das aus einem Rsum-Register 17s zum Speichern einer Summe von R und einem Rcarry-Register zum Speichern eines Übertrags von R aufgebaut ist.
Der Steuerblock 2 weist einen N-Normalisierer 21 zum Normalisieren der Variablen N, einen Steuer-Parameter-Generator 23 und eine Sequenz-Steuereinheit 23 zum Steuern der gesamten, sequentiellen Operation des Systems auf.
Wie in Fig. 2(B) dargestellt ist, weist der Steuer-Paramater-Generator 23 einen b-Generator 23A zum Erzeugen partieller Multiplikatoren b auf der Basis von B, wie später in weiterem Detail unter Bezugnahme auf die Fig. 23(A) bis (E) beschrieben ist; einen c-Generator 23B zum Erzeugen partieller Quotienten (Modulus) c auf der Basis von A, N, R, b und l (Grenz-Indizes), wie später in weiterem Detail unter Bezugnahme auf die Fig. 24(A) bis (C) beschrieben ist; einen Grenz-Index-Generator 23C zum Erzeugen von Grenz-Indizes l auf der Basis von A, N und b und zum Zuführen der erzeugten Grenz-Indizes l zu dem c-Generator 23B, wie später im Detail unter Bezugnahme auf die Fig. 24(A) und (B) beschrieben ist; und einen Komparator 23D zum Vergleichen A und N/2, um dem b-Generator 23A zu ermöglichen, b(k) = 1 zu erzeugen, und um dem c-Generator zu ermöglichen, (ck) = -1 zu erzeugen, jeweils so, daß A zu A - N durch den bA-Generator 31 und den cN-Generator 33 transformiert werden kann, wenn gilt A ≤ N/2 oder 2A - N < 0; auf.
Der Operationsblock 3 weist einen bA-Generator 31 zum Erzeugen partieller Produkte bA auf der Basis von A und b; einen cN-Generator 33 zum Erzeugen modularer Subtrahierer cN auf der Basis von N und c; und einen Generator 35 für ein aktualisiertes R zum Erzeugen eines aktualisierten Rests R(k - 1) auf der Basis der partiellen Reste R(k), wobei k die Zahl von Verarbeitungsstufen von k zu o bezeichnet; einen Übertrag-Sicherungs-Addierer 37 zum Aktualisieren von Rold zu Rnew auf der Basis von bA, cN und R, Bit für Bit, ohne Übertrag-Propagation; und einen Übertrag-Propagations-Addierer 39 zum Ausgeben eines abschließenden Rests R(0) als eine Lösung von A · B mod N, auf.
In Fig. 2(A) wird ein Eingabe-Multiplikand A, eingegeben in das A-Register 11, zu dem Komparator 23D des Parameter-Generators 23 des Steuerblocks 2 zugeführt. Falls A > N/2 ist, arbeitet der Parameter-Generator 23 so, daß der bA-Generator 31 A ausgibt; der cN-Generator 33 gibt -N aus; und der Generator 35 für das aktualisierte R gibt 0 aus. Deshalb gibt der Übertrag-Propagations-Addierer 39 ein neues A = A - N über den Übertrag-Sicherungs-Addierer 37 aus. Das aktualisierte A wird in dem A-Register 11 wieder so gespeichert, daß A von einem Bereich 0 ≤ A < N zu einem Bereich -N/2 ≤ A < N/2 transformiert werden kann, um zu verhindern, daß Bits aus einem vorbestimmten, berechnungsmäßigen Bereich überlaufen.
Das R-Register 17 zum Halten partieller Reste R wird durch die Sequenz-Steuereinheit 25 initialisiert. Deshalb werden die Variablen A, B und R, gespeichert in dem A- Register 11, dem B-Register 13 und dem R-Register 17, zu dem Parameter-Generator 23 zugeführt, um b, c und R zu erzeugen. Weiterhin geben der bA-Generator 31, der cN-Generator 33 und der R-Generator 35 bA, cN und R jeweils aus. Diese Werte werden zu dem Übertrag-Sicherungs-Addierer 37 Bit für Bit addiert und die Summe davon wird in dem R-Register 17 als ein neuer, partieller Rest R gespeichert. Die vorstehenden Schritte werden n-mal entsprechend der Zahl von Bits von N wiederholt.
Danach geben, wenn der abschließende Rest R in dem R-Register 17 zu dem Parameter-Generator 23 des Steuerblocks 2 zugeführt wird, der bA-Generator 31, der cN-Generator 33 und der R-Generator 35 0, N oder 0 und R jeweils aus. Diese Werte werden durch den Übertrag-Sicherungs-Addierer 37 addiert und dann von dem Übertrag-Propagations-Addierer 39 durch Propagieren eines Übertrags in Sequenz, beginnend von dem am wenigsten signifikanten Bit, über einen Ausgangs-Anschluß ausgegeben. Zusammenfassend wird N gemäß dem Wert von R addiert und R wird innerhalb eines Bereichs 0 ≤ R < N für eine modulare Multiplikation transformiert.
Wie in Fig. 1(C) dargestellt ist, werden, wenn die Radix-Zahl r bei der vorliegenden Erfindung ist, Additionen oder Subtraktionen ganzzahliger Vielfacher für modulare Subtraktionen zwischen den Additionen und Subtraktionen für partielle Produkte zwischenberechnet; die absoluten Werte des partiellen Rests R während einer Berechnung werden innerhalb eines vorbestimmten, berechnungsmäßigen Bereichs bestimmt, um die Zahl von berechnungsmäßigen Stufen herunter zu der Zahl n von Bits von N zu reduzieren. Deshalb ist keine Daten-Stand-By-Steuerung erforderlich; die Geschwindigkeit kann erhöht werden; die Schaltkreis-Skalierung kann reduziert werden; und das Schaltkreis-Design kann vereinfacht werden.
In Verbindung hiermit hat das Verfahren nach Baker vorgeschlagen, daß Additionen für eine Multiplikation und Subtraktionen für eine Division in Sequenz ausgeführt werden, wie in Fig. 1(B) dargestellt ist. Allerdings ist die berechnungsmäßige Geschwindigkeit der vorliegenden Erfindung höher als diejenige von Baker. Dies kommt daher, daß bei der vorliegenden Erfindung der Multiplikand A zuvor transformiert wird und weiterhin die Addition oder Subtraktion für eine modulare Subtraktion zuvor auf der Basis des Werts eines partiellen Produkts an der darauffolgenden Stufe eingestellt wird, bevor zu dem partiellen Produkt addiert wird. Deshalb ist das Verfahren nach Baker durch Vielfach-Additionen basierend auf Radix 2 und Modular-Additionen/Subtraktionen basierend auf Radix 4 ausgeführt, so daß dann, wenn die Zahl von Bits eines binären Modulus N n ist, n-fache Operationen erforderlich sind. Im Gegensatz hierzu ist es bei der vorliegenden Erfindung, da die Multiplikation und die Division durch Multiplizier- und Modular-Additionen/Subtraktionen basierend auf derselben Radix 4 ausgeführt werden können, zum Beispiel möglich, die Operationsvorgänge auf die Hälfte zu reduzieren oder die Berechnungsgeschwindigkeit ums Zweifache zu erhöhen. Allgemein kann, falls die Radix-Zahl r 2r' ist (r' ≥ 1), die Zahl von Operationen herunter auf 1/r'-mal reduziert werden.
Fig. 3 zeigt ein Blockdiagramm, das die gesamte Konfiguration der modularen Multiplikation der Basis-Ausführungsform darstellt, wobei die Radix-Zahl 4 ist. Dieses System weist eine erste Einrichtung für einen Eingabe-Distributer-Schaltkreis 41 zum Aufnehmen von Eingabe-Variablen A, B, N über einen parallel angeordneten Eingangs-Anschluß und zum Verteilen dieser Daten Bit für Bit; eine zweite Einrichtung aus Operations-Abschnitten 43, die aus einer Vielzahl von in Serie verbundenen Zellen 43a, 43b... 43n + 3 zum Ausführen von Additionen, Subtraktionen, Bit-Verschiebungen, usw., aufgebaut sind; eine dritte Einrichtung eines Ausgabe-Selektor-Schaltkreises 47 für ein sequentielles Selektieren und Ausgeben von Rsum und Rcarry gespeichert in dem Operations-Abschnitt 43, beginnend von dem am wenigsten signifikanten Bit gemäß der Bit-Länge eines parallel angeordneten Ausgangs-Anschlusses; eine vierte Einrichtung eines Addierers 49, der einen Ausgangs-Formungs- Schaltkreis zum Ausführen eines abschließenden, berechnungsmäßigen Ergebnisses von R = Rsum + 2 Rcarry auf der Basis der internen Ausgänge von dem Ausgangs-Selektor-Schaltkreis 47 und zum Ausgeben von Daten über den Ausgangs- Anschluß; und eine fünfte Einrichtung einer Steuereinheit 45 zum Steuern der gesamten System-Operation; auf.
Die Steuereinheit 45 speichert einen Multiplikator B und bildet einen partiellen Multiplikator b, liest Reste Rsum und Rcarry, gespeichert in den Zellen, die für höher signifikante Bits angeordnet sind, um einen partiellen Quotienten c zu bilden, und aktualisiert die Werte in den Registern durch neue Rsum und Rcarry, nachdem die gesamte Verarbeitung abgeschlossen worden ist. Weiterhin wird, wenn ein Übertrag von einer Ausgangs-Bit-Länge übergelaufen ist, der Überlauf-Übertrag gespeichert und zu niedriger signifikanten Bits der darauffolgenden Eingabe-Daten durch den Addierer, der einen Ausgangs-Formungs-Schaltkreis 49 umfaßt, addiert.
Fig. 4(A) zeigt ein Blockdiagramm, das eine erste Ausführungsform jeder Zelle aufweist, die in dem modularen Multiplikator-System gemäß der vorliegenden Erfindung eingesetzt ist, die der Zelle 43i entspricht, die in Fig. 3 dargestellt ist, zum Ausführen der erwähnten Formel (A).
Die Zelle, die in Fig. 4(A) dargestellt ist, weist ein N-Register 51 zum Halten von N, ein A-Register 53 zum Halten von A, ein Rcarry Register 55 zum Halten von Rcarry ein Rsum Register 57 zum Halten von Rsum, einen bA-Generator 59 zum Bilden eines partiellen Produkts bA, einen cN-Generator 61 zum Bilden eines modularen Subtrahierers cN und einen 5-Eingangs-Übertrag-Sicherungs-Addierer 63 auf.
Wenn die Radix-Zahl r 4 ist, invertiert der bA-Generator 59 und gibt A[i - 1] aus, falls b = -2 ist, invertiert er und gibt aus A[i], falls b = -1, gibt er eine logische Null aus, falls b = 0, gibt er aus A[i], falls b = 1, und gibt aus A[i - 1], falls b = 2 ist. Weiterhin liefert der cN-Generator 61 dieselbe Funktion wie mit dem bA-Generator 59, wobei i ein i-tes Bit von dem am wenigsten signifikanten Bit bezeichnet.
Wie in Fig. 4(B) dargestellt ist, weist der Fünf-Eingangs-Übertrag-Sicherungs-Addierer 63 zwei Voll-Addierer 65 und 67 auf. In Bezug auf die Zahl der Additionen führt dieser 5-Eingangs-Übertrag-Sicherungs-Addierer 63 zwei Additionen simultan aus, das bedeutet R = 4R + bA - cN kann zur selben Zeit durch diesen Addierer 63 ausgeführt werden.
Bei dieser Erfindung sind die 5-Eingangs-Übertrag-Sicherungs-Addierer 63, die von der Zellen-Zahl (n + 3) zu (n - m + 1 ) angeordnet sind, so aufgebaut, um 4R + bA auf der Basis der Zwischenergebnisse cI' zu addieren; und R(i)midsum, um c zu bilden. m wird durch den Grad einer Genauigkeit bestimmt. Zum Beispiel ist, falls r = 4 gilt, m mehr als 5 erforderlich.
Durch das System der ersten Ausführungsform, wie sie vorstehend unter Bezugnahme auf die Fig. 4(A) und (B) beschrieben ist, ist es möglich, die erste Ausführungsform des modularen Multiplikations-Verfahrens (A · B mod N) gemäß der vorliegenden Erfindung wie folgt auszuführen. Dieses Verfahren ist hauptsächlich von den Bit- Verschiebungs-Operationen von Registern abhängig, wie in Fig. 4(C) dargestellt ist.

A · B mod N (1. Verfahren)

Schritt 1 (Transformation)

Falls N < 2A, A ← A - N

Schritt 2 (N Normalisierung)

Verschiebe N und A nach links, bis MSB (das signifikanteste Bit) von N-Register 1 wird.

Schritt 3 (Initialisierung)

R = 0

Schritt 4 (Wiederholung)

(Sequentielle Subtraktion von k = n/2 + 1 bis 1)
c ← fc (4R + b(k)A, b (k - 1), A)
R ← 4R + b(k)A + cN

Schritt 5 (Abschließende Verarbeitung)

Falls R < 0, R ← R + N

Schritt 6 (Rückführen von N)

A ← Rsum + 2Rcarry
Verschiebe N und A nach rechts durch dieselben Bits wie in Schritt 2, um A zu erhalten.

Anmerkung 1:

b(k) = -2B[2k] + B[2k - 1] + B[2k - 2]
wobei B[i] > 0; i > n oder 0 ≥ i; und B[i] = 1; i > n, falls B ein Minusvorzeichen besitzt.

Anmerkung 2:

Das Verfahren einer Entscheidung einer fc-Funktion wird später erläutert.
In dem vorstehenden ersten Verfahren wird R = Rsum + 2Rcarry definiert. Die Additionen werden durch den Übertrag-Sicherungs-Addierer mit Ausnahme der abschließenden Addition ausgeführt. Zum Beispiel wird, um R = R + bA zu erhalten, ein neues Rsum als
Rsum 2Rcarry bA,
und ein neues Rcarry wird als ein neues Rcarry bestimmt:
{Rsum · 2Rcarry} v {2Rcarry · (bA)} v {(bA) · Rsum}
wobei die Exklusiv-ODER-Operation bezeichnet; wobei · das logische Produkt (UND-Operation) bezeichnet; wobei V die logische Summe (Inklusiv-ODER-Operation) bezeichnet. In diesem Fall ist es möglich, nur die höher signifikanten Bits von N, A, R für eine Approximation zu verwenden. Das- bedeutet, Ntop, Atop und Rtop sind anstelle von N, A und R verwendbar. Weiterhin bezeichnet B[i] ein i-tes Bit von LSB.
Bei diesem ersten Verfahren wird der N-Normalisierungs-Schritt so addiert, daß die modulare Multiplikation durch Fixieren von der Register-Bit-Länge ausgeführt werden kann. In Fig. 2(A) wird die N-Normalisierung durch den N-Normalisierer 21 des Steuerblocks 2 durch sequentielles Verschieben des N-Registers 15 und des A-Registers 11 nach links ausgeführt, bis das am meisten signifikante Bit von N 1 wird.
Weiterhin zeigt der Schritt 6 an, daß der Übertrag des Übertrag-Sicherungs-Additions-Ergebnisses so propagiert wird, um ein abschließendes Ergebnis zu erhalten, und weiterhin wird die N-Normalisierung in Schritt 2 zu dem originalen N zurückgeführt.
Fig. 5(A) zeigt ein Blockdiagramm, das eine zweite Ausführungsform darstellt, wobei jede Zelle in dem modularen Multiplikations-System gemäß der vorliegenden Erfindung eingeschlossen ist, was der Zelle 43i entspricht, dargestellt in Fig. 3, zum Ausführen der vorstehend erwähnten Formel (B).
Die Zelle, dargestellt in Fig. 5(A), weist einen 5-Eingangs-Übertrag-Sicherungs- Addierer 69 auf, wie in Fig. 5(B) dargestellt ist, anstelle des Übertrag-Sicherungs-Addierers 63, der in Fig. 4(A) dargestellt ist. Allerdings ist es auch möglich, den 5-Eingangs-Übertrag-Sicherungs-Addierer 63 in der Zelle zu verwenden, die in Fig. 5(A) dargestellt ist. Weiterhin wird das A-Register 53 um zwei Bit verschoben, was gegenüber demjenigen, was in Fig. 4(A) dargestellt ist, unterschiedlich ist, wobei dies daher kommt, daß ein 4-faches bA nicht erforderlich ist.
Der 5-Eingangs-Übertrag-Sicherungs-Addierer 69, dargestellt in Fig. 5(A), weist zwei Halb-Addierer 71 und 73, einen Voll-Addierer 75, zwei logische ODER-Gatter 77 und 79 und ein logisches UND-Gatter 81 auf. Dieser 5-Eingangs-Übertrag-Sicherungs- Addierer 69 führt zwei Additionen simultan aus, das bedeutet, er berechnet R = 4(R - cN) + bA. Da der Voll-Addierer 65 der ersten Ausführungsform, dargestellt in Fig. 4(B), durch zwei Halb-Addierer 71 und 73 ersetzt wird, kann die Verzögerungszeit auf 3/4 des Addierers 65 für die erste Ausführungsform, dargestellt in Fig. 4(B), reduziert werden.
Bei dieser zweiten Ausführungsform ist es, da c zu Beginn der Berechnung bestimmt wird, möglich, die Schaltkreise, wie sie in Fig. 5(B) dargestellt sind, einzusetzen, die einfach in der Schaltkreis-Skalierung und hoch in der Berechnungsgeschwindigkeit sind.
Durch das System der zweiten Ausführungsform, dargestellt in den Fig. 5(A) und 5(B), ist es möglich, die zweite Ausführungsform der modularen Multiplikation (A · B mod N) gemäß der vorliegenden Erfindung auszuführen. Der erste und der zweite Schritt dieser zweiten Ausführungsform sind dieselben wie diejenigen der ersten Ausführungsform.

A · B mod N (2. Verfahren)

Schritt 1 (Transformation)

Falls N < 2A, A ← A - N

Schritt 2 (N Normalisierung)

Verschiebe N und A nach links, bis MSB von N 1 wird.

Schritt 3 (Initialisierung)

R = 0, c = 0

Schritt 4 (Wiederholung)

(Sequentielle Subtraktion von k = n/2 + 1 bis 1)
R ← 4 (R - cN) + b(k)A
c ← fc (R, b(k - 1), A)

Schritt 5 (Abschließende Verarbeitung)

R = R - cN
Falls R < 0, R = R + N

Schritt 6 (Rückführen von N)

A = Rsum + 2Rcarry
Verschiebe N und A nach rechts durch dieselben Bits wie in Schritt 2, um A zu erhalten.

Anmerkung 1:

b(k) = -2B[2k] + B[2k - 1] + B[2k - 2]
wobei B[i] > 0; i > 0 oder 0 ≥ i; und B[i] = 1; i > n, falls B ein Minusvorzeichen besitzt.

Anmerkung 2:

Das Verfahren einer Entscheidung einer fc-Funktion wird später erläutert.
Diese zweite Ausführungsform ist mathematisch äquivalent zu der ersten Ausführungsform. Bei dieser ersten Ausführungsform nimmt es allerdings, da die Summe (4R + A) in Schritt 4 für beide aktualisierte c und R gemäß dem Fall verwendet wird, viel Zeit in Anspruch, um c zu bestimmen. Bei dieser zweiten Ausführungsform wird allerdings die simultane Verarbeitung durch wiederholtes Verzögern des partiellen, modularen Subtrahierers cN Bit für Bit ermöglicht. Allerdings erhöht sich die Anzahl von Additionen in der abschließenden Verarbeitung einmal.
Das Verfahren eines Entscheidens der Funktion fc (R, b, a) wird nachfolgend beschrieben:

fc (R, b, a) (1. Entscheidungs-Verfahren)

Schritt 1 (gemäß den Fällen)

Falls Rtop < 0, schreitet die Steuerung zu Schritt 3 fort.

Schritt 2 (falls R ≥ 0)

fc ← 0
Falls Rtop > Ntop, Rtop ← Rtop - Ntop, und fc ← 1.
Fallst l&sub1; · Ntop < Rtop, fc ← fc + 1.
Steuerung schreitet zu Schritt 4 fort.

Schritt 3 (falls R < 0)

fc ← 0, Rtop ← Rtop
Falls Rtop > Ntop, Rtop ← Rtop - Ntop, und fc ← 1.
Falls l&submin;&sub1; Ntop < Rtop, fc ← fc + 1
fc ← -fc.

Schritt 4

Ende Anmerkung 1. Grenz-Indizes von l&sub1; und l&submin;&sub1;
wobei die oberen Zeichen von &mnplus; und ± dann verwendet werden, wenn ab > 0 gilt, und die unteren Vorzeichen davon dann verwendet werden, wenn ab < 0 gilt.

Anmerkung 2:

l' und l" werden gemäß A nach Schritt 2 wie folgt bestimmt:
l' = 0 ··· A/N < 1/8
l' = 1 ··· 1/8 ≤ A/N < 3/8
l' = 2 ··· 3/8 ≤ A/N (≤ 1/2)
l" = 0 ··· A/N < 1/16
l" = 1 ··· 1/16 ≤ A/N < 3/16
l" = 2 ··· 3/16 ≤ A/N < 5/16
l" = 3 ··· 5/16 ≤ A/N < 7/16
l" = 4 ··· 7/16 ≤ A/N (< 1/2)
Bei diesem ersten Entscheidungsverfahren wird der Wert (R + bA/4)/N so gesteuert, um innerhalb eines vorbestimmten Bereichs von -9/16 bis 9/16 zu liegen. Zusätzlich wird A/N gemäß den zwei Nennern 8 und 16 klassifiziert, um die Grenz-Indizes l für einen Vergleich zu vereinfachen. In diesem Fall ist es ausreichend, 6 höher signifikante Bits von N mit l zu vergleichen.

fc (R, b, a) (2. Entscheidungs-Verfahren)

Schritt 1 (gemäß den Fällen)

Falls Rs < 0, schreitet die Steuerung zu Schritt 3 fort.

Schritt 2 (falls R ≥ 0)

fc ←

0

Falls Rtop > Ntop, Rtop ←

Rtop - Ntop, und fc ←

1.

Falls l&sub1; · Ntop < Ntop, fc ←

fc + 1.

Steuerung schreitet zu Schritt 4 fort.

Schritt 3 (falls R < 0)

fc ← 0, Rtop ← Rtop
Falls Rtop > Ntop, Rtop ← Rtop - Ntop, und fc ← 1.
Falls l&submin;&sub1; Ntop < Rtop, fc ← fc + 1.
fc ← -fc.

Schritt 4

Ende
Anmerkung 1:
Grenz-Indizes von l&sub1;, und l&submin;&sub1;,
l&sub1; = 1/2 - bA/4N
-l&submin;&sub1; = 1/2 + bA/4N
sind zuvor für jeden Fall von b = 0, ± 1 oder ± 2 bestimmt.
In diesem zweiten Entscheidungsverfahren wird, in derselben Art und Weise wie bei dem ersten Entscheidungsverfahren, (R + bA/4)/N so gesteuert, um innerhalb eines Bereichs von -9/16 bis 9/16 zu liegen, und dieses zweite Entscheidungsverfahren wird dann verwendet, wenn 1/2 ± bA/4N) zuvor präzise als die komparativen Indizes erhalten werden kann. Bei diesem zweiten Entscheidungsverfahren ist es ausreichend, fünf höher signifikante Bits von N mit dem komparativen Index zu vergleichen.
Fig. 6(A) stellt ein vereinfachtes Robertson-Diagramm dar, in dem eine Gruppe von Linien (c = ±2, ±1, 0) mit einem Gradienten von 45 Grad als eine lineare Gleichung wie folgt dargestellt ist:
R(k - 1) = 2R(k) - cN
da 2R(k)/N den Abszissen (x-Koordinaten) entspricht und R(k - 1)/N den Ordinaten (y- Koordinaten) entspricht. Weiterhin sind, wie dargestellt ist, die Steigungslinien innerhalb eines Fensters beschränkt, das bestimmt ist durch:
wobei d eine Grenz-Variable bezeichnet (die später in weiterem Detail beschrieben ist).
Das gewöhnliche Robertson-Diagramm zum Ersetzen einer binären Division mit Bildung eines positiven Rests mit einem zugelassenen Ziffern-Satz ist in "Computer Arithmetic: Principles, Architecture, and Design" von Kai Hwang, School of Electrical Engineering Purdue University, John Wiley & Sons, New York, offenbart, was hier unter Bezugnahme darauf eingeschlossen wird.
Fig. 6(B) stellt ein Beispiel des Verfahrens eines Bestimmens eines partiellen Modulus c = 1 an der dritten Stufe R(3) dar, wenn (45) mit (3) dividiert wird, wobei () eine dezimale Zahl bezeichnet.
Fig. 7(A) stellt ein modifiziertes Robertson-Diagramm zur Unterstützung bei der Erläuterung eines Verfahrens eines Entscheidens eines partiellen Quotienten c dar, wodurch die Berechnung, die durch den Ausdruck von Rnew ← rx(Rold - cN) + bA dargestellt ist, ohne einen Bit-Überlauf aus einem vorbestimmten, berechnungsmäßigen Bereich ausgeführt werden kann. In dem gewöhnlichen Robertson-Diagramm ist b = 0, da nur eine Division gehandhabt wird.
In Fig. 7(A) stellen Linien, die einen Gradienten von 45 Grad besitzen, ganze Zahlen c zwischen -r/2 und r/2 dar. Diese Linien werden innerhalb eines Fensters bestimmt, das zwischen -rd und rd auf der Achse der Abszisse und zwischen [-d - bA/rN und d - bA/rN] auf der Achse der Ordinate definiert ist. Hierbei bezeichnet e einen Grenz-Index, der einen Mittelpunkt eines Breichs darstellt, wo zwei angrenzende Steigungslinien überlappt sind. Der komparative Index bewegt sich nach rechts und nach links, da sich der darauffolgende, partielle Multiplikator b ändert und sich deshalb das Fenster nach oben und nach unten bewegt. Allerdings können, da der partielle Multiplizierer b auf eine ganze Zahl -r/2 und r/2 definiert ist und weiterhin der komparative Index negativer Bereiche von l&submin;&sub1; in Bezug auf b zu - l-i in Bezug auf -b entspricht, die zuvor erhaltenen, komparativen Indizes eingeschränkt werden.
Um den partiellen Quotienten zu bestimmen, wird der momente /N-Wert, wobei /N ← (r(R - cN) + bA)/N gilt, berechnet und dann auf der Achse der Abszisse ausgedruckt. Das bedeutet, daß die partielle Quotienten-Linie durch den Vergleich /N mit dem komparativen Index l bestimmt wird.
Weiterhin wird die Grenz-Variable d (wie später in Anhang (1) erläutert ist) wie folgt bestimmt:
d = 1/2 + 1/{4(r - 1)}.
Fig. 7(B) stellt ein modifiziertes Robertson-Diagramm dar, wenn die Radix-Zahl r = 4 gilt, anhand eines Beispiels.
Fig. 7(C) stellt ein modifiziertes Robertson-Diagramm zur Unterstützung bei der Erläuterung der Basis der ersten und zweiten Ausführungsform dar, die einen Zwischenzustand der wiederholten Berechnungen darstellt. Hierbei bezeichnet R(k) den momentanen Rest und R(k - 1) bezeichnet den darauffolgenden Rest. Die Abszisse stellt einen Wert von (4R(k) + b(k)A)/N dar, was einer Addition von partiellen Produkten in Fig. 1(C) entspricht, und die Ordinate stellt den darauffolgenden Rest R(k - 1)/N dar. Ein partieller Quotient c (-2 bis 2) kann durch die Graphen bestimmt werden. Hierbei kann der Graph ausgedrückt werden wie folgt
R(k - 1) = 4R(k) + b(k)A - cN,
wobei -9/16 - {b(k - 1)A}/4 < {R(k - 1)}/N < 9/16 - {b(k - 1)A}/4.
Diese Graphen sind Linien mit einem Gradienten 45 Grad und einem Schnitt mit der Achse der Abszisse bei 0, ±1, ±2.
Die Graphen liegen zwischen -9/4 und 9/4 auf der Abszisse und zwischen -9/16 - b(k - 1)A/4N und 9/16 - b(k - 1)A/4N auf der Ordinate. Als eine Folge liegt R + bA/4 immer innerhalb eines Bereichs von -9/16 zu 9/16.
Andererseits ändert sich der graphische Darstellungsbereich (Fenster) gemäß dem Wert bA. In dem Fall der fc-Funktions-Entscheidungs-Verfahren ist, wenn A ungefähr N/2 ist, der Grenz-Index l&sub1; zwischen c = 0 und c = -1 1/2, falls b = 0, allerdings, verschoben zu 1/4, falls b = 2, und A ist positiv.
Bei einer Entscheidung der Funktion fc ist es, da die Grenz-Bereiche (wo eine zweiwertige Funktion in Bezug auf die Abszisse dargestellt ist) eine Breite von 1/8 besitzt, möglich, c durch Vergleich der höher signifikanten Bits von R(k) mit den höher signifikanten Bits von N unter Berücksichtigung eines Vorzeichens von A zu bestimmen, und zwar ohne Berechnung von (4R(k) + b(k)A)/N.
Die Basis der Präzision und der Grenz-Variablen d für einen Vergleich wird nachfolgend erläutert werden.
Zuerst wird der Grund, warum der absolute Wert von (R + bA/4)/N auf 9/16 oder weniger gesetzt wird, beschrieben werden.
Ein Rest R liegt immer innerhalb eines Bereichs von
-d - bA/4N ≤ R/N ≤ d - bA/4N, d > 0 .... (1)
Hierbei muß, um c = -2, -1, 0, 1 und 2 zu erhalten,
2 - d - bA/4N < 4d < 2 + d - bA/4N .... (2)
erfüllt werden.
Weiterhin wird, da A von 0 ≤ A < N in A von
A ≤ N/2 .... (3)
transformiert wird, wenn die Ausdrücke (1), (2) und (3) gemäß den Bereichen von b = -2, -1, 0, 1, 2 klassifiziert werden,
7/20 ≤ d ≤ 7/12 .... (4)
erhalten.
Allerdings kann, da
2d > 1 .... (5)
notwendig ist, um eine zweiwertige Funktion zu erhalten, so daß zwei Graphen an den angrenzenden Graphen-Grenzen überlappt werden,
1/2 < d ≤ 7/12 .... (6)
von den Ausdrücken (4) und (5) abgeleitet werden. Deshalb kann d von einer Fraktion, die innerhalb dieses Bereichs des Ausdrucks 6 liegt, ausgewählt werden.
Um die Präzisions-Berechnung zu erleichtern, wird, falls der minimale Wert einer Fraktion, die einen Nenner von 2e besitzt, unter der Fraktion ausgewählt wird, die d darstellt,
d = 9/16 .... (7)
bestimmt werden.
Als nächstes wird die Basis, daß die Zahl von Bits von Ntop und Rtop für einen Vergleich bestimmt wird, erläutert werden.
Aus
Rtop/(Ntop + 1) < R/N < (Rtop + 1)/Ns .... (8)
kann
R/N - Rtop/Ntop < 1/Ntop .... (9)
abgeleitet werden.
Deshalb ist, falls Ntop m Bits ist, da
Ntop ≥ 2m-1 .... (10)
gilt, der Fehler 21-m oder geringer.
Hierbei ist in dem Fall des zweiten fc-Entscheidungs-Verfahrens, da der zulässige Fehlerbereich ungefähr 1/16 mit seinem Grenz-Index an seiner Mitte ist,
m ≥ 5 .... (11)
notwendig.
Andererseits ist in dem Fall des ersten fc-Entscheidungs-Verfahrens, da der zulässige Fehlerbereich ungefähr 1/16 -1/32 = 1/32 mit seinem Grenz-Index als seine Mitte ist,
m ≥ 6 .... (12)
erforderlich.
Fig. 8 zeigt eine Tabelle zum Vergleichen der berechnungsmäßigen Geschwindigkeit zwischen der vorliegenden Erfindung und dem Verfahren nach Baker bei einer modularen Multiplikation, wobei die Anzahlen von wiederholten Additionen und Subtraktionen unter Verwendung von Operationsschaltkreisen mit einer n-Bit Länge verglichen werden. Zum Beispiel erfordert, wenn durchschnittliche Bits von B als 1 oder 0 verteilt werden, und n eine Bit-Länge eines Modulus N bezeichnet, das Verfahren nach Baker n/2 Multiplizier-Additionen/Subtraktionen und 3n/4 modulare Additionen/Subtraktionen und deshalb 5n/4 Additionen/Subtraktionen insgesamt im Durchschnitt und ähnlich n Multiplizier- und Modular-Additionen/Subtraktionen und deshalb 2n Additionen/Subtraktionen insgesamt maximal. Andererseits erfordert das Verfahren der vorliegenden Erfindung 3n/8 Multiplizier- und Modular-Additionen/Subtraktionen und deshalb 3n/4 Additionen/Subtraktionen insgesamt im Durchschnitt und ähnlich n/2 Multiplizier- und Modular-Additionen/Subtraktionen und deshalb n Multiplizier- und Modular-Additionen/Subtraktionen insgesamt maximal. Dies zeigt an, daß die berechnungsmäßige Geschwindigkeit des erfindungsgemäßen Verfahrens 1,7-mal höher als bei dem Verfahren nach Baker im Durchschnitt und zweimal höher als nach dem Verfahren nach Baker maximal ist.
Fig. 9(A) zeigt ein Blockdiagramm, das eine dritte Ausführungsform jeder Zelle 43i darstellt, die in dem modularen Multiplikationssystem gemäß der vorliegenden Erfindung, dargestellt in Fig. 4(A), eingesetzt ist, wobei der partielle Rest R, der in redundanter Form dargestellt ist, direkt für einen Multiplikator B an der darauffolgenden Verarbeitungsstufe substituiert werden kann. In Fig. 9(A) ist ein Übertrag-Sicherungs-Addierer 63A, der auf eine Radix-Zahl von 4 angepaßt ist, dargestellt. Weiterhin müssen, wenn irgendeine gegebene Radix-Zahl r angepaßt ist, (n + r') Teil-Zellen 43i in Serie zu einer Feldform verbunden werden, um ein r-Radix-Modular-Multiplikations-System zu realisieren. Mittels der Zellen, dargestellt in Fig. 9(A), kann das folgende, dritte Verfahren ausgeführt werden.

A · B mod N (3. Verfahren)

Hierbei kann, wenn R redundant als
R Rs + 2Rc
dargestellt wird, eine Addition von R + X ersetzt werden, und zwar auf der Basis des redundanten Darstellungs-Prinzips, mit
Rs ← Rs 2Rc X
Rc ← Rs · 2Rc V {X · (RsV 2Rc)}
wobei ein Exklusiv-ODER bezeichnet; wobei · das logische Produkt bezeichnet; und wobei V die logische Summe bezeichnet.
In dieser dritten Ausführungsform kann die Berechnung des Ausdrucks von Rnew ← r x (Rold - cN) + bA durch den Übertrag-Sicherungs-Addierer 63A ausgeführt werden, der die Übertrag-Propagations-Zeiten eliminieren kann.
Fig. 9(B) zeigt ein Blockdiagramm, das eine vierte Ausführungsform jeder Zelle 43i darstellt, die in dem modularen Multiplikations-System gemäß der vorliegenden Erfindung, dargestellt in Fig. 4(A), eingesetzt wird, wobei die partiellen Reste R, dargestellt in redundanter Form, direkt wieder für einen Multiplikator B an der darauffolgenden Stufe substituiert werden können und weiterhin der Multiplikand A auch in redundanter Form dargestellt wird. Mittels der Zellen, dargestellt in Fig. 9(B), kann das nachfolgende, vierte Verfahren ausgeführt werden.

A mod N (4. Verfahren)

In dem Fall eines modularen Potenzierens (modulare Potenzmultiplikation) wird das berechnungsmäßige Ergebnis als der darauffolgende Multiplikand verwendet. Deshalb ist es, wenn eine Hochgeschwindigkeits-Modular-Potenzierung erforderlich ist, bevorzugt, das modulare Multiplikationsergebnis der redundanten Darstellung als den Multiplikanden der darauffolgenden, modularen Multiplikation ohne eine Übertrag-Propagation zu bestimmen. Dieses Verfahren kann durch Anordnen einer Vielzahl von (n + r') Zellen, wie in Fig. 9(B) dargestellt ist, realisiert werden, wobei die Radix-Zahl r = 4, r = 2r' (da r = 2r' ist) realisiert wird. Weiterhin werden die nachfolgenden Substitutionen bei der abschließenden Stufe ausgeführt als
As ← Rs
Ac ← Rc.
Andere Ausführungsformen des modularen Multiplikationsverfahrens gemäß der vorliegenden Erfindung mittels des Systems, das in den Fig. 2 und 3 dargestellt ist, werden nachfolgend beschrieben werden.

A · B mod N (5. Verfahren)

Schritt 1 (Initialisierung)

(1) falls N < 2A, Ar ← A - N
(2) n ← log&sub2; (N) + 1
(3) k ← n/r' + 1 (r = 2r', r' ≥ 1)
(4) R(k) ← 0
(5) c(k + 1) ← 0

Schritt 2 (Wiederholung von n/r + 1-mal)

(1) R(k - 1) ← rx {R(k) - c(k + 1)N} + b(k)A
(2) c(k) ← fc(R(k - 1), b(k - 1))
(3) k ← k - 1

Schritt 3 (abschließende Verarbeitung)

(1) R(0) ← R(0) - c(1)N
(2) A ← R(0) (falls R(0) ≥ 0)
A ← R(0) + N (falls R(0) < 0)
Hier wird die Funktion fc wie folgt ausgeführt:
fc(R, b):
fc ← i(falls li N < R ≤ l i + 1 N)
fc ← 0(falls l-i N ≤ R ≤ li N)
fc ← -i(falls l-i-1 - 1 , N ≤ R < l-i N)
Hierbei ist der Vergleichs-Index l ein Mittelpunkt an einem Bereich, wo zwei Linien auf der Achse einer Abszisse in Fig. 7 überlappt sind; li i - 1/2 - bA/rN, l -i + 1/2 - bA/rN; b ist eine ganze Zahl innerhalb eines Bereichs zwischen -r/2 und r/2; i ist eine ganze Zahl innerhalb eines Bereichs zwischen 1 und r/2. Sowohl die ganze Zahl b als auch i sind zuvor bestimmt.
Wie vorstehend beschrieben ist, können in dieser Ausführungsform komparative Indizes einfach bestimmt werden.

A · B mod N (6. Verfahren)

Bei dieser Ausführungsform wird die Funktion fc gemäß einem Näherungsverarbeitungsverfahren verglichen.
Wenn sich die Bit-Länge n von A, B und N erhöht, erhöht sich die Bit-Länge, die für einen Vergleich von R und dem komparativen Index l erforderlich ist, um die Funktion fc zu bestimmen. Deshalb werden in diesem Fall nur die verschiedenen höher signifikanten Bits wie folgt verglichen:
Funktion fc (R, b):
fc ← i (falls Li Ntop < Rtop ≤ Li &sbplus; &sub1; Ntop
fc ← o(falls L&submin;&sub1; Ntop < Rtop ≤ L&sub1; Ntop
fc ← -i (falls L-i &submin; &sub1; Ntop < Rtop < L-i Ntop
wobei Li i - 1/2 - bAtop/rNtop,
L&submin;&sub1; i + 1/2 - bAtop/rNtop,
-r/2 ≤ b ≤ r/2, wobei b eine ganze Zahl ist
1 ≤ i ≤ r/2, wobei i eine ganze Zahl ist
Ntop bezeichnet x oder mehr signifikante Bits von N
Atop bezeichnet x oder mehr signifikante Bits von A
Rtop bezeichnet x oder mehr signifikante Bits von R
Da A und R ein Vorzeichen besitzen, besitzen Atop und Rtop auch ein Vorzeichen (±).
Weiterhin kann der vorstehende Wert x bestimmt werden, wie dies später in Anhang 2 beschrieben ist, wie folgt:
X = log&sub2; {(r - 1) (rd + 2)} + 3
wobei y eine minimale, ganze Zahl mehr als y bezeichnet.
In der vorstehend erwähnten sechsten Ausführungsform kann der Vergleich zwischen dem komparativen Index mit dem partiellen Rest R durch Vergleich nur verschiedener höherer signifikanter Bits von li und R erhalten werden.

A · B mod N (7. Verfahren)

Bei dieser Ausführungsform wird N gemäß einem Näherungsverarbeitungsverfahren transformiert.
Wenn alle Bits von N und 2A miteinander in der fünften Ausführungsform in Schritt 1 (1) verglichen werden, erhöhen sich die berechnungsmäßige Geschwindigkeit und das Hardware-Volumen mit einem Erhöhen von n (Bits).
In diesem Fall werden Ntop und 2Atop anstelle eines Vergleichs zwischen N und 2A verglichen. In derselben Art und Weise wie bei der Funktion fc bezeichnet Ntop y höher signifikante Bits von N, und Atop bezeichnet A, das unterhalb eines Bereichs von N, verwendet zur Bildung des Ntop, liegt. Weiterhin besitzt, da A ein Vorzeichen besitzt, Atop auch ein Vorzeichen.
Falls Atop/Ntop - A/N < 2/Ntop,
wird 2Atop mit Ntop verglichen.
Falls 2Atop > Ntop bestimmt wird,
wird A ← A - N ausgeführt, so daß
A/N < Atop/Ntop + 2/Ntop < 1/2 + 2/Ntop
erhalten wird. Deshalb kann
d = 1/2 + (1 - 4/Ntop)/4(r - 1)
erhalten werden. Hierbei wird, da das am meisten signifikante Bit von N 1 ist,
d = 1/2 + (1 - 2³ &supmin; y)/4(r - 1) ausgewählt.
Als eine Folge werden, da d kleiner als das originale d wird, wenn diese Ausführungsform zusammen mit der 2. Ausführungsform verwendet wird, x und y in der Beziehung von
x = log&sub2; (r - 1)(rd + 2)/(1 - 23-y) + 3
ausgewählt.
In dieser 6. Ausführungsform ist es möglich, die Zahl von Bits, die zum Vergleich von 2A > N für eine Transformation von A erforderlich ist, zu reduzieren.

ANHANG

Die Ableitung der komparativen Grenz-Variablen d (in der Basis-Konfiguration) und der höher signifikanten Bits x von Ntop und Rtop (in der 6. Ausführungsform) werden nachfolgend erläutert werden:

(1) Ableitung einer Grenz-Variablen d

(In dem Fall von Radix 4)
In Fig. 7(B) ist die Vergleichs-Grenz-Variable d = 7/12 definiert wie folgt:
Die notwendigen Zustände, so daß der Graph kontinuierlich in Bezug auf die Achse der Abszisse ist, werden ausgedrückt als
d > 1/2 ....(22)
Der Zustand, daß (4R + bA)/N innerhalb eines Bereichs von -4d und 4d auf der Achse der Abszisse liegt, ist
4d < 2 + d - bA /4N .... (23)
Hierbei können, da b ≤ 2 und A ≤ N/2 sind, die Ausdrücke (22) und (23) transformiert werden als
1/2 < d ≤ 7/12 .... (24)
Demzufolge kann d = 7/12 .... (25)
erhalten werden.
(In dem Fall einer allgemeinen Radix r)
In derselben Weise wie der Ausdruck (23) kann
rd ≤ r/2 + d - bA /rN .... (26)
in Bezug auf die allgemeine Radix r erhalten werden.
Andererseits kann, da b ≤ r/2, c ≤ r/2 und A ≤ N/2 gilt,
d = 1/2 + 1/4(r - 1) .... (27)
erhalten werden.
(2) Ableitung von x höher signifikanter Bits von N oder R zum Vergleich

Definition

rR + bA
Ntop x höher signifikante Bits von N
Atop x höher signifikante Bits von A
Rtop (x + log&sub2; r) höher signifikante Bits von
Allerdings ist x eine positive, ganze Zahl, und b b(k).
(In dem Fall von Radix 4)
In Fig. 7(B) kann der Index l&sub1; zwischen c = 0 und c = +1 ausgedrückt werden als
l&sub1; 1/2 - · A/4N .... (28)
wobei = b(k - 1) gilt.
L&sub1; kann definiert werden als ein ungefährer Wert des Grenz-Index l&sub1; durch den nachfolgenden Ausdruck als
L&sub1; 1/2 - A/top/4Ntop .... (29)
Falls ≤ δ - δ' gilt .... (30)
wobei R/N - Rtop/Ntop .... (31)
δ d - 1/2 = 1/12 .... (32)
δ' L&sub1; - l&sub1; .... (33)
erfüllt werden kann, ist es möglich, den Vergleich des Grenz-Index l&sub1; mit R einer n-Bit-Länge mit dem Vergleich von L1 mit Rtop zu ersetzen.
Weiterhin kann, falls R/N ≤ rd = 7/3 verwendet wird, der Ausdruck (31) transformiert werden in
≤ (Rtop + 1)/Ntop - Rtop/(Ntop + 1) < 10/3 Ntop .... (34)
Falls b ≤ 2 gilt, ist der Ausdruck (33)
δ' < 2 b /4Ntop ≤ 1/Ntop .... (35)
Deshalb kann
Ntop ≥ 52 .... (36)
aus den Ausdrücken (30), (32), (34) und (35) abgeleitet werden.
Da das am meisten signifikante Bit von immer 1 ist, gilt
Ntop ≥ 2x-1 .... (37)
Als Folge wird der minimale Wert x unter den Bedingungen ausgewählt, daß die Ausdrücke (36) und (37) erfüllt werden, als
x = 7.... (38).
Derselbe Ausdruck (38) kann ausreichen bei l&sub2;, l&submin;&sub1; und l&submin;&sub2; angewandt werden.
(In dem Fall der allgemeinen Radix r)
In derselben Art und Weise kann der nachfolgende Ausdruck erhalten werden als
Ntop ≥ 4(r - 1) (rd + 2).... (39)
Deshalb kann der minimale Wert x ausgedrückt werden als
X = log&sub2; {(r - 1) (rd + 2)} + 3.... (40)
Ein System und ein Verfahren zum Ausführen einer Multiplikation A · B (A: Multiplikand; B: Multiplikator) werden nachfolgend beschrieben werden, die beim Ausführen einer modularen Potenzierung (Potenz-Multiplikation), wie beispielsweise Me mod N (wobei e den Exponenten bezeichnet), effektiv ist.
Eine Multiplikation ist notwendig, um grundsätzlich eine Anzahl von Additionen zu wiederholen. Falls sich die Bit-Länge erhöht, wird die berechnungsmäßige Geschwindigkeit aufgrund des Vorhandenseins einer Übertrag-Propagation in Additionen reduziert. Fig. 1(A) stellt ein Beispiel dar, bei dem eine Multiplikation A · B durch Verschieben des Multiplikanden A Bit für Bit gemäß jedem Bit des binären Multiplikators B in dem herkömmlichen Verfahren erhalten wird.
Um die berechnungsmäßige Geschwindigkeit der Multiplikation zu erhöhen, ist ein Verfahren einer Verwendung eines Übertrag-Sicherungs-Addierers, durch den jedes Bit eines Multiplikanden A und jedes Bit eines Multiplikators B unabhängig irrespektive einer Bit-Länge addiert werden, bekannt. Bei diesem Verfahren wird die Variable X durch eine redundante Darstellung als
X = Xs + 2Xc
dargestellt.
Wenn Y zu X hinzuaddiert wird, werden
((2Xc) · Xs) V (Xs · Y) V (Y · (2Xc) und (2Xc) Xs Y
ausgeführt, und der Wert x wird durch Xc und Xs, wie folgt, aktualisiert:
X ← Xs + 2Xc'
wobei " · " das logische Produkt bezeichnet; wobei "V" die logische Summe bezeichnet; wobei " " die exklusive logische Summe bezeichnet; und wobei "←" die Substitution bezeichnet.
In dem Fall der Fig. 1(A) können die partiellen Produkte durch Verschieben von Bits von A anstelle von Y und durch Addieren jedes Bits von zwei partiellen Produkten Bit für Bit durch Übertrag-Sicherungs-Addierer erhalten werden, und nachdem die abschließende Übertrag-Sicherungs-Addition abgeschlossen worden ist, wird eine Übertrag-Propagations-Addition von X ← Xs + 2Xc ausgeführt, wo es notwendig ist, um einen einzelnen Repräsentationswert X zu bilden.
In diesem Verfahren reduziert allerdings, da die Übertrag-Propagations-Addition ausgeführt wird, nachdem die Übertrag-Sicherungs-Addition der abschließenden Stufe abgeschlossen worden ist, wenn eine Potenzierung oder Potenz-Multiplikationen, wie beispielsweise A ← A · B oder B ← B x B wiederholt ausgeführt werden, die Übertrag-Propagations-Addition für jede Multiplikation unvermeidbar die berechnungsmäßige Geschwindigkeit.
Um das vorstehende, herkömmliche Verfahren zu verbessern, wenn das Ergebnis des Übertrag-Sicherungs-Addierers der abschließenden Stufe als ein Multiplizierer verwendet wird, ist ein Verfahren zum Ausführen von Multiplikationen auf der Basis einer redundanten Repräsentation ohne Ausführen von Übertrag-Propagations-Additionen vorgeschlagen worden, wie dies durch "On a Fast Iterative Multiplication Method by Recoding Intermediate Products" von Takagi und Yajima, Information Processing Transaction No. 36 (1986) (4c - 1), offenbart ist. Bei diesem Verfahren werden binäre Multiplikatoren irgendeines von (-2, -1, 0, 1, 2) direkt zwei Bit für zwei Bit erzeugt. Das bedeutet, daß in dem Fall der Fig. 1(A) irgendeines partieller Produkte von (-2A, -A, 0, A, 2A) durch Verschieben der Bits gebildet wird, wobei (-2) die Verschiebung nach links um ein Bit von A und Bilden einer Zweierkomponenten darstellt; wobei (-1) Bilden einer Zweierkomponenten darstellt; wobei (0) Ausgeben von Null darstellt; wobei (1) eine Nicht-Transformation darstellt; und wobei (2) eine Linksverschiebung um ein Bit, jeweils, darstellt. In dem Fall der Fig. 10 zum Beispiel werden die partiellen Produkte durch Verschieben des Multiplikanden A nach links zwei Bits für zwei Bits addiert.
Um ein Produkt A · B von zwei Variablen A und B zu erhalten, wird der Multiplikator B redundant als B = Bs + 2Bc dargestellt, Bs oder Bc wird als Bs[1], Bs[2], ..., in der Reihenfolge von dem am wenigsten signifikanten Bit dargestellt. In diesem Fall bildet das Verfahren von Takagi et al zwei Funktilnen (fc, fs) unter Bezug auf die Tabelle, die in Fig. 11 dargestellt ist, um partielle Multiplikatoren zwei Bits für zwei Bits zu bilden. In Fig. 11 ist es allerdings, da dort vier auswählende Positionen vorhanden sind, wobei ein Querstrich, der und/oder anzeigt, vorhanden ist, notwendig, fs auf der Basis der niedrigeren, signifkanten Bits zu bestimmen. Weiterhin ist es notwendig, einen Multiplikator von fc und fs zwei Bit für zwei Bit auf der Basis der noch niedriger signifikanter Bits zu bestimmen, da fc entschieden werden muß. Deshalb existiert dabei ein Problem dahingehend, daß die Speicherzugriffssteuerung für Daten verkompliziert wird, um selektive Funktionen zu bestimmen, und deshalb erniedrigt sich die berechnungsmäßige Geschwindigkeit und das Hardware-Volumen erhöht sich.
Fig. 12 zeigt ein Gesamtblockdiagramm einer Ausführungsform des Multiplikator-Systems der vorliegenden Erfindung, das grob gesagt einen Register-Block 110 und einen Operations-Block 120 aufweist.
In Fig. 12 speichert ein A-Register 111 einen Multiplikanden A und ein B-Register 112 speichert einen Multiplikator B. Allerdings wird, da der Multiplikator B durch Variable Bs und Bc als B = Bs + 2Bc in einer redundanten Darstellungsform dargestellt wird, Bs in einem Bs-Register 121-1 gespeichert und Bc wird in einem Bc Register 122-2 jeweils gespeichert. Fig. 13 stellt die Anordnungs-Reihenfolge von Bs und Bc in den Registern 112-1 und 122-2 dar. Ein R-Register 113 speichert das abschließende Ergebnis und eine Arbeits-Variable R während einer Berechnung. Da die Arbeits-Variable R durch Rs und Rc als R = Rs + 2Rc in einer redundanten Repräsentations- Form dargestellt wird, wird Rs in einem Rs-Register 131-1 gespeichert und Rc wird in einem Rc-Register 113-2 jeweils gespeichert.
Ein b(k)-Generator 121 ist mit einer Referenz-Tabelle, wie in Fig. 14 dargestellt ist, versehen und erzeugt Multiplikatoren b(k) basierend auf Radix 4 (b(k) ← (fc, fs) auf der Basis der Variablen Bs und Bc über alle Bits (k = 1, 2, ... n/2 + 1). Fig. 14 listet zwei Funktionen fc und fs für Multiplikatoren b(k) auf, was durch die Kombination von Bs und Bc ausgewählt werden kann, das bedeutet Bs[2k]Bc[2k - 1] und Bs[2k - 1]Bc[2k - 2], wie folgt:
falls eine Kombination (0,0,0,0) ist, dann sind die Daten (fc, fs) (0,0),
" " " (0,0,0,1) ist, dann sind die Daten (") (0,1),
" " " (0,0,1,0) ist, dann sind die Daten (") (0,1),
" " " (0,0,1,1) ist, dann sind die Daten (") (1, -2),
" " " (0,1,0,0) ist, dann sind die Daten (") (1, -2),
" " " (0,1,0,1) ist, dann sind die Daten (") (1, -1),
" " " (0,1,1,0) ist, dann sind die Daten (") (keine),
" " " (0,1,1,1) ist, dann sind die Daten (") (keine),
" " " (1,0,0,0) ist, dann sind die Daten (") (1, -2),
" " " (1,0,0,1) ist, dann sind die Daten (") (1, -1),
" " " (1,0,1,0) ist, dann sind die Daten (") (1, -1),
" " " (1,0,1,1) ist, dann sind die Daten (") (1, 0),
" " " (1,1,0,0) ist, dann sind die Daten (") (1, 0),
" " " (1,1,0,1) ist, dann sind die Daten (") (1, 1),
" " " (1,1,1,0) ist, dann sind die Daten (") (keine),
und
" " " (1,1,1,1) ist, dann sind die Daten (") (keine), wobei die zwei Bits der linken Seite der Kombination die Bits anzeigen, die vertikal angeordnet sind, und die zwei rechtsseitigen Bits der Kombination die Bits anzeigen, die horizontal angeordnet sind.
Weiterhin kann b(k) auch durch Ausführen der nachfolgenden Berechnung erhalten werden:
b(k) ← -2 · (Bs[2k] Bc[2k - 1] + Bs[2k - 1] + Bc[2k - 2] -4 · · Bs[2k - 1] · Bc[2k - 2] + c(k) .... (1)
c(k) ← Bs[2k - 2]VBc[2k - 3] V (Bs[2k - 3] · Bc[2k - 4] .... (2)
wobei V die logische Summe bezeichnet; wobei · das logische Produkt bezeichnet; wobei das Exklusiv-ODER bezeichnet; wobei - eine Negation bezeichnet; wobei x die ordinäre Multiplikation bezeichnet, wobei + die ordinäre Addition bezeichnet, wobei - die ordinäre Subtraktion bezeichnet. Der gebildete Multiplikator b(k) ist irgendeiner von -2, -1, 0, 1, 2.
Ein bA-Generator 122 die partiellen Produkte bA gemäß jedem Wert (-2, -1, 0, 1, 2) von b(k) erzeugt, erzeugt durch den b(k)-Generator 121, in einer solchen Art und Weise, daß der Multiplikand A, gespeichert in dem A-Register 111, eins nach links verschoben wird, und ein Zweier-Komplement bestimmt wird (falls b(k) -2 ist); ein Zweier-Komplement bestimmt wird (falls b(k) -1 ist); Null ausgegeben wird (falls b(k) 0 ist); wird A ausgegeben, wie es ist (falls b(k) 1 ist); und A um eins nach links verschoben (falls b(k) 2 ist).
Eine R-Bit-Verschiebeeinrichtung 123 verschiebt Rs, gespeichert in dem Rs-Register 113-1, und Rc, gespeichert in dem Rc-Register 113-2, um zwei Bit nach rechts. Ein Übertrag-Sicherungs-Addierer 124 führt wiederholt Übertrag-Sicherungs-Additionen der Ausgaben von dem bA-Generator 122 und der R-Bit-Verschiebeeinrichtung 123 aus und speichert die addierten Ergebnisse Rs und Rc in dem Rs-Register 113-1 und dem Rc-Register 113-2 jeweils. Ein Übertrag-Propagations-Addierer 125 führt R ← Rs + 2Rc auf der Basis von Rs und Rc der abschließenden Additions-Ergebnisse aus, um ein einfaches Multiplikationsergebnis auszugeben.
Die Multiplikationsverarbeitung, die durch das System ausgeführt ist, das in Fig. 12 dargestellt ist, ist wie folgt: die Arbeits-Variable R wird zu Null initialisiert; das bedeutet, Rs ← 0 und Rc ← 0 werden für die zwei R- und C-Register 113-1 und 113-2 ausgeführt; ein Multiplikator b(k) wird auf der Basis der Variablen B durch den b(k)-Generator 121 gebildet; b(k)A wird durch den bA-Generator 122 ausgeführt; Rs ← 4Rs (eine Verschiebung nach rechts um 2 Bits) und Rc ← 4Rc (eine Verschiebung nach rechts um 2 Bits) werden durch die R-Bit-Verschiebeeinrichtung 123 ausgeführt; (2Rc) Rs (b(k)A) und ((2Rc · Rs) V (Rs · (b(k)A)) V (b(k)A) · (2Rc) werden durch den Übertrag-Sicherungs-Addierer-Schaltkreis 124 ausgeführt; zwei aktualisierte Rs und Rc werden in den Rs und Rc Registern 113-1 und 113-2 gespeichert; und dieselben Verarbeitungen werden wiederholt.
Beim Wiederholen der Multiplikationen wird R, gespeichert in dem R-Register 113, zu dem B-Register 112 in einer redundanten Repräsentationsform zugeführt, wenn das Multiplikationsergebnis R als ein neuer Multiplikator B verwendet wird, um A · R auszuführen. Diese Operation wird durch den Übertrag-Sicherungs-Addierer- Schaltkreis 124 ausgeführt, wie in Fig. 15(A) dargestellt ist.
In derselben Art und Weise wird, wenn die Multiplikations-Operationen wiederholt werden, um R X R auf der Basis des Multiplikations-Ergebnisses R auszuführen, R, das in dem R-Register 113 gespeichert ist, zu dem A-Register 111 und dem B-Register 112 in der redundanten Repräsentationsform zugeführt. In diesem Fall ist, da der Multiplikand A auch redundant dargestellt wird, ein 4-Eingangs-Übertrag- Sicherungs-Addierer 124 erforderlich, wie in Fig. 15(B) dargestellt ist.
Wenn ein Multiplikations-Ergebnis erforderlich ist, um einen einfachen Wert auszugeben, wird Rs + 2Rc durch den Übertrag-Propagations-Addierer (Welligkeit- bzw. Ripple-Übertrag-Addierer) 125 ausgeführt.
Fig. 15(A) stellt eine erste Ausführungsform eines Übertrag-Sicherungs-Addierer- Schaltkreises 124 gemäß der vorliegenden Erfindung zum Ausführen einer Addition eines partiellen Produkts P = b(k)A und einer Arbeits-Variablen R = Rs + 2Rc dar.
Herkömmlich ist ein Übertrag-Sicherungs-Addierer, wie in Fig. 16 dargestellt ist, angewandt worden. Allerdings sind, da der Zustand von Rs[2k] · Rs[2k - 1] · Rc[2k - 1] · Rc[2k - 2] = 0 (wobei Rc [0] = 0 gilt) nicht immer eingerichtet, wenn das Multiplikations- Ergebnis R als der darauffolgende Multiplikator B, wie er ist, verwendet wird, andere Schaltkreise zum Ausführen von Bs ← Rs (+) (2Rc), Bc ← Rs · (2Rc) erforderlich.
Der Übertrag-Sicherungs-Addierer, dargestellt in Fig. 15(A), eliminiert die vorstehenden Verarbeitungen wie folgt: ein logisches Produkt und eine exklusive, logische Summe.
c[i] ← P[i] · Rs [i - 2], s[i] ← P[i] (+) Rs [i - 2]
werden durch einen ersten Halb-Addierer 141 für jede ganze Zahl (i) von n bis 1 erhalten; eine logische Summe
t[i] ← Rc [i - 3] Vc [i - 1]
wird durch einen ODER-Schaltkreis 142 erhalten; ein logisches Produkt und eine exklusive, logische Summe
Rc [i] ← s[i] · [i], Rs [i] ← s[i] (+) t [i]
werden durch einen zweiten Halb-Addierer 143 erhalten, um das Zwischenergebnis Rc und Rs während sequentieller Multiplikations-Operationen zu aktualisieren. Da die Halb-Addierer an der abschließenden Stufe vorgesehen sind, werden die vorstehenden Bedingungen immer erfüllt. Allgemein kann, da der Voll-Addierer zwei Halb-Addierern im Schaltkreisvolumen entspricht, die vorliegende Erfindung ohne Erhöhung des Schaltkreisvolumens realisiert werden.
Fig. 15(B) stellt eine andere Schaltkreiskonfiguration des Übertrag-Sicherungs-Addierers 124 dar, die auch so erweitert wird, daß der Schaltkreis, der in Fig. 15(A) dargestellt ist, die Addition eines redundant dargestellten Multiplikanden A ausführen kann. In diesem Übertrag-Sicherungs-Addierer 124 wird eine Addition des partiellen Produkts P (gebildet durch P = b(k)A und dargestellt durch P = Ps + 2Pc) und die Arbeits-Variable R (dargestellt durch R = Rs + 2Rc) ausgeführt. Das bedeutet, ein logisches Produkt und ein Exklusiv-ODER werden als
c&sub1; [i] ← Ps[i] · Rs [i - 2], s&sub1;[i] ← Ps[i] (+) Rs [i - 2]
durch einen ersten Halb-Addierer 151 für jede ganze Zahl (i) von n bis 1 ausgeführt; eine logische Summe wird als
t[i] ← Rci - 3] V c&sub1;[i - 1]
durch einen ODER-Gatter-Schaltkreis 152 ausgeführt; und logische Summen und zwei Exklusiv-ODER-Verknüpfungen werden als
c&sub2; [i] ← (s&sub1; [i] · Pc [i - 1]) V (Pc [i - 1] · (t[i] · s&sub1; [i])
s&sub2; [i] ← (s&sub1; [i] Pc [i - 1]) t[i]
durch einen Voll-Addierer 152 ausgeführt, und ein logisches Produkt und ein Exklusiv-ODER werden als
Rc [i] ← (s&sub2; [i] · c&sub2; [i - 1], Rs [i] ← (s&sub2; [i] c&sub2; [i - 1]
durch einen zweiten Halb-Addierer 154 ausgeführt.
Wie vorstehend beschrieben ist, liefert das Multiplizier-System der vorliegenden Erfindung die nachfolgenden Vorteile:
(1) Da die Multiplikatoren basierend auf Radix 4 in einer redundanten Repräsentations-Form dargestellt werden und beginnend von irgendeinem gegebenen Bit erhalten werden, ist die Erfindung für eine modulare Multiplikation effektiv, insbesondere dann, wenn der Multiplikator beginnend von einem höhere Bit verarbeitet wird.
(2) Unterschiedlich gegenüber einem Verfahren von Takagi et al kann, da der Wert definitiv bestimmt werden kann, die vorliegende Erfindung die Anzahl von berechnungsmäßigen Stufen und das Hardware-Volumen reduzieren. Insbesondere kann, wenn die Multiplikatoren in Sequenz von dem höher signifikanten Bit zu dem niedriger signifikanten Bit erhalten werden, die berechnungsmäßige Geschwindigkeit merkbar verbessert werden.
(3) Da die Bedingung, daß
Bs[2k] · Bs[2k - 1] · Bc [2k - 1] · Bc[2k - 2] = 0
über alle Bits (k = 1, 2, ...) eingerichtet wird, nicht eine spezielle Bedingung ist, ist es möglich, leicht Voll-Addierer gegen Halb-Addierer an den Ausgangs-Stufen der Übertrag-Sicherungs-Addierer-Schaltkreise zu ersetzen.
Dies kommt daher, daß in dem Fall der modularen Multiplikation, da ein Verarbeitungsschritt R ← R - cN in Ausführung von R ← 4(R - cN) + bA (falls bA = 0), vorhanden ist, die vorstehende Bedingung gewöhnlich eingerichtet wird.
Um das Verständnis der modularen Multiplikation gemäß der vorliegenden Erfindung zu erleichtern, wird der berechnungsmäßige Vorgang davon systematisch unter Bezugnahme auf Flußdiagramme, die in den Fig. 17 bis 24 dargestellt sind, beschrieben werden.
Fig. 17 stellt eine Basis-Prozedur des Verfahrens einer Berechnung von A · B mod N der vorliegenden Erfindung dar, nachdem drei Variable A(Multiplikand), B(Multiplikator) und N(Modulus) in das System eingegeben worden sind.
Eine Steuerung transformiert zuerst einen Multiplikanden A zu A - N, falls 2A - N < 0 gilt, nach einer Normalisierung von N (in Schritt S1), stellt eine Bit-Länge n des Modulus N ein (in Schritt S2), initialisiert einen partiellen Rest R (in Schritt S3) und bestimmt dann die Zahl k wiederholter Verarbeitungsstufen (in Schritt S4) als
k ← n/r' + 1
wobei x eine maximale, ganze Zahl geringer als x bezeichnet; r = 2r, (r' ≥ 1); und r eine Radix-Zahl bezeichnet.
Danach aktualisiert eine Steuerung den partiellen Rest und bildet einen partiellen Multiplikator b und einen partiellen Quotienten c, beide innerhalb eines Bereichs von -r/2 ≤ b, c ≤ r/2 (in Schritt S5), und aktualisiert die Stufen-Nummer (k) (in Schritt 6) als
k ← k - 1.
Hierbei prüft die Steuerung, ob die momentane Stufen-Nummer k Null ist (in Schritt S7). Falls k nicht Null ist, kehrt die Steuerung zu Schritt S5 zum Wiederholen derselben Schritte S5 und S6 zurück. Falls k Null ist, da dies anzeigt, daß das abschließende Berechnungsergebnis oder der abschließende Rest R(0) erhalten worden ist, transformiert die Steuerung R zu einem abschließenden Ergebnis als eine Lösung von A · B mod N (in Schritt S8), was die Berechnungssteuerung beendet. In Fig. 17 sollte angemerkt werden, daß das Merkmal der vorliegenden Erfindung dasjenige ist, A zu A - N zu transformieren, falls 2A - N < 0 ist, und b und c innerhalb desselben, vorbestimmten Bereichs von -r/2 ≤ b, c ≤ r/2 zu bilden.
Fig. 18(A) stellt eine erste Modifikation eines A-Transformations-Verfahrens (in Schritt S1) dar. Die Steuerung prüft, ob ein absoluter Wert von A gleich oder kleiner als N/2 (in Schritt S11) ist als
A ≤ N/2 oder A N/2 ?
Falls A ≤ N/2 oder A N/2 ist, schreitet die Steuerung direkt zu Schritt S2 fort. Falls A > N/2 ist, transformiert die Steuerung A (in Schritt S12) vor einem Fortschreiten zu Schritt S2 als
A ← A - N
Fig. 18(B) stellt eine zweite Modifikation des A-Transformations-Verfahrens (in Schritt S1) dar. Die Steuerung prüft, ob (2A - N) geringer als Null ist, wenn das originale A N > A ≥ 0 ist (in Schritt S11-1) als
2A - N < 0 ?
Falls 2A - N < 0 gilt, schreitet die Steuerung direkt zu Schritt S2 fort. Falls 2A - N ≥ gilt, transformiert die Steuerung A (in Schritt 12) vor einem Fortschreiten zu Schritt S2 als
A ← A - N.
Fig. 18(C) stellt eine dritte Modifikation des A-Transformations-Verfahrens (in Schritt S1) dar. Die Steuerung prüft, ob (2Atop - Ntop) geringer als Null ist, wenn das originale Atop Ntop > Atop ≥ 0 ist (in Schritt S11-2), als
2Atop - Ntop < 0 ?
wobei Atop eine spezifizierte Zahl höher signifikanter Bits des Multiplikanden A bezeichnet und Ntop dieselbe, spezifizierte Zahl höher signifikanter Bits des Modulus N bezeichnet. Falls 2Atop - Ntop < 0 gilt, schreitet die Steuerung direkt zu Schritt S2 fort. Falls 2Atop - Ntop ≥ 0 gilt, transformiert die Steuerung Atop (in Schritt 12) für eine ungefähre Transformation vor einem Fortschreiten zu Schritt S2 aus als
A ← Atop - Ntop
Fig. 19(A) stellt eine erste Modifikation des n-Einstell-Verfahrens (in Schritt S2) dar. Die Steuerung stellt die Bit-Länge n des Modulus N (in Schritt S21) ein, und zwar vor einem Fortschreiten zu Schritt S3, als
n ← log&sub2; N + 1.
Fig. 19(B) stellt eine zweite Modifikation des n-Einstell-Verfahrens (in Schritt S2) dar. Die Steuerung prüft zuerst, ob die momentane Stufe die erste Stufe ist (in Schritt S22), als
k = 1 ?
Falls die momentane Stufe nicht die erste Stufe ist, schreitet die Steuerung direkt zu Schritt S3 fort. Falls die momentane Stufe die erste Stufe ist, stellt die Steuerung r, N und A ein (in Schritt S23), vor einem Fortschreiten zu Schritt S3, als
n ← n&sub0;
N ← N · 2m
A ← A · 2m
wobei eine ganze Zahl m gemäß dem nachfolgenden Ausdruck bestimmt werden kann als
2n-m > N ≥ 2n-m &supmin; ¹ (N: der originale Modulus)
Fig. 20(A) stellt eine erste Modifikation des R-Initialisierungs-Verfahrens (in Schritt S3) dar. Die Steuerung initialisiert den partiellen Rest R einfach (in Schritt S31), vor einem Fortschreiten zu Schritt S4, als
R ← 0.
Fig. 20(B) stellt eine zweite Modifikation des R-Initialisierungs-Verfahrens dar, wenn R in redundanter Form dargestellt wird als
R = Rs + 2Rc
wobei Rs die Summe von R bezeichnet und Rc den Übertrag von R bezeichnet. In diesem Fall initialisiert die Steuerung den partiellen Rest R (in Schritt S32), vor einem Fortschreiten zu Schritt S4, als
Rs ← 0
Rc ← 0.
Fig. 21(A) stellt eine erste Modifikation eines R-Aktualisierungs- und b-, c-Formations-Verfahrens dar (in Schritt S5). Eine Steuerung bildet zuerst einen partiellen Multiplikator b(k) bei der momentanen Stufe (in Schritt S51) und aktualisiert den partiellen Rest R(k - 1) für die darauffolgende Stufe als
R(k - 1) ← rR(k) + b(k)A
wobei b(k)A ein partielles Produkt bei der momentanen Stufe k bezeichnet, und bildet weiterhin den partiellen Multiplikator b(k - 1) an der darauffolgenden Stufe im Schritt (S52). Danach bildet eine Steuerung einen partiellen Quotienten c(k) an der momentanen Stufe (in Schritt S53) und aktualisiert den partiellen Rest R(k - 1) an der darauffolgenden Stufe (k - 1), wiederum (in Schritt S54) als
R(k - 1) ← R(k - 1) - c(k)N
wobei c(k)N einen modularen Subtrahierer bezeichnet. Danach schreitet die Steuerung zu den Basis-Schritten (S6) und (S7) fort.
Fig. 21(B) stellt eine zweite Modifikation eines R-Aktualisierungs- und b-, c-Formations-Verfahrens dar (in Schritt S5). Die Steuerung setzt zuerst den partiellen Quotienten c(k + 1) an der vorhergehenden Stufe (k + 1) als
c(k + 1) ← 0
zurück und bildet weiterhin den partiellen Multiplikator b(k) an der momentanen Stufe (in Schritt S51A) und aktualisiert den partiellen Rest R(k - 1) an der darauffolgenden Stufe als
R(k - 1) ← r (R(k) - c(k + 1)N) + b(k)A
und bildet den partiellen Multiplikator b(k - 1) an der darauffolgenden Stufe im Schritt (S52A). Danach bildet die Steuerung einen partiellen Quotienten c(k) an der momentanen Stufe (in Schritt S53). Danach schreitet die Steuerung zu den Basis-Schritten (S6) und (S7) fort. In dieser zweiten Modifikation wird der abschließende, partielle Rest R(0) nach Schritt S7 (in Schritt S81) erhalten als
R(0) ← R(0) - c(1)N
Fig. 22(A) stellt eine erste Modifikation einer R-Transformation dar (in Schritt S8). Die Steuerung prüft zuerst, ob der abschließende Rest R(0) wieder als ein Multiplikand A für die darauffolgende, modulare Multiplikations-Berechnung verwendet wird (in Schritt S82). Falls R(0) wieder als A verwendet wird, substituiert die Steuerung R(0) für A (in Schritt S83) als
A ← R(0)
bevor die Berechnungs-Steuerung endet. Allerdings prüft, falls R(0) nicht wieder als A verwendet wird (in Schritt S82), die Steuerung, ob R(0) gleich zu oder mehr als Null ist (in Schritt S84). Falls R(0) gleich zu oder mehr als Null ist, endet die Steuerung. Allerdings bestimmt, falls R(0) geringer als Null ist, die Steuerung den abschließenden, partiellen Rest R(0) (in Schritt S85) als
R(0) ← R(0) + N.
Fig. 22(B) stellt eine zweite Modifikation einer R-Transformation dar (in Schritt S8). Die Steuerung prüft zuerst, ob der abschließende Rest R(0) wieder als ein Multiplikand A für die darauffolgende modulare Multiplikation verwendet wird (in Schritt S82). Falls R(0) als A wiederverwendet wird, substituiert die Steuerung R(0) für A ohne Ändern von N (in Schritt S86) als
N ← N
A ← R(0).
Die Steuerung prüft, ob der abschließende Rest R(0) wieder als ein Multiplikator B für die darauffolgende, modulare Multiplikations-Berechnung verwendet wird (in Schritt S87). Falls R(0) wieder als B verwendet wird, substituiert die Steuerung R(0)/2m für B (in Schritt S89) als
B ← R(0)/2m
und die Steuerung bestimmt R(0) (in Schritt S90) als
R(0) ← R(0)/2m
bevor die berechnungsmäßige Steuerung endet. Allerdings schreitet, falls R(0) nicht wieder als B verwendet wird (in Schritt S87), die Steuerung direkt zu Schritt S90 fort.
Andererseits prüft, falls R(0) nicht wieder als A (in Schritt S82) verwendet wird, die Steuerung, ob R(0) gleich zu oder mehr als Null ist (im Schritt S84). Falls R(0) gleich zu oder mehr als Null ist, schreitet die Steuerung zu Schritt 90 fort. Falls allerdings R(0) < 0 ist, bestimmt die Steuerung den abschließenden, partiellen Rest R(0) (in Schritt S85) als
R(0) ← R(0) + N.
Danach wird der abschließende, partielle Rest R(0) nach Schritt S85 (in Schritt S90) erhalten als
R(0) ← R(0)/2m.
Fig. 23(A) stellt eine erste Modifikation des b(k)-Bildungs-Verfahrens dar (in Schritten S5, S51, S52A). Die Steuerung bildet einen partiellen Multiplikator b(k) innerhalb eines Bereichs von -r/2 ≤ b(k) ≤ r/2 auf der Basis der folgenden Gleichung (in Schritt S51-1) als
Fig. 23(B) stellt eine zweite Modifikation des b(k)-Bildungs-Verfahrens dar. Die Steuerung bildet einen partiellen Multiplikator b(k) auf der Basis des nachfolgenden Ausdrucks (in Schritt S51-2) als
b(k) ← -2B[2k] + B[2k - 1] + B[2k - 2]
wenn B = B[n], B[n - 1] ... B[1] gilt und die Radix-Zahl r = 4 ist, wobei B[i] = 0 ist, falls i > n oder i < 1 ist, und B[i] = 1 ist, falls i > n ist.
Wenn die Radix-Zahl r ist, kann der partielle Multiplikator b(k) ausgedrückt werden als
Fig. 23(C) stellt eine dritte Modifikation eines b(k)-Bildungs-Verfahrens dar. Die Steuerung bildet den partiellen Multiplikator b(k) auf der Basis des nachfolgenden Ausdrucks (in Schritt S51-3) als
b(k) ← fs(Bs[2k]Bc[2k - 1], Bs[2k - 1]Bc[2k - 2]) + fc(Bs[2k - 2]Bc[2k - 3], Bs[2k31]Bc[2k - 4])
wenn B = Bs + 2Bc in redundanter Form dargestellt wird und r = 4 ist.
Fig. 23(D) stellt eine vierte Modifikation eines b(k)-Bildungs-Verfahrens dar. Die Steuerung wählt zwei Werte der zwei Funktionen fc und fs in Kombination von (Bs[2k] Bc[2k - 1] und Bs[2k - 1] Bc[2k - 2] aus der Referenz-Tabelle nachfolgend (in Schritt S51-4) aus:
(fc, fs)
wobei x keine Werte bezeichnet.
Fig. 23(E) stellt eine fünfte Modifikation eines b(k)-Bildungs-Verfahrens dar. Die Steuerung bildet den partiellen Multiplikator b(k) durch Berechnung der zwei Funktionen fs und fc im Schritt (S51-5) wie folgt:
fc ← (Bs[2k] V Bc[2k - 1] V Bs[2k - 1] · Bc(2k - 2])
fc ← -2x(Bs[2k] Bc[2k - 1]) + Bs[2k - 1] + Bc[2k - 2]) - 4 · · Bs[2k - 1] · Bc[2k - 2]
wobei das Exklusiv-ODER bezeichnet; wobei · die logische Summe bezeichnet; wobei V das logische Produkt bezeichnet; und wobei eine Negation bezeichnet; und wobei die Bit-Pegel-Vektoren mit Vorzeichen-Bits bezeichnet.
Fig. 24(A) stellt eine erste Modifikation des c(k)-Bildungs-Verfahrens dar (in Schritten S5, S53). Die Steuerung bestimmt komparative Grenz-Indizes l unmittelbar nach dem A-Transformations-Schritt (51) durch die nachfolgende Definition (in Schritt S53-1) als
li b(k - 1) i - 1/2 - b(k - 1)A/rN
l-i b(k - 1) i + 1/2 - b(k - 1)A/rN
b(k - 1) {-r/2, -r/2 + 1, ... -1, 0, 1, ... r/2 - 1; r/2}
wobei den Satz von -r/2 bis r/2 bezeichnet. Danach bestimmt die Steuerung c(k) auf der Basis von zwei angrenzenden Grenz-Indizes (in Schritt S53-2) als
c(k) = i, falls li N < R(k - 1) ≤ li+1 N
c(k) = 0, falls li-1 N < R(k - 1) ≤ l&sub1; N
c(k) = -i, falls l-i-1 N < R(k - 1) ≤ l&submin;&sub1; N
Fig. 24(B) stellt eine zweite Modifikation des c(k)-Bildungs-Verfahrens dar. Die Steuerung bestimmt komparative Grenz-Indizes l und c(k) in derselben Art und Weise wie bei der ersten Modifikation, dargestellt in Fig. 24(A), auf der Basis von Atop, Ntop und Rtop (spezifiziert für höher signifikante Bits von A, N und R) (in Schritt S53-3) als
li b(k - 1) i - 1/2 - b(k - 1)Atop/rNtop
l-i b(k - 1) i + 1/2 - b(k - 1)Atop/rNtop
b(k - 1) {-r/2, -r/2 + 1, ..., -1, 0, 1, ..., r/2 - 1, r/2};
c(k) = i, falls li Ntop < Rtop (k - 1) ≤ li+1 Ntop
c(k) = 0, falls li-1 Ntop ≤ Rtop(k - 1) ≤ l&sub1; Ntop
c(k) = -i, falls l-i-1 Ntop ≤ Rtop (k - 1) ≤ l-i Ntop
Fig. 24(C) stellt eine dritte Modifikation eines c(k)-Bitdungs-Verfahrens dar. Die Steuerung setzt [i] (in Schritt S53-4) ein als
i = R /N + 1
und prüft, ob R(k - 1) gleich zu oder mehr als Null ist (in Schritt S53-5) als
R(k - 1) ≥ 0 ?
Falls R(k - 1) ≥ 0 ist, prüft die Steuerung ob li gleich zu oder geringer als R(k - 1)/N ist (in Schritt S53-6) als
li ≤ R(k - 1)/N ?
Falls li ≤ R(k - 1)/N ist, bestimmt die Steuerung c(k) (in Schritt S53-8) als
c(k) = i
Falls li > R(k - 1)/N ist, bestimmt die Steuerung c(k) (in Schritt S53-9) als
c(k) = i - 1
Falls R(k - 1) < 0 im Schritt (S53-5) ist, prüft die Steuerung, ob l-i gleich zu oder geringer als R(k - 1) /N ist (in Schritt S53-7) als
l-i ≤ R(k - 1) /N ?
Falls l-i ≤ R(k - 1) /N ist, bestimmt die Steuerung c(k) (in Schritt S53-10) als
c(k) = -i
Falls l-i > R(k - 1) /N ist, bestimmt die Steuerung c(k) (in Schritt S53-11) als
c(k) = -1 + 1.
Derzeit beträgt der maximale Durchsatz von LSls (groß skalierte, integrierte Schaltkreise), die derzeit auf dem Markt für RSA-Öffentlichkeits-Schlüssel-Krypto-Systeme sind, ungefähr 30 kbit/s. Allerdings ist es dort, wo die vorliegende Erfindung bei den Systemen angewandt worden ist, möglich, den Durchsatz ungefähr zweimal ohne Erhöhung des Hardware-Volumens zu erhöhen. Weiterhin ist es möglich, den Durchsatz im Prinzip mehr mit einer Erhöhung des Hardware-Volumens zu erhöhen. Mit anderen Worten ist es möglich, ökonomisch LSls mit einer Basis-Transfer-Geschwindigkeit von 64 kbit/s zu realisieren.
Zusätzlich ermöglichen das Verfahren und das System der vorliegenden Erfindung eine Datenverarbeitung unter hoher Geschwindigkeit mittels einer Hardware mit relativ kleinem Volumen. Zum Beispiel benötigt es derzeit mehrere Minuten für eine einzelne RSA kryptographische Verarbeitung in dem Fall eines IC-Karten-Chips (versehen mit einem 8-Bit-Mikroprozessor). Allerdings ist es möglich, dieselbe kryptographische Verarbeitungszeit herunter bis zu einigen Sekunden zu reduzieren, wenn das Verfahren und das System der vorliegenden Erfindung in dem IC-Karten-Chip eingesetzt werden. Weiterhin ist die vorliegende Erfindung effektiv auf verschiedene Systeme anwendbar, die eine modulare Multiplikationsverarbeitung unter hoher Geschwindigkeit erfordern, ohne auf kryptographische und authentische Systeme begrenzt zu sein, die Multibit-Länge n - modular-Multiplikation- oder Modular-Potenzierung-Berechnungen erfordern.
Wie vorstehend beschrieben ist, können das modulare Multiplikations-Verfahren und das -System gemäß der vorliegenden Erfindung eine Berechnung unter einer hohen Geschwindigkeit r'-mal höher als das Verfahren und das System nach dem Stand der Technik realisieren. Weiterhin kann das System durch einfaches Anordnen derselben Schaltkreise in Serie zum Erleichtern eines System-Designs konfiguriert werden.
Obwohl die modularen Subtrahierer für eine Division geprüft werden müssen, immer wenn die partiellen Reste addiert werden, ist es, da nur die höher signifanten Bits geprüft werden, möglich, die Anzahl von Vergleichs-Operationen herunter auf 1/r'-mal zu reduzieren, um so die Anzahl von Komparator-Schaltkreisen und die Kapazität des Speichers, der in dem System eingesetzt ist, zu reduzieren. Zusätzlich kann, da die Anzahl eines Speicherzugriffs reduziert wird, die berechnungsmäßige Geschwindigkeit erhöht werden.

Claims

1. Verfahren zum Ausführen einer modularen Multiplikation von A · B Modulo N, wobei A einen Multiplikanden bezeichnet, B einen Multiplikator bezeichnet und N einen Modulus bezeichnet, alle in Registern (11, 13, 15) jeweils gespeichert, das die Schritte besitzt:

(a) Speichern eines Multiplikanden A in einem ersten Register (11);

(b) Speichern eines Multiplikators B in einem zweiten Register (13);

(c) Speichern eines Modulus N in einem dritten Register (15);

(d) Speichern eines partiellen Rests R in einem vierten Register (17);

(e) Normalisieren des Modulus N durch einen Normalisierer (21);

(f) Erzeugen partieller Multiplikatoren b(k) und partieller Quotienten c(k) durch einen Parameter-Generator (23), wobei (k) eine Zahl von Verarbeitungsstufen bezeichnet;

(g) Erzeugen partieller Produkte b(k)A durch einen Generator (31) für partielle Produkte;

(h) Erzeugen modularer Subtrahierer c(k)N durch einen Generator (33) für modulare Subtrahierer;

(i) Aktualisieren von Resten R(k) durch einen Generator (35) für aktualisierte Reste;

(j) Ausführen einer Übertrag-Sicherungs-Addition von Rnew ← rx(Rold - c(k)N) + b(k)A, um den Rest R(k), gespeichert in der vierten Registereinrichtung, durch einen Übertrag-Sicherungs-Addierer (37) zu aktualisieren, wobei Rnew einen aktualisierten Rest bezeichnet;

(k) Ausführen einer Übertrag-Propagations-Addition, um den Multiplikanden A, gespeichert in der ersten Register-Einrichtung, durch Rnew zu aktualisieren, und zum Erzeugen einer Lösung von R(0) = A · B Modulo N durch einen Übertrag-Propagations-Addierer (39); und

(l) sequentielles Steuern berechnungsmäßiger Operationen durch eine Sequenz-Steuereinheit (25),

und wobei das Verfahren weiterhin die Schritte aufweist:

(1) Transformieren eines Multiplikanden A [0, N] zu A [-N/2, N/2] durch den Parameter-Generator (23), um das am meisten signifikante Bit des Multiplikanden A zu eliminieren;

(2) Transformieren partieller Multiplikatoren b(k) durch den Parameter-Generator (23) gemäß dem nachfolgenden Ausdruck als

(3) Transformieren partieller Quotienten c(k) durch den Parameter-Generator (23) gemäß dem nachfolgenden Ausdruck als

li (b(k - 1)) i - 1/2 - {b(k - 1)A}/rN

li-1 (b(k - 1)) -i + 1/2 - {b(k - 1)A}/rN

wobei b(k - 1) {-r/2, -r/2 + 1, ..., -1, 0, 1, ..., r/2 - 1, r/2}; wobei einen Satz ganzer Zahlen bezeichnet; und wobei i ein i-tes Bit von dem am wenigsten signifikanten Bit bezeichnet, und weiterhin Bestimmen des partiellen Quotienten c(k) der momentanen Stufe durch den Parameter-Generator (23) wie folgt:

c(k) = i, falls li N < R(k - 1) ≤ li+1 N

c(k) = 0, falls li-1 N ≤ R(k - 1) ≤ l&sub1; N

c(k) -i, falls l-i-1 N ≤ R(k - 1) ≤ l-i N

wobei dieselbe, höhere Radix-Zahl r sowohl für den partiellen Multiplikator b(k) als auch für den partiellen Quotienten c(k) angepaßt wird innerhalb eines Bereichs von -r/2 ≤ b, c ≤ r/2, jeweils, um die Zahl berechnungsmäßiger Stufen zu reduzieren; und wobei die Zahl k wiederholter Verarbeitungsstufen bestimmt wird als k ← n/r' + 1 durch die Sequenz-Steuereinheit (25), wobei r eine Radix-Zahl r 2r' bezeichnet, r' ≥ 2 gilt und n/r' eine maximale, ganze Zahl geringer als n/r' bezeichnet, und wobei ← eine Substitution bezeichnet; und

(4) Bestimmen modularer Subtrahierer c(k)N, zuvor durch den modularen Subtrahierer-Generator (33) auf der Basis partieller Produkte b(k - 1)A bestimmt, durch den partiellen Produkt-Generator (31) an der darauffolgenden Stufe (k - 1), um einen absoluten Wert eines partiellen Rests R herunter zu einem Wert geringer als ein Modulus N zu reduzieren.

2. Verfahren nach Anspruch 1, wobei die Stufe eines Transformierens A die Schritte aufweist:

(a) Vergleichen eines absoluten Multiplikanden A mit einem halben Divisor N/2 als A ≤ N/2 oder A N/2;

(b) falls A ≤ N/2 oder A N/2 gilt, Einstellen der Zahl von Bits auf n in jeder Variablen von A, B oder N;

(c) falls A > N/2 gilt, Substituieren A-N für A als A ← A-N und Einstellen der Zahl von Bits auf n in jeder Variablen von A, B oder N.

3. Verfahren nach Anspruch 2, wobei der Schritt eines Vergleichens A mit einem halben Modulus N/2 die Schritte aufweist:

(a) Vergleichen von 2A-N mit Null als 2A-N < 0, wobei A den originalen Multiplikanden A innerhalb eines Bereichs von N > A ≥ 0 bezeichnet;

(b) falls 2A-N ≥ 0 gilt, Einstellen der Zahl von Bits auf n in jeder Variablen von A, B oder N; und

(c) falls 2A-N < 0 gilt, Substituieren A-N für A als A ← A-N, und Einstellen der Zahl von Bits bis n in jeder Variablen von A, B oder N.

4. Verfahren nach Anspruch 2, wobei der Schritt eines Vergleichens A innerhalb eines halben Modulus die Schritte aufweist:

(a) Vergleichen 2Atop- Ntop mit Null als 2Atop - Ntop < 0, wobei Atop die höher signifikanten Bits des Multiplikanden A mehr als ein spezifiziertes Bit innerhalb eines Bereichs von N > A ≥ 0 bezeichnet; und wobei Ntop höher signifikante Bits des Modulus N mehr als dasselbe spezifizierte Bit bezeichnet; und

(b) falls 2Atop - Ntop < 0 gilt, Einstellen der Zahl von Bits auf n in jeder Variablen von A, B oder N; und

(c) falls 2Atop - Ntop ≥ 0 gilt, Substituieren von A-N für A, falls A ← A-N gilt, und Einstellen der Zahl von Bits auf n in jeder Variablen von A, B oder N.

5. Verfahren nach Anspruch 1, wobei die Zahl von Bits auf n in jeder Variablen von A, B oder N durch Einstellen von n als n ← log&sub2;N + 1 eingestellt wird, wobei [log&sub2;N] eine maximale, ganze Zahl geringer als log&sub2;N bezeichnet.

6. Verfahren nach Anspruch 1, wobei dann, wenn eine Bit-Länge des Modulus der modularen Multiplikation auf einen Wert n&sub0; wird, die Zahl von Bits auf n in jeder Variablen von A, B oder N durch die Schritte eingestellt wird:

(a) Prüfen, ob die momentane Verarbeitung schon ausgeführt worden ist, wenn die modulare Multiplikation wiederholt ausgeführt wird;

(g) Prüfen, ob die momentane Stufe (k) Null ist;

(h) falls die momentane Stufe (k) nicht Null ist, Rückkehren zu dem obigen Schritt (b); und

(i) falls die momentane Stufe (k) Null ist, Transformieren eines abschließenden, partiellen Rests R in eine Lösung von A · B Modulo N.

10. Verfahren nach Anspruch 1, wobei der partielle Rest R aktualisiert wird und der partielle Multiplikator b und der Modulus c durch die Schritte gebildet werden:

(a) Initialisieren eines partiellen Quotienten c(k + 1) einer vorhergehenden Stufe zu Null als c(k + 1) ← 0;

(b) Bilden eines partiellen Multiplikators b(k) einer momentanen Stufe;

(c) Aktualisieren eines partiellen Rests R[k - 1] einer drauffolgenden Stufe durch einen partiellen Rest R(k) einer momentanen Stufe, eines partiellen Quotienten c(k + 1) einer vorhergehenden Stufe und eines partiellen Multiplikators b(k) einer momentanen Stufe als R(k - 1) ← r{R(k) - c(k + 1)N} + b(k)A;

(d) Bilden eines partiellen Multiplikators einer darauffolgenden Stufe b(k - 1);

(e) Bilden eines partiellen Quotienten c(k) einer momentanen Stufe;

(f) Fortschreiben der momentanen Stufe (k) als k ← k - 1;

(g) Prüfen, ob die momentane Stufe (k) Null ist;

(h) falls die momentane Stufe (k) nicht Null ist, Zurückkehren zu dem obigen Schritt (c); und

(i) falls die momentane Stufe (k) Null ist, Transformieren eines abschließenden, partiellen Rests R in eine Lösung von A · B Modulo N; und

wobei der abschließende, partielle Rest R durch den abschließenden, partiellen Rest R(0) und den partiellen Quotienten c(1) als R(0) ← R(0) - c(1)N aktualisiert werden.

11. Verfahren nach Anspruch 1, wobei der partielle Rest R der abschließenden Stufe in eine Lösung A · B Modulo N durch die Schritte transformiert wird:

(a) Prüfen, ob der partielle Rest R(0) der abschließenden Stufe als s Multiplikand A für eine darauffolgende, modulare Multiplikations-Berechnung verwendet wird;

(b) falls R(0) verwendet wird, Substituieren des Rests R(0) für A als A R(0);

(c) falls R(0) nicht verwendet wird, Prüfen, ob R(0) ≥ 0 gilt;

(d) falls R(0) ≥ 0 ist, Beenden der Verarbeitungsstufe; und

(e) falls R(0) < 0 ist, Substituieren von R(0) und des Modulus N für R(0) als R(0) ← R(0) + N, vor der Verarbeitungsstufe.

12. Verfahren nach Anspruch 1, wobei dann, wenn eine Bit-Länge des Modulus der modularen Multiplikation ein festgelegtes Volumen ist, der partielle Rest R der abschließenden Stufe in eine Lösung von A · B Modulo N durch die Schritte transformiert wird:

(a) Prüfen, ob der partielle Rest R(0) der abschließenden Stufe als ein Multiplikand A für eine darauffolgende, modulare Multiplikations-Berechnung verwendet wird;

(b) falls R(0) verwendet wird, Substituieren von R(0) für A als A ← R(0) ohne Ändern von N;

(c) Prüfen, ob der partielle Rest R(0) der abschließenden Stufe als s Multiplikand B für eine darauffolgende, modulare Multiplikations-Berechnung verwendet wird;

(d) falls R(0) bestimmt wird, in dem Schritt (c) vorstehend verwendet zu werden, Substituieren eines Rests R(0)/2m einer abschließenden Stufe für B als B ← R(0)/2m und weiterhin Substituieren von R(0)/2m für R(0) als R(0) ← R(0)/2m ;

(e) falls R(0) dahingehend bestimmt wird, nicht im Schritt (c) vorstehend verwendet zu werden, Substituieren von R(0)/2m für R(0) als R(0) R(0)/2m ;

(f) falls R(0) bestimmt wird, nicht im Schritt (a) vorstehend verwendet zu werden, Prüfen, ob R(0) ≥ 0 gilt;

(g) falls R(0) ≥ 0 gilt, Substituieren von R(0)/2m für R(0) als R(0) ← R(0)/2m, was die Verarbeitungsstufe beendet; und

(e) falls R(0) < 0 gilt, Substituieren von R(0) + N für R(0) als R(0) ← R(0) + N und weiterhin R(0)/2m für R(0) als R(0) ← R(0)/2m, was die Verarbeitungsstufe beendet.

13. Verfahren nach Anspruch 1, wobei dann, wenn die Radix-Zahl r ist und der Multiplikator B eine Serie von Bits von B[n], B[n - 1], ..., B[1] ist, der partielle Multiplikator b(k) auf der Basis des Multiplikators B wie folgt gebildet werden kann:

wobei r 2r, r' ≥ 2; B[i] = 0; i > n oder i < 1; B[i] = 1 und i > n, falls B ein Minus- Vorzeichen besitzt, gilt.

14. Verfahren nach Anspruch 13, wobei dann, wenn die Radix-Zahl 4 ist und der Multiplikator B eine Serie von Bits von B[n], B[n - 1], ..., B[1] ist, der partielle Multiplikator b(k) auf der Basis des Multiplikators B wie folgt gebildet werden kann:

b(k) ← -2B[2k] + B[2k - 1] + B[2k - 2]

wobei B[i] = 0; i > n oder i < 1; B[i] = 1 und i > n, falls B ein Minus-Vorzeichen besitzt, gilt.

15. Verfahren nach Anspruch 1, wobei dann, wenn die Radix-Zahl 4 ist und der Multiplikator B in redundanter Repräsentationsform als B = Bs + 2Bc gebildet wird, wobei Bs eine Multiplikator-Summe bezeichnet und wobei Bc einen Multiplikator-Übertrag bezeichnet, der partielle Multiplikator b(k) auf der Basis von zwei Funktionen fs und fc gebildet werden kann wie folgt:

b(k) ← fs(Bs[2k]Bc[2k - 1] und Bs[2k - 1] Bc[2k - 2]) + fc(Bs[2k - 2]Bc[2k - 3] und Bs[2k - 3] Bc[2k - 4]).

16. Verfahren nach Anspruch 15, wobei die Werte von fs und fc auf der Basis einer Referenz-Tabelle nachfolgend in Kombination von Bs[2k]Bc[2k - 1] und Bs[2k - 1] Bc[2k - 2] ausgewählt werden können,

(fs und fc)

x bedeutet, daß Funktionen (fs, fc) nicht irgendwelche Werte haben.

17. Verfahren nach Anspruch 15, wobei die Funktion fc und fs berechnet werden kann durch

fc(Bs[2k]Bc[2k - 1] und Bs[2k - 1]Bc[2k - 2]) Bs[2k] V Bc[2k - 1] V Bs[2k - 1] · Bc[2k - 2])

fs(Bs[2k] Bc[2k - 1] und Bs[2k - 1] Bc[2k - 2]) -2 · Bs[2k] Bc[2k - 1]) + Bs[2k - 1] + Bc[2k - 2] - 4 · · Bs[2k - 1] · Bc[2k - 2],

wobei V die logische Summe bezeichnet; wobei · das logische Produkt bezeichnet; wobei das Exklusiv-ODER bezeichnet; und wobei --- eine Negation bezeichnet.

18. Verfahren nach Anspruch 1, wobei der partielle Quotient c(k) durch Definieren der komparativen Indizes li (b(k - 1)) und li-1 (b(k - 1)) auf der Basis von Atop, Ntop und Rtop gebildet wird, die dieselbe, spezifizierte Zahl von höher signifikanten Bits besitzen, und durch Vergleichen von Rtop mit den Grenz-Indizes, wie beispielsweise als li N oder l-i N.

19. Verfahren nach Anspruch 1, wobei der partielle Quotient c(k) durch die Schritte gebildet wird:

(a) Bestimmen i = R / N + 1, wobei R / N eine maximale, ganze Zahl geringer als R / N bezeichnet;

(b) Prüfen, ob R(k - 1) ≥ 0 gilt;

(c) falls R(k - 1) ≥ 0 gilt, Prüfen, ob li ≤ R(k - 1)/N gilt;

(d) falls li ≤ R(k - 1)/N gilt, Bestimmen von c(k) = i;

(e) falls li ≥ R(k - 1)/N gilt, Bestimmen von c(k) = i - 1;

(f) falls R(k - 1) < 0 gilt, Prüfen, ob l-i ≤ R(k - 1) /N gilt;

(g) falls l-i ≤ R(k - 1) /N gilt, Bestimmen von c(k) = -i; und

(h) falls l-i ≥ R(k - 1) /N gilt, Bestimmen von c(k) = -i + 1.

20. Modulares Multiplikations-System zum Ausführen einer modularen Multiplikation von A · B Modulo N auf der Basis einer Radix-Zahl r, wobei A einen Multiplikanden bezeichnet, wobei B einen Multiplikator bezeichnet und wobei N einen Modulus bezeichnet, das aufweist:

(a) eine erste Registereinrichtung (11) zum Speichern eines Multiplikanden A;

(b) eine zweite Registereinrichtung (13) zum Speichern eines Multiplikators B;

(c) eine dritte Registereinrichtung (15) zum Speichern eines Modulus N;

(d) eine vierte Registereinrichtung (17) zum Speichern eines partiellen Rests R;

(e) eine Normalisierungseinrichtung (21), die auf die dritte Registereinrichtung anspricht, zum Normalisieren des Modulus N;

(f) eine Parameter-Erzeugungseinrichtung (23), die auf die erste, die zweite, die dritte und die vierte Registereinrichtung und die Normalisierungseinrichtung anspricht, zum Erzeugen partieller Multiplikatoren b(k) und partieller Quotienten c(k), wobei (k) eine Zahl von Verarbeitungsstufen bezeichnet;

(g) eine ein partielles Produkt erzeugende Einrichtung (31), die auf die erste Registereinrichtung und die Parameter-Erzeugungseinrichtung anspricht, zum Erzeugen partieller Produkte b(k)A;

(h) eine Erzeugungseinrichtung (33) für modulare Subtrahierer, die auf die dritte Registereinrichtung und die Parameter-Erzeugungseinrichtung anspricht, zum Erzeugen modularer Subtrahierer c(k)N;

(i) eine Erzeugungseinrichtung (35) für einen aktualisierten Rest, die auf die vierte Registereinrichtung anspricht, zum Aktualisieren von Resten R(k);

(j) eine Übertrag-Sicherungs-Addierer-Einrichtung (37), die auf die Erzeugungseinrichtung für das partielle Produkt, die Erzeugungseinrichtung für den modularen Subtrahierer und die den Rest aktualisierende Einrichtung anspricht, zum Ausführen einer Übertrag-Sicherungs-Addition von Rnew rx(Rold - c(k)N) + b(k)A, um den Rest R(k), gespeichert in der vierten Registereinrichtung, zu aktualisieren, wobei Rnew einen aktualisierten Rest bezeichnet;

(k) eine Übertrag-Propagations-Addierer-Einrichtung (39), die auf die Übertrag-Sicherungs-Addierer-Einrichtung anspricht, zum Ausführen einer Übertrag-Propagations-Addition, um den Multiplikanden A, gespeichert in der ersten Registereinrichtung, durch Rnew zu aktualisieren, und Erzeugen einer Lösung von R(0) = A · B Modulo N; und

(l) eine Sequenz-Steuereinrichtung (25), die auf alle die Einrichtungen anspricht, zum sequentiellen Steuern berechnungsmäßiger Operationen,

wobei:

(1) die Parameter-Erzeugungseinrichtung (23) transformiert einen Multiplikanden A [0, N] zu A [-N/2, N/2], um das am meisten signifikante Bit des Multiplikanden A zu eliminieren;

(2) die Parameter-Erzeugungseinrichtung (23) transformiert partielle Multiplikatoren b(k) gemäß dem nachfolgenden Ausdruck als:

(3) die Parameter-Erzeugungseinrichtung (23) transformiert partielle Quotienten c(k) gemäß dem nachfolgenden Ausdruck als:

li (b(k - 1)) i - 1/2 - {b(k - 1)A}/rN

li-1 (b(k - 1)) -i + 1/2 - {b(k - 1)A}/rN

wobei b(k - 1) {-r/2, -r/2 + 1, ..., -1, 0, 1, ..., r/2 - 1, r/2}; wobei einen Satz ganzer Zahlen bezeichnet; und wobei i ein i-tes Bit von dem am wenigsten signifikanten Bit bezeichnet; und

(4) die Parameter-Erzeugungseinrichtung (23) bestimmt den partiellen Quotienten c(k) der momentanen Stufe wie folgt:

c(k) = i, falls li N < R(k - 1) ≤ li+1 +, N

c(k) = 0, falls li-1 , N ≤ R(k - 1) ≤ l&sub1; N

c(k) = -i, falls l-i - 1 N ≤ R(k - 1) ≤ l-i-1 N

wobei dieselbe, höhere Radix-Zahl r für sowohl den partiellen Multiplikator b(k) als auch den partiellen Quotienten c(k) innerhalb eines Bereichs von - r/2 ≤ b, c ≤ r/2 jeweils angepaßt wird, um die Zahl berechnungsmäßiger Stufen zu reduzieren, und wobei die Zahl k wiederholter Verarbeitungsstufen bestimmt wird als k ← n/r' + 1 durch die Sequenz-Steuereinrichtung (25), wobei r eine Radix-Zahl r 2r', r' ≥ 2, gilt, und n/r' eine maximale, ganze Zahl geringer als n/r' bezeichnet, und wobei ← eine Substitution bezeichnet; und

(5) die Erzeugungseinrichtung (33) für den modularen Subtrahierer bestimmt modulare Subtrahierer c(k)N, zuvor auf der Basis partieller Produkte b(k - 1)A bestimmt, durch den Generator (31) für das partielle Produkt, an der darauffolgenden Stufe (k - 1), um einen absoluten Wert eines partiellen Rests R herunter zu einem Wert geringer als einen Modulus N zu reduzieren.

21. Modulares Multiplikations-System nach Anspruch 20, wobei die Normalisierungseinrichtung (21) den Multiplikanden A und den Modulus N als N ← N · 2m, A ← A · 2m transformiert, wobei 2n &supmin; m > N ≥ 2n &supmin; m-1 gilt, wobei n eine Bit-Länge von N bezeichnet und m eine ganze Zahl bezeichnet.

22. Modulares Multiplikations-System nach Anspruch 20, wobei die Parameter-Erzeugungseinrichtung (23) aufweist:

(a) eine Erzeugungseinrichtung (23A) für einen partiellen Multiplikator, die auf die zweite Registereinrichtung anspricht, zum Erzeugen partieller Multiplikatoren b(k) innerhalb eines Bereichs von -r/2 ≤ b ≤ r/2;

(b) eine Erzeugungseinrichtung (23B) für einen partiellen Quotienten, die auf die erste, die dritte und die vierte Registereinrichtung und auf die Erzeugungseinrichtung für den partiellen Multiplikator anspricht, zum Erzeugen partieller Quotienten c(k) innerhalb eines Bereichs von -r/2 ≤ b ≤ r/2;

(c) eine Erzeugungseinrichtung (23C) für einen komparativen Index, die auf die erste und die dritte Registereinrichtung und auf die Erzeugungseinrichtung für den partiellen Multiplikator und den Quotienten anspricht, zum Erzeugen eines komparativen Index l zum Bestimmen eines Bereichs in einem modifizierten Robertson-Diagramm; und

(d) eine Vergleichseinrichtung (23D), die auf die erste und die dritte Registereinrichtung anspricht, zum Vergleichen des Multiplikanden A mit dem Modulus N, um der Erzeugungseinrichtung für den partiellen Multiplikator und den Quotienten zu ermöglichen, b(k) = 1 und c(k) = -1 jeweils zu erzeugen, so daß A zu A - N durch die Erzeugungseinrichtung für das partielle Produkt und den modularen Subtrahierer transformiert wird, wenn A > N/2 oder 2A - N > 0 gilt.

23. Modulares Multiplikations-System nach Anspruch 20, wobei die Sequenz-Steuereinrichtung (25) eine Initialisierung, eine Daten-Übertragung, einen Bit-Verschiebevorgang und eine Verarbeitungsstufen-Zahl-Erniedrigung ausführt.