schnelles Multiplizieren mit Hilfe des chinesischen Restsatz

13/11/2009 - 15:28 von Bernhard Helmes | Report spam
Einen erfreulichen guten Tag,

lohnt sich folgender Algorithmus zum Multiplizieren von großen
Zahlen :

Sei pi Elemente der Primzahlen

Produkt von pi > a*b

c:=a*b

ai:=a mod pi, bi:=b mod pi ausrechnen
ci:=ai*bi mod pi

und mit Hilfe des chinesischen Restsatz c:=ci mod (Produkt von pi)
ausrechnen.

Soviel ich weiß braucht man für das Ausrechnen vom chinesischen
Restsatz nur den erweiterten Euklidischen Algorithmus.

Würde mich freuen, wenn jemand mir eine Abschàtzung zum
Laufzeitverhalten angeben könnte.

Freundliche Grüße
Bernhard
 

Lesen sie die antworten

#1 Christopher Creutzig
13/11/2009 - 19:25 | Warnen spam
Bernhard Helmes wrote:
Einen erfreulichen guten Tag,

lohnt sich folgender Algorithmus zum Multiplizieren von großen
Zahlen :

Sei pi Elemente der Primzahlen

Produkt von pi > a*b

c:=a*b

ai:=a mod pi, bi:=b mod pi ausrechnen
ci:=ai*bi mod pi

und mit Hilfe des chinesischen Restsatz c:=ci mod (Produkt von pi)
ausrechnen.

Soviel ich weiß braucht man für das Ausrechnen vom chinesischen
Restsatz nur den erweiterten Euklidischen Algorithmus.



Schau Dir mal an, was man macht, um den CRS konkret anzuwenden. Da
stehen jede Menge Multiplikationen mit Zahlen, die jeweils bis zum
Produkt aller p[i] durch eines der p[i] groß werden können. Sprich, Du
ersetzt eine Multiplikation von Zahlen der Lànge n durch m kleinere
Multiplikationen zuzüglich m Multiplikationen einer kurzen Zahl mit
einer Zahl der Lànge n^2-epsilon. Klingt so spontan nicht sonderlich
beschleunigend.

Für 10 EUR im Jahr erfahre ich hier sogar was meine Meinung ist.
Andere Leute müssen dafür heiraten.
[Lars Friedrich über UseNet]

Ähnliche fragen