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

Обозначения и определения для функции дискретного возведения в степень вида A-v modulo N.

Пусть I_n = Z_q представляет собой множество {1, …, q}, где q = (р (М) — значение функции Эйлера для модуля М, a Z'" _M — множество вычетов по модулю М, где п = Гlog₂Ml Пусть распределение D^p есть равномерное распределение вероятностей. Оракульной программой в данном случае является программа вычисления функции g^x modulo М по отношению к исследуемым самотестирующейся и самокорректирующейся программам.

Алгоритм А^х modulo N можно вычислить многими способами ([4] и др.). Среди них один из наиболее известных и широко применяемых на практике — это алгоритм, основанный на считывании индекса (значения степени) слева направо. Этот метод достаточно прост и нагляден, история его восходит к 200 г. до н.э. Метод известен также как русский крестьянский метод.

Пустьх[1,…, п] —двоичное представление положительного числах и А, В и N — положительные целые числа в r-ичной системе счисления, тогда псевдокод алгоритма А^х modulo N, реализованного программой Ехр (-), имеет следующий вид.

Листинг 6.22. Псевдокод алгоритма А^х modulo JV

Из описания алгоритма следует, что число обращений к операции вида А*В modulo N будет logx + (3(х), где Р (х) — число единиц в двоичном представлении операнда х или вес Хэмминга х.