Exponentieren und dann Modulo: große Zahlen

[tuxianer]

Hallo,
ich habe jetzt den Code implementiert:

Delphi-Quellcode:

function tform1.mod_exp(basis,exponent,modulo:integer):int64;
var e:Integer;
begin
  e:=1;
  while (exponent>0) do begin
    if (exponent mod 2 > 0) then e:=(e*basis) mod modulo;
    basis:=(basis*basis) mod modulo;
    exponent:=exponent div 2;
  end;
  result:=e;
end;

Bei Größeren Zahlen kommt aber mist raus z.B.

666^58613 mod 81079=-38808

Rauskommen müsste aber: 49371.

Woran kann das liegen? Mit kleineren Zahlen gehts 1a!

[Fussball-Robby]

Ich denke, 666^58613 sprengt sogar den Anwendungsbereich von Int64. Nimm einfach mal den Windows Rechner. Int64 hat 64 Bit, kommt also bis 2^64. Das kann der Rechner noch anzeigen. Bei deiner Rechnung kommt selbst der Windows-Rechner nicht mehr mit. Es gibt also einen Owerflow.

[tuxianer]

das hab ich mir auch schon überlegt. aber dann gibts ja keine größeren ganzzahl typen. Wie kann ich mir da selbst welche erstellen? Aber eigentlich exponentiert das doch schrittweise. das Ergebnis ist ja nicht groß.

[Fussball-Robby]

Es gibt eine Unit mit dem Zahlentyp BigInt. Einfach mal danach suchen. Ob die allerdings mit solch großen Zahlen zurechtkommt, weiß ich nicht.

[mquadrat]

Ich nehm an du hast das mal per Hand ausgerechnet? Dann lass dir doch in jedem Schritt die Werte deiner Variablen ausgeben. Daraus kannst du ablesen, ob deine Funktion ein generelles Problem hat oder in einem der Schritte "kippt".

[Fussball-Robby]

Zitat:

Zitat von mquadrat

Ich nehm an du hast das mal per Hand ausgerechnet?

Ganz sicherlich nicht :shock: 666^58613... Das sähe so aus: 666x666x666x666x666x666.... und das 58613 mal!

[himitsu]

schalte doch einfach mal die Überlaufprüfung ein, :angel2:

{$Q+} or {$OVERFLOWCHECKS ON}

dann bekommst du eine Meldung bei Überscheitung der Wertebereiche.


ansonsten bleibt dir nur der Werg über sowas wie BigInt.


TBigInt und auch im DEC ist 'ne Bibo für große Zahlen drin DEC-Math

[Neutral General]

Zitat:

Zitat von Fussball-Robby

Zitat:

Zitat von mquadrat

Ich nehm an du hast das mal per Hand ausgerechnet?

Ganz sicherlich nicht :shock: 666^58613... Das sähe so aus: 666x666x666x666x666x666.... und das 58613 mal!

Ja und? Wofür hat man denn in der Grunschule schriftliches multiplizieren gelernt? :mrgreen:

[mquadrat]

Zitat:

Zitat von Fussball-Robby

Ganz sicherlich nicht :shock: 666^58613... Das sähe so aus: 666x666x666x666x666x666.... und das 58613 mal!

Lies dir doch mal den Algorithmus in der Frage durch... Nennt sich schnelles Exponenzieren. Das mussten wir in der Kryptographie-Klausur mit einem simplen Taschenrechner machen ;) Er kann ja auch andere Zahlen nehmen. Es geht nur drum, ob seine Implementierung prinzipiell richtig ist und nur bei "bestimmten" Zahlen Mist rechnet, oder ob sie komplett falsch ist.

[himitsu]

ist dir übrigens schon aufgefallen, daß e nur ein Integer ist, also ist Result (Result:=e) auch nur ein Integer :shock:

[mquadrat]

Integer würde NACH der Modulo Operation ja auch langen, allerdings kann natürlich e*basis und basis*basis den Integer-Wertebereich sprengen.

[tuxianer]

ja danke das integer bei e hat ich übersehen. jetzt gehen die zahlen ein wenig höher. es kommt ein overflow! wie bekomme ich variablen mit ca 256 bit hin?

[gammatester]

Zitat:

Zitat von tuxianer

Hallo,
ich habe jetzt den Code implementiert:

Delphi-Quellcode:

function tform1.mod_exp(basis,exponent,modulo:integer):int64;
var e:Integer;
begin
  e:=1;
  while (exponent>0) do begin
    if (exponent mod 2 > 0) then e:=(e*basis) mod modulo;
    basis:=(basis*basis) mod modulo;
    exponent:=exponent div 2;
  end;
  result:=e;
end;

Bei Größeren Zahlen kommt aber mist raus z.B.

666^58613 mod 81079=-38808

Rauskommen müsste aber: 49371.

Woran kann das liegen? Mit kleineren Zahlen gehts 1a!

Das liegt daran, daß 81079* 81079 = 6573804241 > 2^31 ist. Mach alle Variablen int64, dann geht's.

Gruß Gammateser

[himitsu]

stümmt, geht aber immernoch nicht richtig ... und irgendwie bekomm ich keine Fehlermeldung o.O

Delphi-Quellcode:

{$OVERFLOWCHECKS ON}
{$RANGECHECKS ON}

function mod_exp(basis, exponent, modulo: Integer): Int64;
var basis64: Int64;
begin
  Result  := 1;
  basis64 := basis;
  while exponent > 0 do begin
    if exponent and $1 <> 0 then Result := (Result * basis64) mod modulo;
    basis64  := (basis64 * basis64) mod modulo;
    exponent := exponent div 2;
  end;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  Caption := IntToStr(mod_exp(666, 58613, 81079));
end;

nja mit TBigInt

mein kleiner 512-Bit Integer ist noch nicht ganz fertig (die Grundrechenarten sollten in einigen Tagen aber laufen)

[gammatester]

Zitat:

Zitat von tuxianer

ja danke das integer bei e hat ich übersehen. jetzt gehen die zahlen ein wenig höher. es kommt ein overflow! wie bekomme ich variablen mit ca 256 bit hin?

Mit 256-Bit-Input müssen die Zwischenergebnisse mindestens 512-Bit fassen können. Das wirst Du nicht mit Standarddatentypen schaffen, da sind Multipräzisionszahlen erforderlich. Wenn's pressiert, kannst Du meine Opensource Pascal-Bibliothek MPArith benutzen
http://home.netsurf.de/wolfgang.ehrh...e.html#mparith
oder als Direktlink http://home.netsurf.de/wolfgang.ehrh...2008-02-03.zip

Hier das Beispiel mit dem t_calc-Programm

[D]:=> 666^ 58613 mod 81079
Result = 11771

bzw mit etwas größerem Modul

[D]:=> x=2^234+1
X = 27606985387162255149739023449108101809804435888681 546220650096895197185

[D]:=> 666^58613 mod x
Result = 68076830550130780093976621121303037225758314086178 25255201034417937691


Gruß Gammatester

[gammatester]

Zitat:

Zitat von himitsu

stümmt, geht aber immernoch nicht richtig ... und irgendwie bekomm ich keine Fehlermeldung o.O

Delphi-Quellcode:

{$OVERFLOWCHECKS ON}
{$RANGECHECKS ON}

function mod_exp(basis, exponent, modulo: Integer): Int64;
var basis64: Int64;
begin
  Result  := 1;
  basis64 := basis;
  while exponent > 0 do begin
    if exponent and $1 <> 0 then Result := (Result * basis64) mod modulo;
    basis64  := (basis64 * basis64) mod modulo;
    exponent := exponent div 2;
  end;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  Caption := IntToStr(mod_exp(666, 58613, 81079));
end;

nja mit TBigInt

mein kleiner 512-Bit Integer ist noch nicht ganz fertig (die Grundrechenarten sollten in einigen Tagen aber laufen)

Also mein Delphi 6 rechnet mit Deinem Code richtig 11771 aus. Was sollte denn Deiner Meinung nach rauskommen?
Gammatester

[tuxianer]

ja jetzt klappt es für die Zahlen größe. Aber für noch größere Zahlen immer noch nicht.

[gammatester]

Zitat:

Zitat von tuxianer

ja jetzt klappt es für die Zahlen größe. Aber für noch größere Zahlen immer noch nicht.

Für welche Werte klappt es nicht? Wie gesagt: der code kann nicht funktionieren für Werte > 2^31.

Oder hast Du einen Fehler in meinem MPArith-Paket gefunden?

Gammatester

[tuxianer]

hallo,
ich habe dein Paket noch nicht probiert. Wie füge ich es in meine Funktion ein? Und wie große Zahlen kann ich dann verwenden?

Viele Grüße tuxianer

[spaxxn]

Auch wenns reelle Zahlen sind, könntest du es mit Extended versuchen.

[himitsu]

Komisch, jetzt getestet kommt auch 11771, aber letztens war es irgendwas Anderes :gruebel:

Was die größeren Zahlen angeht, dann mißt du wohl entweder Extendet verwenden, allerdings kann man da nur die ersten 18-19 Stellen betrachten, da die Auflösung nicht anderes zuläßt.

Bei 'ner 30-stelligen Zahl wären also durchschnittlich die letzten 11 Stellen fehlerhaft.



Ansonsten hätte ich fast meine eigene BigInt-Imlementation fertig (BigFloat und 'nen dynamisches BigFloat kommen auch irgendwann) ... rechnen geht schon, aber den einen Sonderfall von Low(TBigInt) / MinBigInt muß ich noch prüfen und mit der Überlaufpüfung hab ich noch Probleme ;(


mit 'nem 512 bit-Integer wäre ein Bereich von -2^511 bis 2^511 - 1 stellengenau abgedeckt.
von*-6.703.903.964.971.298.549.787.012.499.102.923.063. 739.682.910.296.196.688.861.780.721.860.882.015.03 6.773.488.400.937.149.083.451.713.845.015.929.093. 243.025.426.876.941.405.973.284.973.216.824.503.04 2.048
bis*+6.703.903.964.971.298.549.787.012.499.102.923 .063.739.682.910.296.196.688.861.780.721.860.882.0 15.036.773.488.400.937.149.083.451.713.845.015.929 .093.243.025.426.876.941.405.973.284.973.216.824.5 03.042.047
+/- 6.703e153
+/- 6.703 * 10^153

[tuxianer]

na ich bräuchte ja nur integer. hast du nen link zu deinem projekt?

[gammatester]

Zitat:

Zitat von tuxianer

na ich bräuchte ja nur integer. hast du nen link zu deinem projekt?

Hier Delphi-Code der fast 64 Bits verarbeitet. Nicht sehr schnell da MulMod bitweise berechnet wird. Aber immer noch schneller als Multipräzision.

Delphi-Quellcode:

{MulMod and ExpMod functions,  (C) W.Ehrhardt 2008}

{---------------------------------------------------------------------------}
function mulmod63(x,y,n: uint64): uint64;
  {-returns x*y mod n, binary mul-mod from Crandall/Pomerance Alg. 9.3.1}
  { Range restriction due to uint64: 0<n<2^63}
var
  m,s: uint64;
begin
  assert(n and (uint64(1) shl 63) = 0);
  assert(n > 0);
  if x>=n then x := x mod n;
  if y>=n then y := y mod n;
  if (x=0) or (y=0) then begin
    mulmod63 := 0;
    exit;
  end;
  m := int64(1) shl 62;
  while m and x = 0 do m := m shr 1;
  s := 0;
  while m<>0 do begin
    s := s+s;
    if s>=n then dec(s,n);
    if x and m <> 0 then begin
      inc(s,y);
      if s>=n then dec(s,n);
    end;
    m := m shr 1;
  end;
  mulmod63 := s;
end;


{---------------------------------------------------------------------------}
function expmod63(a,b,n: uint64): uint64;
  {-returns a^b mod n, uses right-left form binary ladder}
  { Range restriction due to uint64: 0<n<2^63}
var

  c: uint64;
begin
  assert(n and (uint64(1) shl 63) = 0);
  assert(n > 0);
  c := 1;
  while b>0 do begin
    if odd(b) then c := mulmod63(a,c,n);
    a := mulmod63(a,a,n);
    b := b shr 1;
  end;
  expmod63 := c;
end;



{---------------------------------------------------------------------------}
function mulmod62(x,y,n: int64): int64;
  {-returns x*y mod n, binary mul-mod from Crandall/Pomerance Alg. 9.3.1}
  { Range restriction due to int64: 0<n<2^62, x>=0, y>=0}
var
  m,s: int64;
begin
  assert(n and (int64(3) shl 62) = 0);
  assert(n >  0);
  assert(x >= 0);
  assert(y >= 0);
  if x>=n then x := x mod n;
  if y>=n then y := y mod n;
  if (x=0) or (y=0) then begin
    mulmod62 := 0;
    exit;
  end;
  m := int64(1) shl 62;
  while m and x = 0 do m := m shr 1;
  s := 0;
  while m<>0 do begin
    s := s+s;
    if s>=n then dec(s,n);
    if x and m <> 0 then begin
      inc(s,y);
      if s>=n then dec(s,n);
    end;
    m := m shr 1;
  end;
  mulmod62 := s;
end;


{---------------------------------------------------------------------------}
function expmod62(a,b,n: int64): int64;
  {-returns a^b mod n, uses right-left form binary ladder}
  { Range restriction due to int64: 0<n<2^62, a>=0, b>=0}
var
  c: int64;
begin
  assert(n and (int64(3) shl 62) = 0);
  assert(n >  0);
  assert(a >= 0);
  assert(b >= 0);
  c := 1;
  while b>0 do begin
    if odd(b) then c := mulmod62(a,c,n);
    a := mulmod62(a,a,n);
    b := b shr 1;
  end;
  expmod62 := c;
end;

Jenach Delphi Version kann int64 bzw uint64 benutzt werden. Die Bereiche sind dann 0 bis 2^62-1 bzw 0 bis 2^63-1.


Gruß Gammatester

[himitsu]

also Integer geht bei direkter Rechnung nicht ;(

666^4 sprenkt schonmal die Integergrenzen und auch 512 Bit werden gesprengt

falls ich mich jetzt nicht verschätzt hab, dann komm ich auf etwa 10.0000.000 Bits für 666^58613 :gruebel:

vielleicht sollte ich mir doch noch überlegen auch noch 'en dynamischen BigInteger zu erstellen (wenn ich diesen soweit fertig hab :stupid: ), denn so geht es nicht ;(

Delphi-Quellcode:

I := IntPower(666, 58613) mod 81079;

aber über die mod_exp-Funktion geht's :-D

Delphi-Quellcode:

Function mod_exp(Basis, Exponent, Modulo: TBigInt): TBigInt;
  Begin
    Result := 1;
    While Exponent > 0 do Begin
      If Exponent.Data and $1 <> 0 Then
        Result := (Result * Basis) mod Modulo;
      Basis := (Basis * Basis) mod Modulo;
      Exponent := Exponent div 2;
    End;
  End;

oder falls es wem so gefällt

Delphi-Quellcode:

Function mod_exp(Basis, Exponent, Modulo: TBigInt): TBigInt;
  Begin
    Result := 1;
    If not Exponent.isNegative Then
      While not Exponent.isZero do Begin
        If Exponent.Data[0] and $1 <> 0 Then Begin
          Result.Multiply(Basis);
          Result.Modulus(Modulo);
        End;
        Basis.Multiply(Basis);
        Basis.Modulus(Modulo);
        Exponent.bShR(1);
      End;
  End;

Delphi-Quellcode:

Var i: TBigInt;

I := mod_exp(666, 58613, 81079);
S := I.asString;

also meine TBigInt bekommt auch 11771 raus und nicht

Zitat:

Zitat von tuxianer

Bei Größeren Zahlen kommt aber mist raus z.B.

666^58613 mod 81079=-38808

Rauskommen müsste aber: 49371.

so, jetzt muß ich nur noch etwas aufräumen und mir enlich mal 'nen Namen für mein Projekt einfallen lassen :cry:
(UCC paßt nicht mehr, da es einen kompletten Neuanfang darstellt und es sich nicht mehr hauptsächlich um Unicode-Funktionen handelt)

'nen Teil des Projekts hatte ich da mal gepostet
http://www.delphipraxis.net/internal...=879295#879295
nur TBigInt fehlt dort noch, da ich hiermit erst letzte Woche begonnen hab.
(OK, die Grundidee hatte ich schonmal im UCC versucht umzusetzen)

Ach ja, an die Rechenleistung wie vom DECMath werd ich nie rankommen, aber das hab ich auch nich ernsthaft vor ... aber zumindestens 'ne leicht zu nutzend Bibo sollte schon rauskommen :stupid:

ich beeil mich auch ... versuch bis Ende der Woche was Neues hochzuladen :angel:

[JasonDX]

Das ganze sollte auch ohne BigInt funktionieren, zumindest mit 32bit-ints als Input:

Delphi-Quellcode:

function exp_mod(x, n, m: integer): integer;
var
  i: integer;
  p, r: int64;
begin
  i := 1;
  r := 1;
  p := x;
  while (i > 0) and (i < n) do
  begin
    if (i and n > 0) then
      r := (r * p) mod m;
    p := (p * p) mod m;
    i := i shl 1;
  end;
  result := r;
end;

ok, fragt nich mich, was ich grad gedacht hab, iwie hab ich das Problem der Frage verfehlt :duck:

greetz
Mike

[tuxianer]

kannst du bitte mal die Datei uploaden, die ich für den bigint einbinden muss? und wie mach ich das sowas habe ich noch nie gemacht mit delphi. Danke schonmal!

[gammatester]

Zitat:

Zitat von tuxianer

kannst du bitte mal die Datei uploaden, die ich für den bigint einbinden muss? und wie mach ich das sowas habe ich noch nie gemacht mit delphi. Danke schonmal!

Kannst Du vielleicht noch verraten, wenn von 3 potentiellen du Du meinst, und welche Datei?

Gruß Gammatester

[tuxianer]

sorry ich meine himitsu und mir geht es um den bigint

[himitsu]

TBigInt

TBigInt ... Platz 1 ... sollte mir das was su denken geben?

[tuxianer]

also ich habe mir jetzt non vlc heruntergeladen. wiemuss ich jetzt weiter vorgehen? ich möchte nur die fmath verwenden. Ich habe jetzt alles dateien in meinen projektordner kopiert aber wenn ich unter uses fmath hinschreibe kommen fehlermeldungen.

[himitsu]

ist halt Teil eines Projektes. :stupid:

aber ich versuch mal die den BigInt-Teil zu vereinzeln.
mir raucht eh grad de Kopf von dessen großer Schwester (oder Bruder?) ... nja, etas abwechslung tut bestimmt Gut :angel:



[add]
was für Fehlermeldungen kommen eigentlich?
(außer daß Delphi meckern sollte, das etwas ('ne menge Units) fehlt)

und welche Delphiversion nutzt du?

[vsilverlord]

Das finde ich toll, vllt erinnert ihr euch noch an mein Problem. Ich hatte ein ähnliches Problem bei dem ich sehr große Zahlen gebraucht habe. Corpsman hat mir ja BigInt empfohlen bei dem leider keine Divison funktioniert hat und selber war ich nicht instande das zu programmieren. Wenn das mit den großen Zahlen funktionieren würde wäre ich darüber sehr erfreut. Wieviel Stellen unterstützt das neue Format? Und kann ich die Unit einfach einbinden und später + und - benutzen?

[tuxianer]

ich fänds auch echt nett von dir, da ich es für eine Projekt (RSA) benötige. Im Moment kann ich leider nur primzahlen bis ca. 200 erzeugen und mit diesen Arbeiten alles andere kann zu groß werden. Also danke schonmal :cheers:!

[himitsu]

http://www.delphipraxis.net/internal...=895756#895756

512 Bit im Zweierkomplement = 152(153) Dezimalstellen
Int64 = 18(19) Dezimalstellen

und man kann, dank der neuen Kompilerfeatures, einfach sowas wie + und - Verwenden (siehe Testprojekt)

< <= = <> >= >
+ - div mod
and or xor not shl shr
Inc Dec

und als Funktionen in der Klasse und einiges nochmals als Einzelfunktion in der Unit (nach der Klassendefinition) unter anderem dieses:
DivMod Power LdExp LtExp LxExp ExpMod Log2 Log10 LogN Radic Sqr Sqrt Fibonacci RoundTo RoL RoR

[tuxianer]

Vielen Dank erstmal. :bounce1: Seh ich das richtig das ich jetzt einfach bei uses schreiben muss ....., BigInt in meinen bisgherigen sources? und die datie halt in den gleichen ordner packen...

[himitsu]

Jupp, die Datei einfach in den Projektordner, oder einen anderen Ordner, welcher in den Suchpfaden drin steht.

dann BigInt in Uses eintragen

und TBigInt verwenden.


und zur Verwendung:
die "Standardfunktionalität ist genauso wie bei auch "normalen" Integern

z.B. kann man TBigInt auch ganr normal speichern und laden:

Delphi-Quellcode:

Var BI: TBigInt;
  F: File...;
  S: TStream;
  P: Pointer;

BlockWrite(f, BI, SizeOf(BI));
S.Write(BI, SizeOf(BI));
MoveMemory(P, @BI, SizeOf(BI));

[MSSSSM]

schau dir das mal an:


http://www.lang-ib.de/Delphi-Ecke/Tr...s/vli/vli.html

[gammatester]

Zitat:

Zitat von MSSSSM

schau dir das mal an:


http://www.lang-ib.de/Delphi-Ecke/Tr...s/vli/vli.html

Das ist natürlich gerade für RSA völlig ungeeignet, da die wichtigste Routine, um die es in diesem Thread ja geht, nämlich eine ExpMod gänzlich fehlt.

Gruß Gammatester

[himitsu]

Zitat:

Zitat von gammatester

Das ist natürlich gerade für RSA völlig ungeeignet, da die wichtigste Routine, um die es in diesem Thread ja geht, nämlich eine ExpMod gänzlich fehlt.

na gut, dieses könnte man sich da notfalls noch nachrüsten.

erstmal eine Modfunktion erstellen

vom Prinzip her so:

Delphi-Quellcode:

Function Mod....
  Begin
    Result{Modulo} := Dividend - ((Dividend div Divisor) * Divisor)
  End;

für TVLI etwa so :gruebel:

Delphi-Quellcode:

Procedure TVLI.Mod(Dividend, Divisor: TVLI);
  Var Temp: TVLI;

  Begin
    Temp := TVLI.Create;
    Temp.Assign(Dividend);
    Temp.Divide(Divisor);
    Temp.Multiply(Divisor);
    Assign(Dividend);
    Substract(Temp);
    Temp.Free;
  End;

und nun muß man sich nur noch eine der hier schon vorgeschlagenen ExpMod-Funktionen für TVLI zurechtbiegen.
(also eine ohne Binäroperationen, wie AND und Co.)

[tuxianer]

mal ne andere Frage mit delphi 2005 geht der bigint nicht oder? da müsst ich das nämlich mal am anderen pc probieren.