проверка на простоту, RSA

у меня выводятся такие ошибки, работаю в delphi, можете объснить, что они значат?[img][/img][Вы должны быть зарегистрированы и подключены, чтобы видеть это изображение]

Первая ошибка - это, очевидно, деление на ноль.
Вторая - выход за границы, например, массива или другой структуры данных, или попытка обратиться к несуществующей ячейке.

Можно кого-нибудь попросить посмотреть мою програмку, если вы не заняты?
мне ее завтра сдавать, осталось немного доработать...

Кидай сюда и все) Только желательно в теге code, чтоб читабельно было)

Код:


unit test;

interface
  Uses SysUtils, Math;

  const
  MaxLen = 100;
  BASE = 10;
  BASE_DIG = 1;

type
  TLong = record
    Length: Longint;
    Coef: Array[0..MaxLen] of longint;
  end;
//--------------------------------------------------------
              //Äëèííàÿ àðèôìåòèêà
//--------------------------------------------------------

  procedure Zero(var A: TLong);
  function  Add(const A, B: TLong): TLong;
  function  Minus(x:TLong;y:TLong):TLong;
  function  Mul(const A: TLong; const B: Longint): TLong;
  function  Mul_(const A, B: TLong): TLong;
  procedure Divide(const A: TLong; const B: Longint; var Q: TLong; var R: longint);
  procedure Divide_(A, B: TLong; var Q, R: TLong);
  function  Convert(S: String): TLong;
  procedure Print(A: TLong);
  function  power(t:longint; k: TLong): TLong;
  function  Check(const A,B:TLong):boolean;
  function  All(x:TLong;y:TLong):boolean;
  procedure Swap(Var x,y:TLong);
  procedure Rand(b:longint;var k:TLong);
  function  All_(x:TLong;y:TLong):boolean;
  function  modpow(a,b,n:TLong):TLong;
//--------------------------------------------------------
              //Ïðîâåðêà íà ïðîñòîòó p è q
//--------------------------------------------------------

  function  s_(n:TLong):TLong; //Íàéòè s è t, óäîâëåòâîðÿþùèå óðàâíåíèþ N-1=2^s * t
  function  t_(n:TLong):TLong; //Íàéòè s è t, óäîâëåòâîðÿþùèå óðàâíåíèþ N-1=2^s * t
  function  a_(n:TLong):TLong; //Ñëó÷àéíûì îáðàçîì âûáðàòü a, 1 < a < N
  function  n_a(n,a:TLong):boolean;//åñëè true, òî n ñîñòàâíîå
  function  next1(n,a:TLong):boolean;//a^t=1(mod N) åñëè true, òî ïóíêò 2
  function  next2(n,a:TLong):boolean;//a^(2^k*t)=-1(mod N)åñëè true, òî ïóíêò 2
  function  prost(var n:TLong):boolean;
//--------------------------------------------------------
              //RSA
//--------------------------------------------------------
  function euclid(a, b:TLong):TLong;
  function d_(p,q:TLong):TLong;

implementation
//--------------------------------------------------------
              //Äëèííàÿ àðèôìåòèêà
//--------------------------------------------------------

//î÷èñòèòü ÷èñëî TLong
procedure Zero(var A: TLong);
begin
  FillChar(A.Coef, SizeOf(A.Coef), 0);
  A.Length := 1;
end;

//A + B
function Add(const A, B: TLong): TLong;
var
  C: TLong;
  I: longint;
begin
  if A.Length < B.Length then
  begin
    Add := Add(B, A);
    Exit;
  end;
  Zero(C);
  for I := 0 to A.Length - 1 do
    C.Coef[I] := A.Coef[I] + B.Coef[I];
  for I := 0 to A.Length - 1 do
  begin
    Inc(C.Coef[I + 1], C.Coef[I] div BASE);
    C.Coef[I] := C.Coef[I] mod BASE;
  end;
  C.Length := A.Length;
  if C.Coef[A.Length] <> 0 then Inc(C.Length);
  Add := C;
end;

function  Minus(x:TLong;y:TLong):TLong;
Var i, t: longint;
    c: TLong;
Begin
  i:=0;
  fillchar(c, sizeof(c), 0);
  if y.length > x.length then Swap(x,y);
  if x.length=y.length then
  begin
    while (x.coef[x.length-1]>=y.coef[y.length-1]) and (i<>y.length) do
      i:=i+1;
    if i<> y.length then
      Swap(x,y);
  end;
  For i:=1 to x.length do
  begin
    t:=x.coef[i]-y.coef[i];  //ðàçíîñòü â ýòîì ðàçðÿäå
    if t < 0 then
    begin
      dec(x.coef[i+1]);  //çàíèìàåì åäèíèöó
      t:=t+10;      //äîáàâëÿåì 10 ê ðàçíîñòè
    end;
    c.coef[i]:=t;
  end;
  c.length:=x.length;
  while(c.coef[c.length]=0) and (c.length > 1) do //èçáàâëÿåìñÿ îò íóëåé
    c.length:=c.length-1;
  minus:=c;
end;

Procedure Swap(Var x,y:TLong);    //ìåíÿåì ìåñòàìè
var t:TLong;
    j, M:longint;
begin
  M:=Max(x.length,y.length);
  if x.length < M then
    for j:=x.length+1 to M do
      x.coef[j]:=0;
  if y.length < M then
    for j:=y.length+1 to M do
      y.coef[j]:=0;
  for j:=0 to M do
  begin
    t.coef[j]:=x.coef[j];
    x.coef[j]:=y.coef[j];
    y.coef[j]:=t.coef[j];
  end;
end;

//ïðîèçâåäåíèå äëèííîãî íà êîðîòêîå
function Mul(const A: TLong; const B: Longint): TLong;
overload;
var
  C: TLong;
  I: longint;
begin
  Zero(C);
  for I := 0 to A.Length - 1 do
    C.Coef[I] := A.Coef[I] * B;
  for I := 0 to A.Length - 1 do
  begin
    Inc(C.Coef[I + 1], C.Coef[I] div BASE);
    C.Coef[I] := C.Coef[I] mod BASE;
  end;
  C.Length := A.Length;
  if C.Coef[A.Length] <> 0 then Inc(C.Length);
  Mul := C;
end;

//ïðîèçâåäåíèå äâóõ äëèííûõ
function Mul_(const A, B: TLong): TLong;
overload;
var
  C: TLong;
  I, J: longint;
  temp, carry: longint;
begin
  Zero(C);
  for I := 0 to A.Length - 1 do
  begin
    carry := 0;
    for J := 0 to B.Length - 1 do
    begin
      temp := A.Coef[I] * B.Coef[J] + C.Coef[I + J] + carry;
      carry := temp div BASE;
      C.Coef[I + J] := temp - carry * BASE;
    end;
    C.Coef[I + B.Length] := carry;
  end;
  I := A.Length + B.Length - 1;
  while (I > 0) and (C.Coef[I] = 0) do
    Dec(I);
  C.Length := I + 1;
  Mul_ := C;
end;

//äåëåíèå äëèííîãî íà êîðîòêîå, Q -- ÷àñòíîå, R -- îñòàòîê
procedure Divide(const A: TLong; const B: Longint; var Q: TLong; var R: longint);
overload;
var
  I: longint;
  temp: Longint;
begin
  Zero(Q);
  R := 0;
  for I := A.Length - 1 downto 0 do
  begin
    temp := R * BASE + A.Coef[I];
    Q.Coef[I] := temp div B;
    R := temp - Q.Coef[I] * B
  end;
  I := A.Length - 1;
  while (I > 0) and (Q.Coef[I] = 0) do
    Dec(I);
  Q.Length := I + 1;
end;

//äåëåíèå äâóõ äëèííûõ
procedure Divide_(A, B: TLong; var Q, R: TLong);
overload;
var
  N, M, I, J, K, junk: Longint;
  temp1, temp2, temp: Longint;
  scale, //êîýôôèöèåíò íîðìàëèçàöèè
  Guess, _r, //ïðåäïîëîæèòåëüíîå ÷àñòíîå è îñòàòîê
  borrow, carry: longint;  //ïåðåíîñû
begin
  //åñëè äåëèòåëü áîëüøå äåëèìîãî
  if A.Length < B.Length then
  begin
    Zero(Q);
    R := A;
    Exit;
  end;
  //äåëèòåëü áàçîâîãî òèïà
  if B.Length = 1 then
  begin
    Divide(A, B.Coef[0], Q, R.Coef[0]);
    R.Length := 1;
    Exit;
  end;
  Zero(Q);
  Zero(R);
  Inc(A.Length);
  A.Coef[A.Length] := 0;
  N := B.Length;
  M := A.Length - B.Length;
  scale := BASE div (B.Coef[N - 1] + 1);
  if scale > 1 then //íîðìàëèçàöèÿ
  begin
    A := Mul(A, scale);
    B := Mul(B, scale);
  end;
  I := M;
  J := N + I;
  while I > 0 do
  begin
    Dec(I);
    Dec(J);
    Guess := (A.Coef[J] * BASE + A.Coef[J - 1]) div B.Coef[N - 1];
    _r := (A.Coef[J] * BASE + A.Coef[J - 1]) mod B.Coef[N - 1];
    while _r < BASE do
    begin
      temp2 := B.Coef[N - 2] * Guess;
      temp1 := _r * BASE + A.Coef[J - 2];
      if (temp2 > temp1) or (Guess = BASE) then
      begin
        Dec(Guess);
        Inc(_r, B.Coef[N - 1]);
      end
      else Break;
    end;
    carry := 0;
    borrow := 0;
    for K := 0 to N - 1 do
    begin
      temp1 := B.Coef[K] * Guess + carry;
      carry := temp1 div BASE;
      Dec(temp1, carry * BASE);
      temp2 := A.Coef[K + I] - temp1 + borrow;
      if temp2 < 0 then
      begin
        A.Coef[K + I] := temp2 + BASE;
        borrow := -1;
      end
      else
      begin
        A.Coef[K + I] := temp2;
        borrow := 0;
      end;
    end;
    temp2 := A.Coef[N + I] - carry + borrow;
    if temp2 < 0 then
    begin
      A.Coef[N + I] := temp2 + BASE;
      borrow := -1;
    end
    else
    begin
      A.Coef[N + I] := temp2;
      borrow := 0;
    end;
    if borrow = 0 then
      Q.Coef[I] := Guess
    else
    begin
      Q.Coef[I] := Guess - 1;
      carry := 0;
      for K := 0 to N - 1 do
      begin
        temp := A.Coef[K + I] + B.Coef[K] + carry;
        if temp >= BASE then
        begin
          A.Coef[K + I] := temp - BASE;
          carry := 1;
        end
        else
        begin
          A.Coef[K + I] := temp;
          carry := 0;
        end;
      end;
      A.Coef[N + I] := A.Coef[N + I] + carry - BASE;
    end;
    K := A.Length - 1;
    while (K > 0) and (A.Coef[K] = 0) do
      Dec(K);
    A.Length := K + 1;
  end;
  while (M > 0) and (Q.Coef[M] = 0) do
    Dec(M);
  Q.Length := M + 1;
  if scale > 1 then
  begin
    Divide(B, scale, B, junk);
    Divide(A, scale, R, junk);
  end
  else R := A;
end;

//ñòðîêó â TLong
function Convert(S: String): TLong;
var
  I, K, d: longint;
  _S: String;
  C: TLong;
begin
  Zero(C);
  d := Length(S);
  while d mod BASE_DIG <> 0 do  //äîáàâèëè íóëè ñëåâà
  begin
    S := '0' + S;
    Inc(d);
  end;
  K := 0;
  _S := '';
  for I := d downto 1 do
  begin
    _S := Concat(S[I], _S);
    if (I - 1) mod BASE_DIG = 0 then
    begin
      C.Coef[K] := StrToInt(_S);
      Inc(K);
      _S := '';
    end;
  end;
  C.Length := K;
  Convert := C;
end;

Procedure print(a:TLong); //âûâîä ÷èñëà
Var i: longint;
    s: string;
Begin
  For i:=a.length-1 downto 0 do
    Begin
      s:=inttostr(a.coef[i]);
      Write(s);
    End;
  WriteLn;
End;

function power(t:longint; k: TLong): TLong; {âîçâåäåíèå ÷èñëà t â ñòåïåíü k}
var
  res,q:TLong;
  r:longint;
begin
  if all(k,convert('0')) then
  begin
    power:=convert('1');
    exit;
  end;
  res := convert('1');
  while all_(convert('0'),k) do
  begin
    if not check(k,convert('2')) then
      res := mul_(res,convert('t'));
    t:= sqr(t);
    divide(k,2,q,r);
    k := q;
  end;
  power := res;
end;

//ïðîâåðêà êðàòíîñòè äâóõ ÷èñëå
function  check(const A,B:TLong):boolean;
var Q,R:TLong;
begin
  divide_(A,B,Q,R);
  if all(R,convert('0')) then
    check:=TRUE
    else check:=FALSE;
end;

//TRUE êîãäà ñîâïàäàþò
function  all(x:TLong;y:TLong):boolean;
var i:longint;
begin
  if x.length<>y.length then
    All:=FALSE
      else
      for i:=0 to x.length-1 do
        if x.coef[i]=y.coef[i] then
          All:=TRUE
          else
            begin
              All:=FALSE;
              exit;
            end;
end;

//ðàíäîì îãðàíè÷åííûé äëèíîé b
procedure Rand(b:longint;var k:TLong);
var f:longint;
begin
  zero(k);
  randomize;
  k.Length:=random(b)+1;
  k.Coef[k.Length-1]:=random(9)+1;
  for f:=k.length-2 downto 0 do
    k.coef[f]:=random(10);
end;

function  All_(x:TLong;y:TLong):boolean; //TRUE åñëè õ < y
var i:longint;
begin
  if x.length<y.length then
    begin
      All_:=TRUE;
      exit;
    end;
  if x.length>y.length then
    begin
      All_:=FALSE;
      exit;
    end;
 if not all(x,y) then
  for i:=x.length-1 downto 0 do
    if x.coef[i]<=y.coef[i] then
      All_:=TRUE
        else
        begin
          All_:=FALSE;
          exit;
        end
 else all_:=FALSE;
end;

function modpow(a,b,n:TLong):TLong;
var d,q,r,q1:TLong;
    r1:longint;
begin
  if all(b,convert('0')) then
  begin
    modpow:=convert('1');
    exit;
  end;
  d:=convert('1');
  while all_(convert('0'),b) do
  begin
    divide_(mul_(d,d),n,q,r);
    d := r;
    if not check(b,convert('2')) then
      divide_(mul_(d,a),n,q,r);
    d := r;
    divide(b,2,q1,r1);
    b := q1;
  end;
  modpow := d;
end;
//--------------------------------------------------------
              //Ïðîâåðêà íà ïðîñòîòó p è q
//--------------------------------------------------------
function s_(n:TLong):TLong;
var n1,q,k:TLong;
    r:longint;
begin
  zero(n1);
  zero(q);
  zero(k);
  n1:=n;
  k:=convert('0');
  while check(n1,convert('2')) do
  begin
    divide(minus(n1,convert('1')),2,q,r);
    n1:=add(q,convert('1'));
    k:=add(k,convert('1'));
  end;
  s_:=k;
end;

function t_(n:TLong):TLong;
var q,r:TLong;
begin
  zero(q);
  zero(r);
  divide_(minus(n,convert('1')),power(2,s_(n)),q,r);
  t_:=q;
end;

function a_(n:TLong):TLong;
var s:TLong;
begin
  zero(s);
  rand(n.Length,s);
  if (all_(convert('1'),s)) and (all_(s,n))then a_:=s
    else a_(n)
end;

function  n_a(n,a:TLong):boolean;
begin
  if check(n,a) then
    n_a:=true;
end;

function  next1(n,a:TLong):boolean;
begin
  if all(modpow(a,t_(n),n),convert('1')) then
    next1:=TRUE
    else next1:=FALSE;
end;

{function  next2(n,a:TLong):boolean;
var d,h,q,r,k,t,s:TLong;
begin
  t:=t_(n);
  s:=s_(n);
  d:=convert('0');
  while all(d,n) do
  begin
    h:=minus(mul_(n,d),convert('1'));
    while all(k,minus(s,convert('1'))) do
    begin
      if all(h,convert('1')) then
      begin
        next2:=TRUE;
        exit;
      end
      else
      begin
        divide_(h,pow(a,t),q,r);
        h:=q;
      end;

      k:=add(k,convert('1'));
    end;

    d:=add(d,convert('1'));
  end;
  next2:=FALSE;
end;    }

function  next2(n,a:TLong):boolean;
var q,r,k,s,t,l:TLong;
begin
  zero(q);
  zero(r);
  zero(k);
  zero(s);
  zero(t);
  zero(l);
  s:=s_(n);
  k:=convert('0');
  t:=t_(n);
  {while all(k,minus(s,convert('1'))) do
  begin
    L:=mul_(power(2,k),t);
    if all(modpow(a,l,n),minus(n,convert('1'))) then
    begin
      next2:=TRUE;
      exit;
    end
    else
    k:=add(k,convert('1'));
  end;}
  next2:=FALSE;
end;

function  prost(var n:TLong):boolean;
var a,i,k:TLong;
begin
  zero(a);
  while (check(n,convert('2'))) or (check(n,convert('5'))) do
    rand(100,n);
  a:=a_(n);
  if check(n,a) then
  begin
    print(n);
    prost:=FALSE;
    exit;
  end;
  i:=convert('0');
  k:=mul(convert('10'),n.length);
  while ((next1(n,a)) or (next2(n,a))) and (all_(i,convert('10'))) do
  begin
    a:=a_(n);
    if check(n,a) then
    begin
      print(n);
      prost:=FALSE;
      exit;
    end;
    i:=add(i,convert('1'));
  end;
  print(n);
  prost:=TRUE;
end;
//--------------------------------------------------------
              //RSA
//--------------------------------------------------------
function euclid(a, b:TLong):TLong; //ÍÎÄ äâóõ ÷èñåë
var x,y:TLong;
begin
  x:=a;
  y:=b;
  while not all(x,y) do
  begin
    if all_(y,x) then
      x:=minus(x,y)
    else y:=minus(y,x);
  end;
  euclid:=x;
end;

function d_(p,q:TLong):TLong;
var m,d:TLong;
begin
  m:=mul_(minus(p,convert('1')),minus(q,convert('1')));
  while not all(euclid(m,d),convert('1')) do
    rand(MaxLen,d);
  d_:=d; 
end;


end.

вероятно с длиной я переборщил..., первая часть это модуль длинной арифметики, вторая: функции для проверки на простоту
алгоритмы брал [Вы должны быть зарегистрированы и подключены, чтобы видеть эту ссылку]

Тут мне кажется разобраться невозможно. Извини уж(

жалко( пойду тестить каждую функцию....может поможет

Ищи где ты что-то делишь на что-то, вдруг то, на что ты делишь может оказаться нулем.
Потом смотри размерность массивов, везде ли она совпадает с нужной и не заходишь ли ты где-нибудь за границу.

Я вроде ручками справился, только одна осталась, не понимаю в чем проблема.
все функции кроме prost() проверены и протестированы, они работают. При запуске prost она вылетает на t:=t_(n); print(t); ну или между ними, это в самых верхних строчках prost, это странно так как отдельно они все работают. Подскажите, ппожалуйста, что делать.

Код:


function s_(n:TLong):TLong;
var n1,q,k:TLong;
    r:longint;
begin
  zero(q);
  zero(k);
  k:=convert('0');
  if not check(n,convert('2')) then
  begin
    divide(minus(n,convert('1')),2,q,r);
    n1:=q;
    k:=convert('1');
    while check(n1,convert('2')) do
    begin
      divide(n1,2,q,r);
      n1:=q;
      k:=add(k,convert('1'));
    end;
  end; 
  s_:=k;
end;

function t_(n:TLong):TLong;
var q,r:TLong;
begin
  zero(q);
  zero(r);
  if not check(n,convert('2')) then
    divide_(minus(n,convert('1')),power(convert('2'),s_(n)),q,r);
  t_:=q;
end;

function a_(n:TLong):TLong;
var s:TLong;
begin
  rand(n.Length,s);
  if (all_(convert('1'),s)) and (all_(s,n))then a_:=s
    else a_(n)
end;

function  n_a(n,a:TLong):boolean;
begin
  if check(n,a) then
    n_a:=true;
end;

function  next1(n,a:TLong):boolean;
begin
  if all(modpow(a,t_(n),n),convert('1')) then
    next1:=TRUE
    else next1:=FALSE;
end;

function  next2(n,a:TLong):boolean;
var q,r,k,s,t,l:TLong;
begin
  zero(q);
  zero(r);
  zero(k);
  zero(s);
  zero(t);
  zero(l);
  s:=s_(n);
  k:=convert('0');
  t:=t_(n);
  while all_(k,minus(s,convert('1'))) do
  begin
    L:=mul_(power(convert('2'),k),t);
    if all(modpow(a,L,n),minus(n,convert('1'))) then
    begin
      next2:=TRUE;
      exit;
    end
    else
    k:=add(k,convert('1'));
  end;
  next2:=FALSE;
end;

function  prost(n:TLong):boolean;
var a,i,k,s,t:TLong;
begin
  zero(a);
  zero(i);
  zero(k);
  zero(s);
  zero(t);
  s:=s_(n);
  print(s);
  t:=t_(n); //<----------------
  print(t); //<----------------
  a:=a_(n);
  print(a);
  if check(n,a) then
  begin
    print(n);
    prost:=FALSE;
    exit;
  end;
  i:=convert('0');
  //k:=mul(convert('10'),n.length);
  while ((next1(n,a)) or (next2(n,a))) and (all_(i,convert('10'))) do
  begin
    a:=a_(n);
    if check(n,a) then
    begin
      print(n);
      prost:=FALSE;
      exit;
    end;
    i:=add(i,convert('1'));
  end;
  print(n);
  prost:=TRUE;
end;

А откуда вообще переменная "n" берется? Где вообще у тебя эти глобальные переменные?
Действительно странно. У меня только одно предположение. По отдельности все процедуры работают правильно. Процедуру S_(n) выполняет нормально. Потом следует правильно работающая отдельно процедура t_(n), на которой прога вылетает.
Логично предположить, что в процедуре S_(n) ты как-то изменяешь переменную n, так, что уже в t_(n) эта переменная не подходит и соответственно вылетает.

Из предыдущего твоего поста я заметил, что в процедуре Divide, которая используется и в s_(n) ты используешь внутренние переменные N, M и т.д. А разницы нет, что n маленькая, что большая. Компьютер может решить, что ты используешь не внутреннюю переменную N, а глобальную n и изменить ее значение вместо значения N. Это объясняет почему процедуры отдельно работают нормально, а вместе вылетают. Попробуй назови переменные иначе, чтобы нигде не встречалось повторов названий.

я попробовал все поменять, на 300-ой строчке спекся, запустил программу и после некоторых манипуляций, я увидел почему она вырубается, там пишется ошибка: деление на 0. Но ведь если программа выдает эту ошибку, значит деление происходит стандартной функцией ':', или нет?

все, кажется теперь работает, только вот если поставить MaxLen = 10000;
он пишет, что стек переполнен....может где-то используется в стандартных...а если MaxLen = 1000; то все хорошо)
можно последний вопрос?
подскажите, пожалуйста, как делать "Выбрать число e так, чтобы e * d = 1 (mod m)" тоже для длинных чисел, мой мозг уже устал((
d и m даны, e нужно найти.
я знаю способ через алгоритм Евклида, но там в некоторые моменты возникают отрицательные числа, что для меня недопустимо(