Exponentieren und dann Modulo: große Zahlen

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