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

[Mb123]

Hallo,
ich habe eine funktion geschrieben die mir folgenden ausdruck ausrechnen soll: c=m^e mod N
so hier erstmal die funktion:

Delphi-Quellcode:

[...]
var
  e,m:integer;
[...]
function verschluesseln(q:integer;s:integer):integer;
begin

result:=m^e; mod q*s;
end;

ich erhalte nun folgenden fehler:
[Error] Programm.pas(87): Pointer type required
[Fatal Error] Project5.dpr(5): Could not compile used unit 'Programm.pas'

kann mir einer sagen was ich da verändern muss ? denn mit der meldung kann ich irgendwie nich besonders viel anfangen.

[leddl]

^ steht für einen Pointer :zwinker:
Versuch dein Glück stattdessen mal mit Power der Unit Math ;)

[Mb123]

danke erstmal :) hab jetzt so gemacht :

Delphi-Quellcode:

function Power(Basis,Exponent:Extended):extended;
begin
result := exp(Exponent*ln(Basis))
end;

function verschluesseln(m:integer):integer;
begin
n:=q*s;
result:=Power(m,e) mod n;
end;

nur das problem ist jetzt das ich mit Power(m,e) ja einen extended Wert habe. ich schätz es wird jetzt schwierig diesen wert in einen integer umzuwandeln, denn bei der rsa verschlüsselung sind werte die bei power(m,e) eingesetzt werden schon mal zahlen wie power(133,151). weiß jemand wie ich das problem lösen kann ?

[Mb123]

kann man nicht vielleicht irgendeine langzahlen bibliothek oder sowas implementieren ?
weil mit zahlen wie 291^151 sollte der computer durch irgendwie eine modulo rechnung durch-
führen können ?? mit meinem TI Voyage 200 geht das sogar :shock:

Zitat:

...mit Microsoft Visual C++ 6.0 zu entwickeln.
Um das Rechnen auch mit großen Zahlen zu gewährleisten, musste eine geeignete
Langzahlen-Bibliothek implementiert werden, die den Ansprüchen der einfachen
Implementierung in die Entwicklungsumgebung genügte. Diese Anforderungen wurden
durch die so genannte NTL-Langzahlen-Bibliothek([6]) erfüllt. Die benötigten Funktionen,
wie z. B. der erweiterte Euklidsche Algorithmus wurden unter Verwendung der in
den Quellen [1], [2], bzw. [8] bereitgestellten Pseudo-Codes in die Sprache C++ umgesetzt.

das habe ich in einer arbeit gelesen, in der das problem auch aufgetreten und gelöst wurde.
könnte man sowas auch in delphi umsetzten ?

[MatWur]

eine gute Bibliothek mit Routinen für grosse Ganzzahlen suche ich auch schon lange, bisher ohne Erfolg :roll: Deswegen versuche ich gerade eine für mich zu programmieren, ich hänge aber bei der Multiplikation fest... naja.
Für die Potenzierung gibt es im binären einen sehr schnellen und nicht allzu schwer zu implementierenden Algorithmus, den kannst du in der Wiki nachlesen: http://de.wikipedia.org/wiki/Schnelles_Potenzieren

mfg

Matthias

[Die Muhkuh]

Zitat:

Zitat von MatWur

eine gute Bibliothek mit Routinen für grosse Ganzzahlen suche ich auch schon lange, bisher ohne Erfolg :roll:

Dann kennst Du Hagens DecMath nicht ;)

DecMath

http://www.michael-puff.de/dirindex....agen_Reddmann/

[MatWur]

hm, Danke Schön.
In der Tat kannte ich diese Bibliothek noch nicht, sie sollte für Mb123 eigentlich sehr gut brauchbar sein. Die sieht sehr schön und übersichtlich aus. Für mein Problem hilft sie mir leider nicht. Ich versuche den Schönhage-Strassen-Algorithmus zur schnellen Multiplikation von Binärzahlen zu realisieren, vom Prinzip her habe ich das auch schon. Meine Implementierungen sind aber nicht praktikabel, weil ich noch viel zu viel Speicherplatz während der Multiplikation brauche und dementsprechend auch langsam bin. In der Library ist der Algorithmus implementiert, aber ich bräuchte den Source-Code um mal zu gucken, wie Hagen das Platzproblem gelöst hat... naja, dafür habe ich meinen eigenen Fred (seltsamerweise in Numerik/Optimierung...wieso ich den gerade da reingestellt habe weiss ich nicht mehr so sicher :lol: ), das gehört hier gar nicht her.
Danke nochmal für den Link!

mfg

Matthias

[hsg]

Hmm, darf ich mal fragen, was du für Zahlen multiplizieren möchtest?

Der Schönhage-Strassen-Algo taugt nur was für wirklich extrem große Zahlen. Bei "normalen" Zahlen braucht er wegen den DFTs sogar länger als der normale Schulalgo.

Zitat:

Zitat von Wikipedia

Selbst bei modernen Computern ist diese Methode der Berechnung erst bei Zahlen mit mehreren tausend Stellen effizienter als der Karatsuba-Algorithmus.

[alcaeus]

Ach Jungs...

Warum wollen so viele einen RSA-Algorithmus implementieren, wenn sie denn absolut keine Ahnung von den mathematischen Grundlagen der modulo-Rechnung haben? Das Thema hatten wir schon ein paar Mal, letztens in http://www.delphipraxis.net/internal...t.php?t=102928. Fakt ist: wer bei (a ^ b) mod c zuerst a ^ b ausrechnet, sollte sich dringendst mit Modulorechnungen auseinandersetzen.

Greetz
alcaeus

[MatWur]

@ hsg: ich möchte Zahlen mit bis zu 2^27 Bit multiplizieren können, wenn man mit Mersennezahlen rumspielt kommen solche Grössenordnungen raus. Selbst Karazuba (oder Karatsuba) ist da viel zu langsam. Im Moment müsste der Wiki-Satz übrigens lauten: 'Gerade bei modernen Computern ...' den von steigender Registergrösse (wie momentan von 32 auf 64 Bit) profitiert die Karazuba-Methode stärker als der SchönStrAlg (der profitiert stärker von einer Takterhöhung als die K_Methode)

mfg

Matthias

[hsg]

Zitat:

Zitat von MatWur

@ hsg: ich möchte Zahlen mit bis zu 2^27 Bit multiplizieren können, wenn man mit Mersennezahlen rumspielt kommen solche Grössenordnungen raus. Selbst Karazuba (oder Karatsuba) ist da viel zu langsam. Im Moment müsste der Wiki-Satz übrigens lauten: 'Gerade bei modernen Computern ...' den von steigender Registergrösse (wie momentan von 32 auf 64 Bit) profitiert die Karazuba-Methode stärker als der SchönStrAlg (der profitiert stärker von einer Takterhöhung als die K_Methode)

mfg

Matthias

Okay, bei solchen Zahlen hat das ganze wohl Sinn. Den Karatsuba-Algo kenne ich nicht, daher kann ich nicht vergleichen, ab wann dort der Schönhage-Strassen-Algo wirklich besser wird. Das ganze Thema ist bei mir eh schon ein paar Jahre her (Seminararbeit während des Studiums). Dann wünsche ich dir viel Erfolg damit.

[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

[MatWur]

Hallo Hagen,

vielen Dank für die Erklärungen, das kommt schon näher an das was ich suche :P
Ich schreibe mal ein paar Kommentare dazu

Zitat:

Zitat von 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

Die verschiedenen Algorithmen habe ich erkannt durch die Aufrufdeklarationen. Was 'inplaced' bedeutet ist mir nicht klar. Ich selber arbeite auf einem AMD WinXP 2,4 GHz unter Nutzung des mathematischen Co-Prozessors (ich denke das ist der SSE2 Befehlssatz)

Zitat:

Zitat von negaH

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.

Datentyp Cardinal, habe ich gesehen, Könnte ich mich daran gewöhnen :zwinker: Zu meinen Brakevens gleich mehr :oops:

Zitat:

Zitat von negaH

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 !

Das Quadrierung effizienter ist habe ich mir gedacht (und in dem Testlauf zu deiner Bibliothek wird es ja auch schön dargestellt^^). Wie die Karatsuba-Methode aber für die Quadratur verbessert werden soll ist mir unklar. Bei Karatsuba werden die zu multiplizierenden Zahlen ja in Zifferblöcke zerlegt, die auch bei einer Quadratur schon im ersten Rekursionschritt nicht mehr gleich sein müssem. Schon ab dem 1. Rekursionschritt muss ich also auch bei Quadratur schon wieder zur 'normalen' Multiplikation greifen. Ich erhalte deswegen bei der K-Methode in etwa die gleiche Laufzeit bei Multiplikation und bei Quadratur.

Zitat:

Zitat von negaH

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.

Tom-Cook-3 Methode habe ich schon vom Namen her gehört aber mich noch nicht näher mit befasst, Ich wollte erst den SchönStrAlg realisieren bevor ich versuche ihn zu optimieren :lol: Die Auswirkungen der verschiedenen Prozessoren ist für mich momentan eher nebensächlich, wie gesagt, ich möchte den Alg auf meinem System programmieren, seine Logik verstehen und einfach selber brauchbar zusammen bekommen.

Zitat:

Zitat von negaH

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

Das Eine Multipliaktion bei der rekursiven Berechnung abhängig von der aktuellen Ziffernanzahl in die jeweils beste Methode verzweigt ist klar. Für Add/Sub/Mul mit2/Div durch 2 habe ich schnelle Algorithmen auf Assembler-ebene realisiert, ebenso Karatsuba, die sind gut genug für mich. Überlauf/Unterlauf vermute ich benötigst du bei der Verwendung von Variablen dynamischer Digitlänge. Ich habe da dann einen einfachen, statischen Datenblock vorliegen und sollte wegen der Moduloberechnung solche Routinen nicht brauchen. Mein momentanes Brekeven zwischen Karatsuba und FFT liegt momentan übrigens ca. bei 2^21 Bits Ausgangszahllänge (geschätzt), wenn man weiss, das die K-Methode bei dieser Länge mehrere Sekunden braucht zur Multiplikation, kann man sich vorstellen, das meine Implementierung der FFT noch sehr hmmm... rudimentär ist. Zu den speziellen Problemen aber mehr in meinem Fred. Ich habe gesehen, das du dort auch geantwortet hat. Hier erst mal herzlichen Dank für deine ausführlichen Informationen, das hilft mir sehr. insbesondere Tom-Cook-3 werde ich wohl mal suchen und lernen müssen.

mfg

Matthias

[Mb123]

also um nochmal zu meinem problem zurückzukommen :P
ich hab es jetzt folgendermaßen gelöst:

Delphi-Quellcode:

procedure TForm1.Button9Click(Sender: TObject);

var
  I,e,m,n: Integer;
  s:String;
  b:char;

begin
 ListBox1.Clear;
 ListBox2.Clear;
e:= StrToInt(edit10.text);
n:= StrToInt(edit5.text)*StrToInt(edit4.Text);
i:=1;
s:=Richedit1.Text;
repeat

b:= s[i];
ListBox1.Items.Add(IntToStr(Ord(b)));
m:=Ord(b);
ListBox2.Items.Add(IntToStr(discreteExponent(m,e,n))); {anwendung der funktion c=m^e mod N}
i:=i+1;


until i=Length(RichEdit1.Text);



end;

so jetzt gibt es allerdings folgendes problem:
wenn ich zum Beispiel folgende werte zum testen ver schlüsselung nehme (siehe Attachment), dann kommen auch die gewünschten zahlen raus. nehme ich allerdings größere werte (siehe attachment 2) so erhalte ich falsche ergebnisse für den geheimtext (siehe attachment 3).
kann mir da jemand helfen ? es ist schon recht komisch, dass das ganze bei kleinen werten funktioniert, bei großen jedoch nicht :?
ich erhalte dann auch negative werte als geheimtext(siehe attachment 3), was ja nicht sein kann

[MatWur]

der von dir verwendete Typ 'integer' kann nur Zahlen einer bestimmten Größenordnung aufnehmen, auserdem interpretiert dieser Typ Zahlen >= 2^31 als negative Zahlen. Versuche es einmal damit: ersetze alle Variablen vom Typ 'integer' durch den typ 'ìnt64' und probier es mal damit. Allerdings kann der Diskrete Logarithmus sehr grosse Werte annehmen, evtl tritt auch mit dem noch ein Überlauf ein. Probier es einfach mal aus.

mfg

Matthias

[Mb123]

ok das klappt auch nich :( ich hab jetzt versucht mit der DecMath und den darin enthaltenen IInteger zu arbeiten aber da krieg
ich beim compilen schon "undeclared identifier:'IInteger' .. muss man da was spezielles beim installieren beachten ?
ich hab einfach die test-datei gestartet und über den project manager dann ein neue application geöffnet um das mit den IInteger mal zu testen. kannst du mir sagen wie ich den IInteger benutzen kann bzw. richtig installiere ?

[negaH]

Datentypen müssen ersetzt werden, wie schon erwähnt.

Zitat:

Allerdings kann der Diskrete Logarithmus sehr grosse Werte annehme

Eben nicht (wenn wir das gleiche meinen;) ). Der "diskrete Logarithmus", ich denke du meintest die "diskrete modulare Exponentation" was im Grunde ein falscher Name ist, wir reden von der "binären modularen Exponentation". Dieser Algo. kann eben nicht überlaufen denn die größte Zahl die entstehen kann in diesem Algo. ist exakt 2 mal an Bits größer als das Modulo -> also als das N. Wenn wir N also als Integer deklarieren dann müssen die Multiplikation und Quadrierungen in diesem Algo mit Int64 Datentypen arbeiten. Bedenkt man welche Datengrößen entstehen wenn man erst m^e ausrechnet, Ln2(m)*Ln2(e), dann sind das schon sehr kleine Zahlengrößen mit denen die "binäre Exponentation" auskommt.

Suche mal hier im Forum nach "modulare binäre Exponentation", ich hatte schon einen Source gepostet der mit Int64 arbeitet.

Zitat:

ok das klappt auch nich Sad ich hab jetzt versucht mit der DecMath und den darin enthaltenen IInteger zu arbeiten aber da krieg
ich beim compilen schon "undeclared identifier:'IInteger' .. muss man da was spezielles beim installieren beachten ?
ich hab einfach die test-datei gestartet und über den project manager dann ein neue application geöffnet um das mit den IInteger mal zu testen. kannst du mir sagen wie ich den IInteger benutzen kann bzw. richtig installiere ?

uses NInts, NMath;

mit aufnehmen.

Entpacke das ZIP (das was für deine Delphi Version gültig ist wohlgemerkt, also D5 oder D6 oder D7) mit Ordnerstruktur. Erzeuge einen neuen Unterordnerordner da wo die DCU/Packages liegen. Erzeuge ein neues projekt in diesem Unterordner und setze in den Projektoptionen den Suchpfad auf "..\", also auf den übergeordneten Ornder. Binde nun die gewünschten Units in deinen Uses Klauseln ein -> uses NInts, fertig. Deklariere deine Variablen vom Typ IInteger und benutze die Funktionen aus NInts. Im Ordner \libintf\ findest du die Headers=Interface Sektionen aller Units. In denen kannst du nachschauen welche Funktionen vorhanden sind.

@MatWur:

Zitat:

Was 'inplaced' bedeutet ist mir nicht klar.

Man alloziert zb. den Speicher für das Resultat gleich am Anfang der Funktion und arbeitet nun alle Teiloperationen nur in diesem Speicher ab. Meine Karatsuba Implementierung benötigt zb. ein Ln2(A) + Ln2(B) Bits großes Resultat und intern ein Temporary das 2 * (Ln2(A) + Ln2(B)) groß ist. Alle Operationen sprich Inputs für die rekursiven Karatsuba Aufrufe und deren Outputs arbeiten nun immer in diesem Speicherbereich. Wenn die äußerste Karatsuba zum Aufrufer zurückkehrt steht in diesem Speicher quasi das Resultat das durch die rekursiven Aufrufe der Karatsuba Funktion direkt berechnet wurden. Ich weis nicht ob's dir was bringt aber ich habe mal meinen Karatsuba rangehangen.

Zitat:

Nutzung des mathematischen Co-Prozessors (ich denke das ist der SSE2 Befehlssatz)

Soviel wie ich weis ist das nicht der SSE2 Befehlssatz. SSE2 ist erstmal eine Intel Erfindung, AMD's Counterpart heist anders, denoch haben sich AMD und Intel geeinigt und neuere AMDs unterstützen SSE2. Das hat nichts mit dem Coprozessor zu tuen, der arbeitet mit Fließkommazahlen. Das intern in den CPUs weite Teile des Coprozessors und dieser SSE2 Befehle in den gleichen Recheneinheiten erledigt werden ist dabei nebensächlich. Sogesehen stimmt deine Aussage wiederum indirekt ;)

Zitat:

Datentyp Cardinal, habe ich gesehen, Könnte ich mich daran gewöhnen

Ja, alle meine Routinen arbeiten nur mit Ganzzahlen, sie nutzen also nirgends die Fließkommazahlen des Coprozessors, der ist viel zu langsam.

Zitat:

Wie die Karatsuba-Methode aber für die Quadratur verbessert werden soll ist mir unklar. Bei Karatsuba werden die zu multiplizierenden Zahlen ja in Zifferblöcke zerlegt, die auch bei einer Quadratur schon im ersten Rekursionschritt nicht mehr gleich sein müssem. Schon ab dem 1. Rekursionschritt muss ich also auch bei Quadratur schon wieder zur 'normalen' Multiplikation greifen. Ich erhalte deswegen bei der K-Methode in etwa die gleiche Laufzeit bei Multiplikation und bei Quadratur.

Die Karatsuba-Sqr ist natürlich schneller als die Mul, ca. 1.5 mal. Auch diesen Source habe ich mal unten rangehangen. Das sieht ma auch am Source im Vergleich, die Sqr ist viel kompakter hat also weniger Sonderfälle zu berücksichtigen, ergo performanter und ruft natürlich im Innersten auch die Sqr-Schoolboy Methode auf die eben ihrerseits 1.5 mal schneller sein sollte als eine Schoolboy Multiplikation.

Zitat:

Überlauf/Unterlauf vermute ich benötigst du bei der Verwendung von Variablen dynamischer Digitlänge.

Nein. Das sind Funktionen die quasi 1 Digit zu einem großen Speicherbereich addieren/subtrahieren. Wenn wei zb. bei Karatsuba inplaced unsere Zahlen zerlegt haben,rekursiv immer die Hälte von der Hälfte, dann müssen wir nach deren Multiplikation ja das Resultat wieder zusammenbauen. Bei dieser Operation entstehen Über/Unterläufe, Carry, die wir dann natürlich in die anderen Hälten des Resultates einrechnen müssen. Dazu benötigt man also Funktionen die zb. die Zahl +1 in eine große Zahle reinrechnen, ein Carry eben.

DIncD() wäre zb. so eine Funktion bei mir, "Digit-Speicher Increment with one Digit" -> 1 Digit = 32 Bit.

Zitat:

Toom-Cook-3

Das ist Karatsuba aber man splittet in 3 Teile statt nur 2 Hälften. Es gibt demzufolge auch eine Toom-Cook-5,-7,-11 und so weiter.

Gruß Hagen

Delphi-Quellcode:

var
  DMulS: function(R,A: Pointer; AC: Cardinal; B: Pointer; BC: Cardinal): Integer = _DMulS;

function DMulK(R,A: PDigits; AC: Integer; B: PDigits; BC: Integer; T: PDigits): Integer; register;
// Karatsuba Mul, don't call directly use DMulN()
// R[] = A[] * B[], A are AC digits and B are BC digits long
// T temporary workspace must be 2(AC + BC) digits
// R must be (AC + BC) digits
// returns R.Count
// we use goto's because faster
var
  I,J,K,A0,A1,R0,R1: Integer;
label
  Null, Finish;
begin
  NCalcCheck;
// first stage, remove leading zero's and recalc sizes,
  I := AC + BC;
  if A[AC -1] = 0 then AC := DNorm(0, A, AC -1);
  if AC > 0 then
  begin
    if B[BC -1] = 0 then BC := DNorm(0, B, BC -1);
    if BC = 0 then AC := 0;
  end else BC := 0;
  Result := AC + BC;
  if Result < I then
  begin
    while I > Result do
    begin
      Dec(I);
      R[I] := 0;
    end;
//    DFill(0, @R[Result], I - Result);
    if Result = 0 then Exit;
  end;

// swap such that A >= B
  if AC < BC then
  begin
    I := AC; AC := BC; BC := I;
    Pointer(J) := A; A := B; B := Pointer(J);
  end;
// smaller Mul possible ?
  if BC < Mul_KBE then
  begin
    Result := DMulS(R, A, AC, B, BC);
    Exit;
  end;
// second stage, do Karatsuba dependend on the sizes of A and B
  if AC = BC then
  begin
    A0 := AC shr 1;
    J := 0;
    if not Odd(AC) then
    begin
      I := DCmpN(A, @A[A0], A0);
      if I = 1 then DSubN(R, A, @A[A0], A0) else
        if I = -1 then
        begin
          DSubN(R, @A[A0], A, A0);
          J := 1;
        end else DFill(0, R, A0);
      I := DCmpN(B, @B[A0], A0);
      if I = 1 then DSubN(@R[A0], B, @B[A0], A0) else
        if I = -1 then
        begin
          DSubN(@R[A0], @B[A0], B, A0);
          J := J xor 1;
        end else DFill(0, @R[A0], A0);
      DMulK(T, R, A0, @R[A0], A0, @T[AC]);
      DMulK(R, A, A0, B, A0, @T[AC]);
      DMulK(@R[AC], @A[A0], A0, @B[A0], A0, @T[AC]);
      if J <> 0 then J := DAddN(T, T, R, AC)
        else J := -DSubN(T, R, T, AC);
      Inc(J, DAddN(T, T, @R[AC], AC));
      Inc(J, DAddN(@R[A0], @R[A0], T, AC));
      if J <> 0 then DIncD(J, @R[AC + A0], A0);
    end else
    begin
      A1 := AC - A0;
      K  := A[A0];
      if K <> 0 then Dec(K, DSubN(R, A, @A[A1], A0)) else
      begin
        I := DCmpN(A, @A[A1], A0);
        if I = 1 then DSubN(R, A, @A[A1], A0) else
          if I = -1 then
          begin
            DSubN(R, @A[A1], A, A0);
            J := 1;
          end else DFill(0, R, A0);
      end;
      R[A0] := K;
      K := B[A0];
      if K <> 0 then Dec(K, DSubN(@R[A1], B, @B[A1], A0)) else
      begin
        I := DCmpN(B, @B[A1], A0);
        if I = 1 then DSubN(@R[A1], B, @B[A1], A0) else
          if I = -1 then
          begin
            DSubN(@R[A1], @B[A1], B, A0);
            J := J xor 1;
          end else DFill(0, @R[A1], A0);
      end;
      R[AC] := K;
      R0 := AC +1;
      DMulK(T, R, A1, @R[A1], A1, @T[R0]);
      DMulK(R, A, A1, B, A1, @T[R0]);
      DMulK(@R[R0], @A[A1], A0, @B[A1], A0, @T[R0]);
      if J <> 0 then DAddN(T, R, T, R0)
        else DSubN(T, R, T, R0);
      R1 := AC -1;
      if DAddN(T, T, @R[R0], R1) <> 0 then
      begin
        I := T[R1] + 1;
        T[R1] := I;
        if I = 0 then Inc(T[AC]);
      end;
      if DAddN(@R[A1], @R[A1], T, R0) <> 0 then
        DIncD(1, @R[R0 + A1], A0);
    end;
    goto Finish;
  end;
  A0 := (AC +1) shr 1;
  if A0 < BC then
  begin
    A1 := AC - A0;
    R0 := A0 + A0;
    R1 := A1 + BC - A0;
    if A0 > A1 then
    begin //  A1 - A0
      if A[A1] = 0 then
      begin
        I := DSubC(R, @A[A0], A, A1);
        if I = 1 then R[A1] := TDigit(-1)
          else R[A1] := 0;
      end else
      begin
        R[A1] := TDigit( -Integer(A[A1]) - DSubN(R, @A[A0], A, A1) );
        I := 1;
      end;
    end else
       I := DSubC(R, @A[A0], A, A0);
    if I = 0 then goto Null;
    J := BC - A0; // B1
    if A0 > J then // B0 - B1
    begin
      DMoveZero(@B[A0], T, J, A0);
      J := DSubC(@R[A0], B, T, A0);
    end else
      J := DSubC(@R[A0], B, @B[A0], A0);
    if J = 0 then goto Null;
    DMulK(T, R, A0, @R[A0], A0, @T[R0]);
    if I = -1 then
    begin
      I := -J;
      if I = -1 then I := -DSubN(@T[A0], @T[A0], R, A0)
        else I := 0;
    end else
    begin
      I := J;
      if DSubN(@T[A0], @T[A0], @R[A0], A0) = 0 then Inc(I);
      if I = 1 then
      begin
        DSubN(@T[A0], @T[A0], R, A0);
        I := 0;
      end;
    end;
    J := DMulK(R, A, A0, B, A0, @T[R0]);
    if (J > 0) and (DAddN(T, T, R, J) <> 0) then
    begin
      K := R0 - J;
      if K > 0 then I := I + DIncD(1, @T[J], K)
        else Inc(I);
    end;
    J := DMulK(@R[R0], @A[A0], A1, @B[A0], BC - A0, @T[R0]);
    if (J > 0) and (DAddN(T, T, @R[R0], J) <> 0) then
    begin
      K := R0 - J;
      if K > 0 then I := I + DIncD(1, @T[J], K)
        else Inc(I);
    end;
    I := I + DAddN(@R[A0], @R[A0], T, R0);
    if I > 0 then
      DIncD(I, @R[R0 + A0], A0);
    goto Finish;
  end;
// A is twice of B
  if A0 = BC then
  begin
    Dec(A0);
    A1 := AC - A0;
    R0 := A0 + A0;
    R1 := A0 + A1;  // !!!!
    //   A1 - A0
    R[A0] := A[R0];
    I := A1 - A0;
    if I = 2 then
      R[A0 + 1] := A[R0 + 1];
    if DSubN(R, @A[A0], A, A0) <> 0 then
      DDecD(1, @R[A0], I);
    // B0 - B1
    DMove(B, @R[A1], A0);
    TDigit(I) := R[A1];
    TDigit(K) := TDigit(I) - B[A0];
    R[A1] := TDigit(K);
    if TDigit(K) > TDigit(I) then I := -DDecD(1, @R[A1 +1], A0 -1)
      else I := 0;
    DMulK(T, R, A1, @R[A1], A0, @T[AC]);
    if I = -1 then
      DSubN(@T[A0], @T[A0], R, A1);
    J := DMulK(R, A, A0, B, A0, @T[AC]);
    if (J > 0) and (DAddN(T, T, R, J) <> 0) then
    begin
      K := R1 - J;
      if K > 0 then I := I + DIncD(1, @T[J], K)
        else Inc(I);
    end;
    J := DMulK(@R[R0], @A[A0], A1, @B[A0], BC - A0, @T[AC]);
    if (J > 0) and (DAddN(T, T, @R[R0], J) <> 0) then
    begin
      K := R1 - J;
      if K > 0 then I := I + DIncD(1, @T[J], K)
        else Inc(I);
    end;
    I := I + DAddN(@R[A0], @R[A0], T, R1);
    if I > 0 then
    begin
      A0 := A0 + R1;
      DIncD(I, @R[A0], AC + BC - A0);
    end;
    goto Finish;
  end;
// 1.)   large digits MUL, remarks see below, A is more as twice long as B
  if not Odd(Cardinal(AC) div Cardinal(BC)) then
  begin
    DMulK(R, A, BC, B, BC, T);
    DMove(@R[BC], T, BC);
    I := BC;
  end else I := 0;
  Dec(AC, BC + BC);
  repeat
    if I > AC then Break;
    DMulK(@R[I], @A[I], BC, B, BC, @T[I]);
    Inc(I, BC);
    if I > AC then Break;
    DMulK(@T[I - BC], @A[I], BC, B, BC, @T[I + BC]);
    Inc(I, BC);
  until False;
  AC := AC + BC + BC - I;
  if AC > 0 then DMulK(@R[I], B, BC, @A[I], AC, @T[I + BC])
    else Dec(I, BC);
  if DAddN(@R[BC], @R[BC], T, I) <> 0 then
    if AC > 0 then
      DIncD(1, @R[BC + I], AC);
  goto Finish;
Null:
// A0 - A1 = 0 or B1 - B0 = 0,
// special case, we can leave some calculations
  DMulK(R, A, A0, B, A0, T);
  DMulK(@R[R0], @A[A0], A1, @B[A0], BC - A0, T);
  I := DAddN(T, R, @R[R0], R1);           // T01 := [R01] + R23
  if DAddN(@R[R1 + A0], @R[R1 + A0], @R[R1], R0 - R1) <> 0 then  // [R12] := [R12] + [R01]
    I := I + DIncD(1, @R[R0 + A0], R1 - A0);
  I := I + DAddN(@R[A0], @R[A0], T, R1);          // [R12] := [R12] + T01
  if I > 0 then
    DIncD(I, @R[R1 + A0], A0);
Finish:
// correct result, speedup outer Karatsuba
//  if R[Result -1] = 0 then Dec(Result);
  Result := DNorm(0, R, Result);
end;

{ Remark on point 1.) Karatsuba/TOOM large Digit Mul,
  here are A.Count > 2 * B.Count,
    Instead to split symmetric and call DMulK() recursive again we use a
    large digit MUL of B.Count Digitsize. The Results of each large Digit MUL
    are stored interleaved into R and T

     A0A1 A2A3 A4A5 A6A7          * B0B1

     C0C1 C2C3             <- A0A1 * B0B1
     D0D1 D2D3          <- A2A3 * B0B1
          E0E1 E2E3       <- A4A5 * B0B1
          F0F1 F2F3  <- A6A7 * B0B1

stored interleaved into R and T and added with only ONE final addition

  R  C0C1 D0D1 D2D3 F0F1 F2F3
+ T     C2C3 E0E1 E2E3

= R  R0R1 R2R3 R4R5 R6R7 R8R9

In above case we avoid many useloss moves/coping and reduce it to maximal
one move of C2C3 from R to T.
Same method is applied for asymmetric Toom-Cook Multiplication.
}

var
  DSqrS: function(R,A: Pointer; C: Cardinal): Integer = _DSqrS;

function DSqrK(R,A: PDigits; C: Integer; T: PDigits): Integer;
// karatsuba Square, don't call directly use DSqrN()
// R[] = A[]², A are C digits long, R are 2C digits long,
// T temporary must be 2C digits long
var
  I,D,J: Integer;
begin
  NCalcCheck;
  I := C + C;
  if A[C -1] = 0 then
  begin
    C := DNorm(0, A, C -1);
    D := C + C;
    DFill(0, @R[D], I - D);
    Result := D;
    if D = 0 then Exit;
  end else Result := I;
  if C < Sqr_KBE then
  begin
    Result := DSqrS(R, A, C);
    Exit;
  end;
  D := C shr 1;
  if Odd(C) then
  begin
    I := D +1;
    TDigit(J) := A[D];
// code with implicit comparsion in subtraction and postprocessed correction if overflow is detected
    if DSubN(R, A, @A[I], D) <> 0 then
      if J = 0 then DCplN(R, R, D) // we must inverse our overflow
   else Dec(J);
// code with preprocessing comparsion to detect overflows,
// suppose <50% of our computation produce overflows then above code avoids >50% comparsions
{    if J = 0 then
    begin
      case DCmpN(A, @A[I], D) of
   1: DSubN(R, A, @A[I], D);
       -1: DSubN(R, @A[I], A, D);
   0: DFill(0, R, D);
      end;
    end else Dec(J, DSubN(R, A, @A[I], D));}
    R[D] := TDigit(J);
    Inc(C);

    DSqrK(T, R, I, @T[C]);
    DSqrK(R, A, I, @T[C]);
    DSqrK(@R[C], @A[I], D, @T[C]);

    DSubN(T, R, T, C);
    if DAddN(T, T, @R[C], C -2) <> 0 then
    begin
      TDigit(J) := T[C - 2] + 1;
      T[C -2] := TDigit(J);
      if J = 0 then Inc(T[C -1]);
    end;
    if DAddN(@R[I], @R[I], T, C) <> 0 then
      DIncD(1, @R[C + I], D);
  end else
  begin
// code with implicit comparsion in subtraction
    I := DSubC(R, @A[D], A, D);
    if I <> 0 then
    begin
      if I > 0 then DCplN(R, R, D);
      DSqrK(T, R, D, @T[C]);
    end;
// code with comparsion
{    I := DCmpN(A, @A[D], D);
    if I <> 0 then
    begin
      if I > 0 then DSubR(A, @A[D], D, R)
   else DSubR(@A[D], A, D, R);
      DSqrK(T, R, D, @T[C]);
    end;}

    DSqrK(@R[C], @A[D], D, @T[C]);
    J := DSqrK(R, A, D, @T[C]);
    if I <> 0 then
    begin
//   I := DSubR(R, T, C, T) + DAddN(T, @R[C], C) + DAddN(@R[D], T, C);
      I := DSubN(T, T, @R[C], C);
      if (J > 0) and (DSubN(T, T, R, J) <> 0) then
   Inc(I, DDecD(1, @T[J], C - J));
      Dec(I, DSubN(@R[D], @R[D], T, C));
    end else
      if J > 0 then I := DAddN(T, R, @R[C], C) + DAddN(@R[D], @R[D], T, C)
   else I := DAddN(@R[D], @R[D], @R[C], C);
    if I > 0 then DIncD(I, @R[D + C], D);
  end;
// correct result, speedup outer Karatsuba
  if R[Result -1] = 0 then Dec(Result);
end;

[MatWur]

Hallo Hagen,
Beispielprogramm und innere Zitate wegen Doppelquote gelöscht

Zitat:

Zitat von negaH

Datentypen müssen ersetzt werden, wie schon erwähnt.

Eben nicht (wenn wir das gleiche meinen;) ). Der "diskrete Logarithmus", ich denke du meintest die "diskrete modulare Exponentation" was im Grunde ein falscher Name ist, wir reden von der "binären modularen Exponentation". Dieser Algo. kann eben nicht überlaufen denn die größte Zahl die entstehen kann in diesem Algo. ist exakt 2 mal an Bits größer als das Modulo -> also als das N. Wenn wir N also als Integer deklarieren dann müssen die Multiplikation und Quadrierungen in diesem Algo mit Int64 Datentypen arbeiten. Bedenkt man welche Datengrößen entstehen wenn man erst m^e ausrechnet, Ln2(m)*Ln2(e), dann sind das schon sehr kleine Zahlengrößen mit denen die "binäre Exponentation" auskommt.

Suche mal hier im Forum nach "modulare binäre Exponentation", ich hatte schon einen Source gepostet der mit Int64 arbeitet.

Die Bezeichnung Diskreter Logarithmus habe ich nur verwendet, weil Mb123 so seine Funktion bezeichnet hat :wink: sonst wäre ich auch nicht auf den Namen gekommen.

Zitat:

Zitat von negaH

@MatWur:

Man alloziert zb. den Speicher für das Resultat gleich am Anfang der Funktion und arbeitet nun alle Teiloperationen nur in diesem Speicher ab. Meine Karatsuba Implementierung benötigt zb. ein Ln2(A) + Ln2(B) Bits großes Resultat und intern ein Temporary das 2 * (Ln2(A) + Ln2(B)) groß ist. Alle Operationen sprich Inputs für die rekursiven Karatsuba Aufrufe und deren Outputs arbeiten nun immer in diesem Speicherbereich. Wenn die äußerste Karatsuba zum Aufrufer zurückkehrt steht in diesem Speicher quasi das Resultat das durch die rekursiven Aufrufe der Karatsuba Funktion direkt berechnet wurden. Ich weis nicht ob's dir was bringt aber ich habe mal meinen Karatsuba rangehangen.

inplaced ist mir durch deine Antwort in meinem FFT-Fred schon klar geworden, die geringe Menge an Speicher will mir noch nicht so recht in den Kopf gehen. Aber ich werde deine Beispielroutinen durchgehen, dann wird mir hoffentlich einiges klarer. Aber ohne praktisches Beispiel ist sowas immer schwer nach zu vollziehen. Zumindestens mir geht es so :angel:

Zitat:

Zitat von negaH

Soviel wie ich weis ist das nicht der SSE2 Befehlssatz. SSE2 ist erstmal eine Intel Erfindung, AMD's Counterpart heist anders, denoch haben sich AMD und Intel geeinigt und neuere AMDs unterstützen SSE2. Das hat nichts mit dem Coprozessor zu tuen, der arbeitet mit Fließkommazahlen. Das intern in den CPUs weite Teile des Coprozessors und dieser SSE2 Befehle in den gleichen Recheneinheiten erledigt werden ist dabei nebensächlich. Sogesehen stimmt deine Aussage wiederum indirekt ;)

Ja, alle meine Routinen arbeiten nur mit Ganzzahlen, sie nutzen also nirgends die Fließkommazahlen des Coprozessors, der ist viel zu langsam.

hmmm, auf meinem Computer ist der Coprozessor deutlich schneller als die Ganzzahlarithmetik, auch wenn er Gleitkommazahlen berechnet. Bei Berechnungen mit 4 oder 5 Operationen lohnt es sich sogar mit Runden und zurückspeichern in einen Ganzzahlwert. Vielleicht habe ich eine völlig falsche Vorstellung von SSE2... mit Hardwareinterna und Befehlssätzen habe ich mich schon lange nicht mehr befasst. Black Box Computer.

Zitat:

Zitat von negaH

Die Karatsuba-Sqr ist natürlich schneller als die Mul, ca. 1.5 mal. Auch diesen Source habe ich mal unten rangehangen. Das sieht ma auch am Source im Vergleich, die Sqr ist viel kompakter hat also weniger Sonderfälle zu berücksichtigen, ergo performanter und ruft natürlich im Innersten auch die Sqr-Schoolboy Methode auf die eben ihrerseits 1.5 mal schneller sein sollte als eine Schoolboy Multiplikation.

Über die Karatsuba-Methode haben wir gerade in meinem Matheforum diskutiert, ich wage mal folgende Behauptung aus Intuition heraus: die Zeitersparnis bei deiner Quadratur (und die ist im Testprogramm zu deiner Bibliothek ja klar ersichtlich) wird zu 99% durch die Zeitersparnis der Sqr-Schoolboy Methode 'erzeugt', nur sehr wenig der gesamten Zeitersparnis von der speziellen Methode(n) während der Karatsuba-Rekursion. Das könnte man in etwa so zeigen: Quadriere Zahlen, die gerade noch nur mit der Sqr-Schoolboy Methode abgearbeitet werden können und miss die Zeitersparnis gegenüber der Multiplikation. Bereits diese hohen 'nur Sqr-Schoolboy Methode'-Zahlen werden eine Zeitersparnis von ca 33% erbringen. Quadrierst du dann Zahlen bis zur Maximalgrösse für Karatsuba wird sich diese Zeitersparnis prozentual nur sehr wenig weiter erhöhen. Aber wie gesagt, ich schaue mir das Beispielprogramm genau an sobald ich dazu komme.

Zitat:

Zitat von negaH

Nein. Das sind Funktionen die quasi 1 Digit zu einem großen Speicherbereich addieren/subtrahieren. Wenn wei zb. bei Karatsuba inplaced unsere Zahlen zerlegt haben,rekursiv immer die Hälte von der Hälfte, dann müssen wir nach deren Multiplikation ja das Resultat wieder zusammenbauen. Bei dieser Operation entstehen Über/Unterläufe, Carry, die wir dann natürlich in die anderen Hälten des Resultates einrechnen müssen. Dazu benötigt man also Funktionen die zb. die Zahl +1 in eine große Zahle reinrechnen, ein Carry eben.

DIncD() wäre zb. so eine Funktion bei mir, "Digit-Speicher Increment with one Digit" -> 1 Digit = 32 Bit.

ah ja, das wird klar. Da ich solche Algorithmen immer sehr kompakt programmiere (bei weiten nicht so schön und modular wie bei dir :mrgreen: ) ist das ein Problem, das direkt im Algorithmus gelöst wird, ich verwende dafür keine eigene Unterroutine.

Zitat:

Zitat von negaH

Das ist Karatsuba aber man splittet in 3 Teile statt nur 2 Hälften. Es gibt demzufolge auch eine Toom-Cook-5,-7,-11 und so weiter.

Gruß Hagen

Klingt eigentlich logisch. Dann wird auch klar warum diese Algorithmen gestaffelt immer noch ein bischen Zeitersparnis auf den letzten draufpacken. Muss ich auch mal genauer durchleuchten.
Deine Routinen werde ich genauer durchleuchten und dich dann evtl. noch mal mit ein paar Fragen quälen^^ Für weitere Diskussionen sollten wir dann besser meinen Fred mit den FFT's nehmen, sonst gerate ich noch in den Verdacht Mb123's Fred zu misbrauchen :angel2:
Aber danke dir wieder herzlich für die Informationen, die nächsten Tage habe ich ein Haufen Input's zu verarbeiten :zwinker:

bis denne

Matthias