Exponentieren und dann Modulo: große Zahlen

[gammatester]

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