1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

//Es werden die Zahlen x, n und p übergeben, berechnet wird 
//(x hoch n) modulo p 
function FastExpMod(x, n, p: Int64): Int64; 
var 
  z: Int64; 
begin 
  if (n = 0) then 
  begin 
    Result := 1; 
    exit; 
  end; 
  if Odd(n) then 
    result := (x * FastExpMod(x, n - 1, p)) mod p 
  else 
  begin 
    z := FastExpMod(x, n div 2, p); 
    result := (z * z) mod p; 
  end; 
end; 

procedure TForm1.Button1Click(Sender: TObject); 
begin 
  ShowMessage(IntToStr(FastExpMod(5, 4, 11))); 
end;					

1:
2:
3:
4:
5:
6:
7:

function calculate(k,c,n:int64):int64;  // (k^c) mod n 
begin 
  if c<1 then result := 1 else 
  begin 
    result := k*calculate(k,c-1,n) mod n; 
  end; 
end;					

1:

ShowMessage(IntToStr(FastExpMod(65, 432323453434355732, 1112989782323131)));					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure TClientFrm.Button1Click(Sender: TObject);
var help,c,d,n:int64;
begin
  c:=7;
  d:=74368806461143;
  n:=104116349456429;
  help:=FastExpMod(65, c, n);
  ShowMessage(IntToStr(help));
  ShowMessage(Inttostr(FastExpMod(help,d,n)));
end;					

1:

g:=(c^d) mod n;					

1:

g:=c &^ d mod n;					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:

{ Find the GCD using Euclid's algorithm                                        }
function GCD(const N1, N2: Int64): Int64;
var X, Y, J : Int64;
begin
  X := N1;
  Y := N2;
  if X < Y then
    Swap(X, Y);
  While (X <> 1) and (X <> 0) and (Y <> 1) and (Y <> 0) do
    begin
      J := (X - Y) mod Y;
      if J = 0 then
        begin
          Result := Abs(Y);
          exit;
        end;
      X := Y;
      Y := J;
    end;
  Result := 1;
end;

{ Find the modular inverse of A modulo N using Euclid's algorithm.             }
function InvMod(const A, N: Int64): Int64;
var g0, g1, v0, v1, y, z : Int64;
begin
  if N < 2 then
    raise EInvalidArgument.CreateFmt ('InvMod: n=%d < 2', [N]);
  if GCD(A, N) <> 1 then
    raise EInvalidArgument.CreateFmt ('InvMod: GCD(a=%d, n=%d) <> 1', [A, N]);
  g0 := N;  g1 := A;
  v0 := 0;  v1 := 1;
  while g1 <> 0 do
    begin
      y := g0 div g1;
      z := g1;
      g1 := g0 - y * g1;
      g0 := z;
      z := v1;
      v1 := v0 - y * v1;
      v0 := z;
    end;
  if v0 > 0 then
    Result := v0 else
    Result := v0 + N;
end;

{ Calculates x = a^z mod n                                                     }
function ExpMod(A, Z: Int64; const N: Int64): Int64;
var Signed : Boolean;
begin
  Signed := Z < 0;
  if Signed then
    Z := -Z;
  Result := 1;
  while Z <> 0 do
    begin
      while not Odd(Z) do
        begin
          Z := Z shr 1;
          A := (A * Int64(A)) mod N;
        end;
      Dec (Z);
      Result := (Result * Int64(A)) mod N;
    end;
  if Signed then
    Result := InvMod(Result, N);
end;					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

function ModExp(a,b,n : Int64) : Int64;
var d,t: Int64;
    i: Integer;
begin
  if (b = 0) then
  begin
    Result := 1 mod n;
  end else
  if (b < 0) then
  begin
    Result := (-1);
  end else
  begin
    d := 1;
    { Um a potenziert mit b modulo n zu berechnen, sind nicht b
      Multiplikationen von m mit sich selbst erforderlich.
      Tatsächlich genügen weniger als 2 log(b) Multiplikationen.
      Ausgehend von der Beobachtung, dass z.B. a hoch 8 durch
      3-maliges Quadrieren von a zu berechnen ist, wird die
      Binärdarstellung für b für den folgenden Algorithmus
      zugrundegelegt.
    }
    i := Trunc(logn(2, b));
    while (i >= 0) do
    begin
      d := (d*d) mod n;
      t := Trunc(Power(2,i));
      if ((b and t) <> 0) then d := (d*a) mod n;
      i := i - 1;
    end;
    Result := d;
  end;
end;					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

define modexp(a, x, n) { # return a ^ x mod n
  auto r
  
  r = 1
  while ( x > 0 ) {
    if ( (x % 2) == 1 ) {
      r = (r * a) % n
    }
    
    a = ( a * a ) % n
    x /= 2
  }
  return(r)
}					

1:
2:
3:

if ((b and t) <>0) then...
Z:=Z shr 1;
while not Odd(Z) do...					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:

//Es werden die Zahlen x, n und p übergeben, berechnet wird
//(x ^ n) modulo p
function TForm1.FastExpMod(x, n, p: Int64): Int64;
var
  z: Int64;
begin
  if (n = 0) then
  begin
    Result := 1;
    exit;
  end;
  if odd(n) then
    result := FastMultMod(x,FastExpMod(x, n - 1, p),p)
  else
  begin
    z := FastExpMod(x, n div 2, p);
    result := FastMultMod(z,z,p);
  end;

end;

//Es werden die Zahlen x, n und p übergeben, berechnet wird
//(x * n) modulo p
function TForm1.FastMultMod(x, n, p: Int64): Int64;
var
  z: Int64;
begin
  if (n = 1) then
  begin
    Result := x;
    exit;
  end;
  if odd(n) then
    result:=(x + FastMultMod(x, n - 1, p)) mod p
  else
  begin
    z := FastMultMod(x, n div 2, p);
    result := (z + z) mod p;
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  c:=5;
  d:=7270789624973;
  n:=36353963780549;
  // hab n spinedit zum bequemen testen eingebaut...
  help:=FastExpMod(spinedit1.value, c, n);
  ShowMessage(IntToStr(help));
  ShowMessage(Inttostr(FastExpMod(help,d,n)));
end;					

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

type   TRSAString=array [1..256] of int64;

...

function TRSA.decode(text:TRSAString;priv_key,n:int64):TRSAString;
var i:integer;
begin
  i:=0;
  ClearRSAString(result);  // löscht Inhalt von "result"
  while (i<length(text)) do
  begin
    inc(i);
    result[i]:=FastExpMod(ord(text[i]),priv_key,n);
  end;
end;					

1:

 while (i<length(text)-1)					

1:

result := FastMultMod(x,0,p)					

1:
2:
3:
4:
5:

  if (n=0) OR (x=0) then
  begin
    Result := 0;
    exit;
  end;