Delphi, RSA i duze liczby.

Potrzebuje uzyc szyfru RSA w mojej aplikacji, jednak nie moge znalezc nigdzie jakiegos wspanialego unitu, ktory pozwolil by mi operowac na dosc duzych liczbach. Co prawda stwoezylem pewien 'system' pozwalajacy liczyc na naprawde duzych liczbach, polegajacy na dzialaniach 'pisemnych', jednak jest on daleko za wolny :( I tu mam pytanko: czy ktos z Was ma moze jakis unit/biblioteke umozliwiajaca obliczenia na duzych liczbach (a najlepiej implementacje RSA w delphi/Dll :))?

Zajrzyj tutaj może znajdziesz coś odpowiedniego dla siebie. Chociaż głowy nie daję sobie uciąć ;)

Szukaj na 4p modułu vlong

// nota bene napisałem ten moduł właśnie po to, żeby rsa zaimplementować - Ł

Dzieki wam.
A wie ktos moze jak sprawdzic czy dwie liczby sa wzglednie pierwsze? Probowalem rozlozyc je na dzielniki, ale to za dlugo trwa :(

ali88 napisał(a)

A wie ktos moze jak sprawdzic czy dwie liczby sa wzglednie pierwsze? Probowalem rozlozyc je na dzielniki, ale to za dlugo trwa :(

I o to chodzi w RSA, że rozkład dużych liczb pierwszych troche długo trwa ;P.

dwie liczby są względnie pierwsze, m.in. jeśli są pierwsze. do sprawdzania czy liczba jest pierwsza służą dwa algorytmy probabilistyczne, jeden sprawdza z p-wem 50%, drugi z 75%, poczytaj sobie o nich w jakiejś książce.

[dopisane]
a zresztą - tu masz implementację sprawdzania, czy liczba jest pierwsza z prawdopodobieństwem 50%

function check(const n : verylongint) : boolean;
var
  K,v,X,u : verylongint;
  j       : integer;
begin
  for j := bits-1 downto 1 do if bitset(n,j) then break;
  repeat
    vrand(j,K);  {K < N}
  until vcomp(n,k) = 1;     {K losowe takie, ľe K < n}

  vshr(n,1,v);              {v = n/2}
  vmodexp(K,v,N,X);         {x = K^v mod n}


  longtovlong(1,v);         {v=1}
  vsub(n,v,u);              {u = n-1}

check := (vcomp(x,v) = 0) or (vcomp(x,u) = 0); {x=v lub x=u - pierwsza}

end;

Dodam jeszcze: http://4programmers.net/article.php?id=199#test_rabina