Программируем

Пожалуйста, зарегистрируйтесь или войдите под уже созданным логином. Вы получите полный доступ ко всем статьям форума.

Join the forum, it's quick and easy

Программируем

Пожалуйста, зарегистрируйтесь или войдите под уже созданным логином. Вы получите полный доступ ко всем статьям форума.

Программируем

Вы хотите отреагировать на этот пост ? Создайте аккаунт всего в несколько кликов или войдите на форум.
Программируем

На нашем форуме программистов вы сможете найти софт для программирования и другие программы. На форуме обсуждаются многие языки программирования, задачи и их решения. Используются языки: C, Assembler, Pascal, Delphi, Flash и другие.

Последние темы

» Арена искусственных интеллектов Gridwars
проверка на простоту, RSA EmptyСр Окт 12, 2016 2:43 am автор SeriousPasha

» требуется несколько JS разработчиков
проверка на простоту, RSA EmptyПт Окт 07, 2016 10:19 pm автор mrktwn1

» Защита приложения от взлома
проверка на простоту, RSA EmptyЧт Июн 18, 2015 10:28 pm автор stradi

» Ищите программиста или дизайнера?
проверка на простоту, RSA EmptyПт Мар 27, 2015 6:25 am автор фриланс

» Создание и продвижение сайтов, их развитие.
проверка на простоту, RSA EmptyСр Мар 25, 2015 12:40 am автор asdfghhgfdsa

» Исходники для студентов + скайп-консультации,помощь в написании программ
проверка на простоту, RSA EmptyВт Окт 07, 2014 11:25 pm автор Horpion

» IT- технологии для развития бизнеса
проверка на простоту, RSA EmptyПн Июн 23, 2014 6:11 pm автор dvos12

» Стенли Кубрик "С Широко закрытыми Глазами"
проверка на простоту, RSA EmptyЧт Июн 12, 2014 2:01 am автор Vertuozzz

» Каталог популярных хостинг компаний
проверка на простоту, RSA EmptyСб Май 10, 2014 7:18 pm автор naik

Самые активные пользователи

Aster (142)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
Exkalibur (89)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
Чебурашка (63)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
Administrator (34)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
ak95 (8)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
Пушкин (7)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
K4_ (7)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
LuDa (7)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
Goldcoding (6)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 
Admin (6)
проверка на простоту, RSA Bar_leftпроверка на простоту, RSA Barпроверка на простоту, RSA Bar_right 

Партнеры

проверка на простоту, RSA Top100 Rambler's Top100

Участников: 2

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

    avatar
    ak95
    Новичек
    Новичек


    Сообщения : 8
    Очки : 10
    Репутация : 0
    Дата регистрации : 2011-06-19
    Возраст : 29
    Откуда : Москва

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

    Сообщение автор ak95 Вс Июн 19, 2011 4:14 pm

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


    Сообщения : 8
    Очки : 10
    Репутация : 0
    Дата регистрации : 2011-06-19
    Возраст : 29
    Откуда : Москва

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

    Сообщение автор ak95 Вс Июн 19, 2011 4:16 pm

    [Вы должны быть зарегистрированы и подключены, чтобы видеть эту ссылку]
    Aster
    Aster
    Admin
    Admin


    Сообщения : 142
    Очки : 274
    Репутация : 11
    Дата регистрации : 2010-01-07

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

    Сообщение автор Aster Вс Июн 19, 2011 4:23 pm

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


    Сообщения : 8
    Очки : 10
    Репутация : 0
    Дата регистрации : 2011-06-19
    Возраст : 29
    Откуда : Москва

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

    Сообщение автор ak95 Вс Июн 19, 2011 4:58 pm

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


    Сообщения : 142
    Очки : 274
    Репутация : 11
    Дата регистрации : 2010-01-07

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

    Сообщение автор Aster Вс Июн 19, 2011 4:59 pm

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


    Сообщения : 8
    Очки : 10
    Репутация : 0
    Дата регистрации : 2011-06-19
    Возраст : 29
    Откуда : Москва

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

    Сообщение автор ak95 Вс Июн 19, 2011 5:12 pm

    Код:

    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.
    вероятно с длиной я переборщил..., первая часть это модуль длинной арифметики, вторая: функции для проверки на простоту
    алгоритмы брал [Вы должны быть зарегистрированы и подключены, чтобы видеть эту ссылку]
    Aster
    Aster
    Admin
    Admin


    Сообщения : 142
    Очки : 274
    Репутация : 11
    Дата регистрации : 2010-01-07

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

    Сообщение автор Aster Вс Июн 19, 2011 5:25 pm

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


    Сообщения : 8
    Очки : 10
    Репутация : 0
    Дата регистрации : 2011-06-19
    Возраст : 29
    Откуда : Москва

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

    Сообщение автор ak95 Вс Июн 19, 2011 5:27 pm

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


    Сообщения : 142
    Очки : 274
    Репутация : 11
    Дата регистрации : 2010-01-07

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

    Сообщение автор Aster Вс Июн 19, 2011 5:29 pm

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


    Сообщения : 8
    Очки : 10
    Репутация : 0
    Дата регистрации : 2011-06-19
    Возраст : 29
    Откуда : Москва

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

    Сообщение автор ak95 Вс Июн 19, 2011 8:50 pm

    Я вроде ручками справился, только одна осталась, не понимаю в чем проблема.
    все функции кроме 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;
    Aster
    Aster
    Admin
    Admin


    Сообщения : 142
    Очки : 274
    Репутация : 11
    Дата регистрации : 2010-01-07

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

    Сообщение автор Aster Вс Июн 19, 2011 9:26 pm

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

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


    Сообщения : 8
    Очки : 10
    Репутация : 0
    Дата регистрации : 2011-06-19
    Возраст : 29
    Откуда : Москва

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

    Сообщение автор ak95 Вс Июн 19, 2011 10:25 pm

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


    Сообщения : 8
    Очки : 10
    Репутация : 0
    Дата регистрации : 2011-06-19
    Возраст : 29
    Откуда : Москва

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

    Сообщение автор ak95 Вс Июн 19, 2011 11:04 pm

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

      Текущее время Пт Мар 29, 2024 3:28 pm