Fehler bei function (c=m^e mod N)

[negaH]

Die Breakevenpoints zwischen den verschiednene Algorithmen können sehr unterschiedlich sein.
Je nachdem

1.) ob man quadriert oder multipliziert
2.) welche Algorithmen man implementiert hat
3.) wie man diese implementiert hat
4.) ob man inplaced arbeitet oder nicht
5.) auf welchen Prozessoren man arbeitet

In meinem DECMath habe ich für die Multiplikation verschiedene Algos implementiert, Reichenfolge nach Zahlengrößen vom kleinsten zum größten

1.) Schoolboy Methode bis ca. 10 Digits
2.) Comba Methode bis ca. 38 Digits
3.) Karatsuba bis ca. 108 Digits
4.) Toom-Cook-3 bis 5376 Digits
5.) Schönhage FFT ab 5376 Digits aufwärts

1 Digit sind 4 Bytes, ich rechne intern also meistens mit 32Bit Datentypen.

Die Quadrierung benutzt ebenfalls diese Algortihmen aber in spezial Form, ergo ergeben sich ander Breakeven


1.) Schoolboy Methode bis ca. 12 Digits
2.) Comba Methode bis ca. 62 Digits
3.) Karatsuba bis ca. 174 Digits
4.) Toom-Cook-3 bis 5376 Digits
5.) Schönhage FFT ab 5376 Digits aufwärts

Wie man sieht ist die Quadrierung effiziernter als die Multiplikation wodurch sich die Breakeven Points nach oben verschieben.
Man sieht auch das sich die FFT erst mit "gigantisch" großen Zahlen lohnt >>> 2^172032 !

Nun kommts aber, denn diese Breakeven Points gelten ausschließlich für "lame 486'er". Da ich zb. für > Pentium 4 die SSE2 und MMX Befehle in der Schoolboy und FFT und Toom-Cook benutze verändert sich die Breakevens enorm

Multiplikation:

1.) Schoolboy Methode bis ca. 16 Digits
2.) Comba Methode wird nicht benutzt
3.) Karatsuba bis ca. 64 Digits
4.) Toom-Cook-3 bis 5461 Digits
5.) Schönhage FFT ab 5461 Digits aufwärts

Die Comba Methode wird garnicht mehr benutzt, sie ist nur ein Trick in der Schoolboy Methode die die Teilprodukte anders ausrechnet und hat auf Grund der schlechteren oder besseren ? Pipline Architektur der Pentiums keinen Vorteil mehr.
Die größten Performancesteiergerungen bingt die Toom-Cook-3 Methode sowohl in Richtung Karatsuba und in Richtung FFT. In Beiden Richtungen erweitert sie ihren Breakeven Bereich und wird demzufolge häufiger auf Pentiums benutzt als auf anderen 486 Prozessoren (Pentium 2,3 und älter).
Das liegt hautpsächlich daran das ich eben die SS2 Befehle benutze, also quasi 64 Bit Multiplikationen intern durchführe statt 32 Bit breite.

Allerdings muß man das alles relativieren, da eben der Pentium 4 Core im Grunde 2 mal langsammer ist als zb der Pentium 3 Core. Die SSE2 Befehle, die 2 mal schneller sind als normale Befehle, schaffen also erst den realen Performancevorteil eines Pentium 4 im Vergleich zu einem Pentium 3. Ich rede hier NICHT von einem höher getakteten System sondern vergleiche die reale Anzahl der notwendigen Taktzyklen für diese Operationen unabhängig vom Prozessortakt. Der P4 ist also ziemlich lahm.

Klar dürfte auch sein das zb. die Schönhage FFT im innersten Kern auf die Karatsuba Methode und somit wiederum auf die Schoolboy Methode zurückgreift. Das gleiche gilt für Toom-Cook. Sie zerlegt die Zahlen quasi rekursiv bis sie auf diese Teilprodukte die Schoolboy Methode anwendet. Essentiell benötigt man also sehr schnelle Schoolboy Multiplikationen/Quadrierungen und Addtionenen/Subtraktionen/Überlauf/Unterlauf Funktionen.

Gruß Hagen