Лемма 2.2.

Лемма 2.2. Программа S_T_exp(n,M,q,g,β) является (1/288,1/8)самотестирующейся программой, которая контролирует результат вычисления значения функции gxmoduloM с любым модулем M.

Доказательство. Полнота теста линейной состоятельности доказывается аналогично доказательству полноты в лемме й, где x1,x2 RZq. Полнота теста единичной состоятельности вытекает исходя из следующего очевидного факта. Корректное выполнение теста [PM,g(x1)'PM.g(1)](mod M) соответствует вычислению функции:

Для доказательства условия самотестируемости необходимо отметить, что так как и в лемме 1 для того, чтобы вероятность корректных ответов Rl и Re в обоих тестах была не более 1β достаточно выполнить тест линейной состоятельности 576ln(4/β) раз и тест единичной состоятельности 32ln(4/β) раз.

Можно показать, основываясь на теоретико групповых рассуждениях, что возможно обобщение программы S_T(') и для других групп (алгоритмы данной программы основываются на вычислениях в мультипликативной группе вычетов над конечным полем). То есть для всех yG, P(y)G*, где G* представляет собой любую группу, кроме групп G**. К группам последнего вида относятся бесконечные группы, не имеющие конечных подгрупп за исключением {О`}, где О` тождество группы. Таким образом, можно показать (при использовании в вышеуказанных алгоритмах параметров с их независимым, равновероятным и случайным выбором), что программа вида S_T(') является (ε/36,ε)самотестирующейся программой. Отсюда следует доказательство утверждения леммы

Исходя из определения самотестирующейся/ самокорректирующейся программной пары и основываясь на результатах доказательств лемм 1 и 2, очевидным образом следует доказательство теоремы 1.

Замечания. Как видно из псевдокода алгоритма 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, может осуществляться на большее число слагаемых. Хотя это приведет к гораздо большему количеству вызовов оракульной программы, но в то же время позволит значительно снизить вероятность ошибки.


Ведете ли вы блог?

Да
Нет
Планирую


Результаты опроса

Новостной блок