Modulus überlastet

[X_ster]

Hey,
ich hab das problem, dass die funktion

Code: Alles auswählen

function m (n :int64) :int64;
var
r,q,p: int64;
 
begin
 q := 2;
 p := (q**(n-1));
 r:= p mod n;
 Result := r;
end;

mit höheren zahlen überlastet wird. leider unterstützt mod kein real, single oder double.
Gibt es da auch eineandere Lösung??

[carli]

Die unit "gmp".
Die genaue Dokumentation gibts unter google mit dem Stichwort "gnu gmp mpz"

[Euklid]

Alternativ kannst Du große Zahlen auch hiermit berechnen: http://forge.lazarusforum.de/wiki/gnurz" onclick="window.open(this.href);return false;

Zur Einarbeitung reicht das Wiki.

[indianer-frank]

Vielleicht sollte erst einmal geklärt werden,was das ganze überhaupt soll. Auf jeden Fall ist hier kein "Modulus überlastet". Wenn ich mal annehme, daß ** eine Potenz bedeutet, soll hier 2^(n-1) mod n betrechnet werden (für RSA, Miller-Rabin?). Für n prim kommt immer 1 raus (kleiner fermatsche Satz). Ansonsten kommt man für normale Größenordnungen ohne Langzahlen aus, wenn man weiß, was mod für Eigenschaften hat. Man berechnet natürlich nicht zuerst 2^(n-1) aus, sondern rechnet mit (x*y) mod n = (x mod n)*(y mod). Das Stichwort ist binäre modulare Exponentiation.

Code: Alles auswählen

function m(n: int64): int64;
var
  q,r,n1: int64;
begin
  r := 1;
  q := 2;
  n1 := n-1;
  while n1>0 do begin
    if odd(n1) then r := r*q mod n;
    n1 := n1 shr 1;
    q  := sqr(q) mod n;
  end;
  m := r;
end;

Beispiele: m(16380) = 2048; m(16381) = 1;

PS: Das kleinste nichtprime n für das m(n) keine Zweierpotenz oder 0 ergibt, ist n=18 mit m(18)=14.