Построение самотестирующейся/самокорректирующейся
Сначала рассмотрим следующие 4 алгоритма (см. рис.4.2 - 4.5). Для доказательства полноты и безопасности указанной самотестирующейся/ самокорректирующейся программной пары доказывается следующая теорема.
Теорема 4.1. Пара программ S_K_exp(x,M,q,g,b) и S_T_exp(x,M,q,g,b) является (1/288,1/8,1/8)-самокорректирующейся/ самотестирующейся программной парой для функции gxmoduloM с входными значениями, выбранными случайно и равновероятно из множества In.
Для доказательства теоремы необходимо доказать две леммы.
Лемма4.1. Программа S_K_exp(M,q,g,b) является (1/8)-самокорректи-рующейся программой для вычисления функции gxmoduloM в отношении равномерного распределения Dn.
Доказательство.
Полнота программы S_K(?) означает, что если оракульная программа P(x), обозначаемая как Exp(?) выполняется корректно, то и самокорректирующаяся программа S_K(?) будет выполняться корректно. В данном случае полнота программы очевидна. Если P(x) корректно вычислима, то из [PM,g(x1)?PM.g(x2)](modM) следует, что fM,g(x)=fM,g(x1)°fM,g(x2)=
Program S_K_exp(x,M,q,g, Rk); {вход n,x,M,q,g, выход Rk}
begin
for l=1 to 12ln(1/b)
begin
x1:=random(q); {random- функция случайного равновероятного выбора из целочисленного отрезка
[1,...,q-1]}
x2:=(x-x1)modq;
Exp(g,x1,M,R1); {Exp- процедура вычисления gxmoduloM=R}
Exp(g,x2,M,R2);
R0:=(R1×R2)modM;
end;
Rk=choice(R0(l)); {choice- функция выбора из массива, состоящего из 12ln(1/b) элементов, ответов, который повторяется наибольшее количество раз}
end.
Рис. 4.2. Псевдокод алгоритма S_K_exp
Program S_T_exp(x,M,q,g,b); {вход x,M,q,g, выход значение предиката output}
begin
t1:=0;t2:=0;
for l=1 to é576ln(4/b)ù
begin
L_T(g,M,q,Rl); {L_T - процедура, реализующая тест линейной состоятельности, выход - Rl}
t1:=t1+Rl;
end;
if t1/é576ln(4/b)ù>1/72 then output:=«false»;
for l=1 to é32(4/b)ù
begin
N_T(g,M,q,Re); {N-T - процедура, реализующая тест единичной состоятельности, выход - Re}
t2:=t2+R;
end;
if t2/é32ln(4/b)ù>1/4 then output:= «false»
else output:=«true»
end.
Рис. 4.3. Псевдокод алгоритма S_T_exp
Program L_T(n,R); {вход g,M,q, выход Rl}
begin
x1:=random(q);
x2:=random(q);
x:=(x1+x2)modq;
Exp(g,x1,M,R1);
Exp(g,x2,M,R2);
Exp(g,x,M,R);
if R1×R2=R then Rl:=1
else Rl:=0;
end.
Рис. 4.4. Псевдокод алгоритма теста линейной состоятельности L_T
Program N_T(n,R); {вход g,M,q, выход Re}
begin
x1:=random(q);
x2:=(x1+1)modq;
Exp(g,x1,M,R1);
Exp(g,x2,M,R2);
if R1×g=R2 then Re:=1
else Re:=0;
end.
Рис. 4.5. Псевдокод алгоритма теста единичной состоятельности N_T
Для доказательства безопасности сначала необходимо отметить, что так как x1ÎRZq, то и x2 имеет равномерное распределение вероятностей над Zq. Так как вероятность ошибки e£1/8, то в одном цикле вероятность Prob[Rk=fM,g(x)]³3/4. Чтобы вероятность корректного ответа была не менее чем 1-b, исходя из оценки Чернова [Be1,BLR], необходимо выполнить не менее 12ln(1/b) циклов n.
Лемма 4.2. Программа S_T_exp(n,M,q,g,b) является (1/288,1/8)-самотестирующейся программой, которая контролирует результат вычисления значения функции gxmoduloM с любым модулем M.
Доказательство.
Полнота программы S_T(?) доказывается аналогично доказательству полноты в лемме 4.1, где x1,x2ÎRZq. Полнота теста единичной состоятельности вытекает исходя из следующего очевидного факта. Корректное выполнение теста [PM,g(x1)?PM.g(1)](mod M) соответствует вычислению функции:
fM,g(x)=fM,g(x1)°fM,g(1)=
Для доказательства условия самотестируемости необходимо отметить, что так как и в лемме 4.1 для того, чтобы вероятность корректных ответов Rl и Re в обоих тестах была не более 1-b
достаточно выполнить тест линейной состоятельности é576ln(4/b)ù раз и тест единичной состоятельности é32ln(4/b)ù раз.
Можно показать, основываясь на теоретико-групповых рассуждениях, что возможно обобщение программы S_T(?) и для других групп (вышеописанные алгоритмы основываются на вычислениях в мультипликативной группе вычетов над конечным полем). То есть для всех yÎG, P(y)ÎG*, где G*
-представляет собой любую группу, кроме групп G**. К группам последнего вида относятся бесконечные группы, не имеющие конечных подгрупп за исключением {О¢}, где О¢ - тождество группы. Таким образом, можно показать (если параметры выбираются независимо, равновероятно и случайным образом), что программа вида S_T(?) является (e/36,e)-самотестирующейся программой. Из всего сказанного, следует доказательство утверждения леммы n.
Исходя из определения самотестирующейся/ самокорректирующейся программной пары и основываясь на результатах доказательств лемм 1 и 2, очевидным образом следует доказательство теоремы 1 n.
Замечания. Как видно из псевдокода алгоритма Axmodulo N в нем используется операция ABmodulo N. Используя ту же технику доказательств, как и для функции дискретного возведения в степень, можно построить (1/576,1/36,1/36)-самокорректирующуюся/ самотестирующуюся программную пару для вычисления функции модулярного умножения. Это справедливо, исходя из следующих соображений. Вычисление функции fM(ab)=fM((a1+a2)(b1+b2)) следует из корректного выполнения программы с 4-х кратным вызовом оракульной программы P(a,b), то есть:
[PM(a1,b1)+PM(a1,b2)+PM(a2,b1)+PM(a2,b2)](mod M).
Алгоритм вычисления Axmodulo N
выполняется для c=2. Однако, декомпозиция x, как следует из свойства самосводимости функции Axmodulo N, может осуществляться на большее число слагаемых. Хотя это приведет к гораздо большему количеству вызовов оракульной программы, но в то же время позволит значительно снизить вероятность ошибки.
