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

**hsg**

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

Ich schreibe mal ein paar Kommentare dazu

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

Zu meinen Brakevens gleich mehr

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

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

ich hab es jetzt folgendermaßen gelöst:

zusammenfalten · markieren

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

zusammenfalten · markieren

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

sonst wäre ich auch nicht auf den Namen gekommen.

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

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

) ist das ein Problem, das direkt im Algorithmus gelöst wird, ich verwende dafür keine eigene Unterroutine.

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

Aber danke dir wieder herzlich für die Informationen, die nächsten Tage habe ich ein Haufen Input's zu verarbeiten

bis denne

Matthias

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

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

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

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

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

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

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

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

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

Forumregeln