3. Устойчивость, линейная и единичная состоятельность

Пусть свойство Iвыражается уравнениемI(x₁,...,x_k)=0, где кортеж (x₁,...,x_k) выбирается с распределениемEиз пространстваD^k. Пара (I,E) характеризует семейство функцийF, гдеfFтогда и только тогда, когда для всех (x₁,...,x_k) с ненулевой выборкой элементов кортежа изE,I ^f(x₁,...,x_k)=0. Базовой техникой самотестирования является идентификация свойстваустойчивостидля семейства функцийF. Неформально (D,D)-устойчивостьпары (I,E) для семейства функцийGреализует, что если для программыPG, свойствоI^P(x₁,...,x_k)=0 удовлетворяется с высокой вероятностью, когдаx₁,...,x_kвыбрано с распределениемEизD^k, тогда существует функцияgFG, которая согласуется сPна большей части входов изD.

Рассмотрим некоторое свойство линейности (I,E), где свойствоI ^f(x₁,x₂,x₃) тождественноf(x₁)+f(x₂)=f(x₃) иEозначает (x₁_RZ_p,x₂_RZ_p,x₁+x₂). Пара (I,E) характеризуетF={f(x)=cxcZ_p} – множество всех линейных функций надZ_p. В этом примереG– тривиальное множество всех функций и пара (I,E) устойчива для G.

Как только мы убедились посредством рандомизированных попыток, что программа Рудовлетворяет свойству устойчивости, можно переходить к тестированию программы на линейную и единичную состоятельность.

Существует два базовых теста для самотестирующихся программ – тест линейной состоятельностиитест единичной состоятельности [BLR]. Продемонстрируем построение таких тестов на примере следующей тривиальной модулярной функции. Пустьx,R– положительные целые, тогдаf_R(x)x (mod R), гдеR- фиксировано.

Пусть x₁иx₂случайно, равновероятно и независимо от других событий выбраны из Z_R2ⁿиxпринимает значение:x:x₁+x₂(mod R2ⁿ). Необходимо отметить, чтоf_R(x)[f_R(x₁)+f_R(x₂)](modR) – линейная функция по всем входам (аргументам). Тогдатест линейной состоятельностизаключается в выполнении или не выполнении равенства:P_R(x)[P_R(x₁)+P_R(x₂)](modR), аошибка линейной состоятельности– есть вероятность того, что данный тест не выполнился.

Пусть zслучайно выбрано из Z_R2ⁿв соответствии с распределениемиzпринимает значение:z:z+1(mod R2ⁿ). Отметим также, чтоf_R(z)[f_R(z)+1](modR). Тогдатест единичной состоятельностизаключается в выполнении или не выполнении равенства:P_R(z)[P_R(z)+1](modR), аошибка единичной состоятельности– есть вероятность того, что данный тест не выполнился.

4. Метод создания самокорректирующейся процедуры вычисления теоретико-числовой функции дискретного экспоненцирования

   1. Обозначения и определения для функции дискретного возведения в степень вида gxmodulo m.

Пусть I_n=Z_qпредставляет собой множество {1,...,q}, гдеq=(M) - значение функции Эйлера для модуляM, аZ^*_M- множество вычетов по модулюM, гдеn=log₂M. Пусть распределениеD^pесть равномерное распределение вероятностей. Оракульной программой, в данном случае, является программа вычисления функцииg^xmoduloM, по отношению к исследуемым самотестирующейся и самокорректирующейся программам.

Алгоритм A^xmoduloN можно вычислить многими способами [Кн и др.], один из наиболее общеизвестных и применяемых на практике, - это алгоритм, основанный на считывании индекса (значения степени) слева направо. Этот метод достаточно прост и нагляден, история его восходит еще к 200 г. до н.э. Он еще также известен как русский крестьянский метод.

Пусть x[1,...,n] - двоичное представление положительного числаxиA,BиN- положительные целые числа вr-ичной системе счисления, тогда псевдокод алгоритмаA^xmoduloN, реализованного программой Exp() имеет следующий вид.

Program Exp(x,N,A,R); {вход x,N,A, выход R}

begin

B:=1;

for i:=1 to n do

begin

B:=(B*B)modN;

if [i]=1 then B:=(A*B)modN;

end;

R:=B;

end.

Рис. 4.1. Псевдокод алгоритма A^xmoduloN

Из описания алгоритма видно, что число обращений к операции вида (A*B)moduloNбудет logx+(x), где(x) число единиц в двоичном представлении операндаxили вес Хэммингаx.