Построение самотестирующейся/самокорректирующейся программной пары для функции дискретного экспоненцирования

Прежде всего рассмотрим следующие четыре алгоритма (см. листинги 6.23—6.26).

Листинг 6.23. Псевдокод алгоритма S_K_exp.

Листинг 6.24. Псевдокод алгоритма S_T_exp 150.

Листинг 6.25. Псевдокод алгоритма теста линейной состоятельности L_T.

Листинг 6.26. Псевдокод алгоритма теста единичной состоятельности N_T.

Для доказательства полноты и безопасности указанной самотестирующейся/самокорректирующейся программной пары доказывается следующая теорема.

Теорема 6.2. Пара программ S_K_exp (x, М, q, g, (3) и S_T_exp (x, М, q, g, (3) является (1/288, 1/8, 1/8)-самокорректирующейся/самотестирующейся программной парой для функции g^x modulo М с входными значениями, выбранными случайно и равновероятно из множества 1_п.

Для доказательства теоремы необходимо доказать две леммы.

Лемма 6.1. Программа S_K_exp (M, q, g, (3) является (1/8)-самокорректирующейся программой для вычисления функции g^x modulo М в отношении равномерного распределения D_n.

Доказательство. Сначала покажем, что если оракульная программа Р (х), обозначаемая как Ехр (-), выполняется корректно на большинстве входов, то и самокорректирующаяся программа S_K (-) будет выполняться корректно. В данном случае это очевидно. Если Р (х) корректно вычислима, то из [Р_м^(х_х)] • Р_м «(х₂)] (mod М) следует, что.

Для доказательства того, что на большинстве входов программа S_K (-) выдает корректный результат, необходимо отметить, что так как x₁ е _RZ_q, то и х₂ имеет равномерное распределение вероятностей над.

Zq. Так как вероятность ошибки г < 1/8, то в одном цикле вероятность Prob [R_k =/_Mg(x) ] > ¾. Чтобы вероятность корректного ответа была не менее чем 1 — (3, исходя из оценки Чернова, необходимо выполнить не менее 121п (1/(3) циклов. ?

Лемма 6.2. Программа S_T_exp (n, М, q, g, (3) является (1/288, 1/8)-самотестирующейся программой, которая контролирует результат вычисления значения функции g^x modulo М с любым модулем М.

Доказательство. Корректность программы S_T (-) доказывается аналогично доказательству корректности в лемме 6.1, где х_ь х₂ е _RZ_q. Корректное выполнение теста единичной состоятельности [P^CxJ • P,_w^,(l)] (mod M) соответствует вычислению функции.

Для доказательства условия самотестируемости необходимо отметить, что, как и в лемме 6.1, для того чтобы вероятность корректных ответов Я, и R_e в обоих тестах была не менее чем 1 — (3, достаточно выполнить тест линейной состоятельности Г5761п (4/(3)! раз и тест единичной состоятельности Г321п (4/(3)! раз.

Можно показать, основываясь на общих положениях теории групп, что возможно обобщение программы S_T (-) и для других групп (вышеописанные алгоритмы основываются на вычислениях в мультипликативной группе вычетов над конечным полем), т. е. для всех у е G, Р (у) е G*, где G* представляет собой любую группу, кроме групп G**. К группам последнего вида относятся бесконечные группы, не имеющие конечных подгрупп за исключением {О'}, где О' — тождество группы. Таким образом, можно показать (если параметры выбираются независимо, равновероятно и случайным образом), что программа вида S_T (-) является (е/36, е)-самотестирующейся программой.? Исходя из определения самотестирующейся/самокорректирующейся программной пары и основываясь на результатах доказательств лемм 6.1 и 6.2, очевидным образом следует доказательство теоремы 6.2.? Замечания. Как следует из псевдокода алгоритма А^х modulo N, в нем, как уже говорилось, используется операция АВ modulo N. Используя ту же технику доказательств, что и для функции дискретного возведения в степень, можно построить (1/576, 1/36, 1/36)-самокорректирующуюся/самотестирующуюся программную пару для вычисления функции модулярного умножения. Это справедливо исходя из следующих соображений. Вычисление функции.

следует из корректного выполнения программы с 4-кратным вызовом оракульной программы Р (а, Ь), т. е.

Рис. 6.7. Схема работы самотестирующейся/самокорректирующейся.

программной пары Алгоритм вычисления А^х modulo N выполняется для с = 2. Однако декомпозиция х, как следует из свойства самосводимости функции А^х modulo N, может осуществляться на большее число слагаемых. Хотя это приведет к гораздо большему количеству вызовов оракульной программы, но в то же время позволит значительно снизить вероятность ошибки.

Таким образом, мы рассмотрели возможность создания самотестирующихся программ с эффективным тестирующим модулем. Такой модуль осуществляет автономное тестирование программ на предмет отсутствия/наличия преднамеренных и/или непреднамеренных программных дефектов и использует ST-napy функций (g_c, f_c), таких, что Y = g_c(f (<2|), …,/(а_с)) и X-h_c(f_u …, а_с) для некоторого входного вектора X, которые используют свойство рандомизированной самосводимости функции Y =/(Х), вычисляемой посредством программы Р. Для этого реализуется алгоритм, блок-схема которого приведена на рис. 6.1.