Теория и практика защиты программ

       

Вычисления над матрицами


Одной из первых работ в области вероятностных алгоритмов, которая, в конечном счете, явилась одной из основополагающей в области методологии самотестирования явилась работа Р.Фрейвалдса, написанная им еще в 1979 году. Он предложил следующий простой и элегантный чекер для задачи умножения матриц (рис.4.7).

Program P_S_T(P,e,b,x,f(x)); {вход P,e,b,(x1,f(x1)),...,xd+1,f(xd+1))),

выход («Норма»,«Сбой»)}

  begin

        for i=1 to O((1/k)log(1/b)) do

            begin

               x,t:=random(Zp);          {random - функция случайного равновероятного выбора из множества вычетов по модулю р};

                       if

(более, чем в e

итерациях) then output «Сбой»;

          end;

  output «Норма»;

        for j=0 to d do

            begin

                       for i=1 to O(log(d/b)) do

begin

                                  t:=random(Zp); {random - функция случайного равновероятного выбора из множества вычетов по модулю р};

                                  if

(более, чем в ¼

итерациях) then output «Сбой»;

                            end;

          end;

          output «Норма»;

end.



Содержание раздела