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

       

Время выполнения программы


Рис.4.8. Псевдокод алгоритма самокорректирующейся

программы умножения матриц

Время выполнения программы S_K_multAB составляет О(M(n)+n2log(1/k)), где M(n) – время выполнения программы умножения матриц размером n´n [BLR].

Самотестирующаяся программа для умножения матриц строится достаточно просто.

 

Program S_T_multAB(A,B,k); {вход A,B,k, выход («Норма»,«Сбой»)}

         begin

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

            begin

                       A:=random(F);            {random - функция случайного равновероятного и независимого выбора матрицы размером (n´n) из F};

                       B:=random(F);            {random - функция случайного равновероятного и независимого выбора матрицы размером (n´n) из F};

                       C:=P(A,B);

                       if C_F(A,B,C,1/4)=«Норма» then output 0 and goto 1;

                       if C_F(A,B,C,1/4)=«Сбой» then output 1 and goto 1;

          end;

1:end.



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