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: