Обозначения и определения для функции дискретного возведения в степень вида gxmoduloM
Пусть In=Zq представляет собой множество {1,...,q}, где q=j(M) - значение функции Эйлера для модуля M, а Z*M
- множество вычетов по модулю M, где n=élog2Mù. Пусть распределение Dp есть равномерное распределение вероятностей. Оракульной программой, в данном случае, является программа вычисления функции gxmoduloM, по отношению к исследуемым самотестирующейся и самокорректирующейся программам.
Алгоритм Axmodulo N можно вычислить многими способами
[Кн и др.], один из наиболее общеизвестных и применяемых на практике, - это алгоритм, основанный на считывании индекса (значения степени) слева направо. Этот метод достаточно прост и нагляден, история его восходит еще к 200 г. до н.э. Он еще также известен как русский крестьянский метод.
Пусть x[1,...,n] - двоичное представление положительного числа x
и A, B и N - положительные целые числа в r-ичной системе счисления, тогда псевдокод алгоритма Axmodulo N, реализованного программой 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. Псевдокод алгоритма AxmoduloN
Из описания алгоритма видно, что число обращений к операции вида (A*B)moduloN будет logx+b(x), где b(x) число единиц в двоичном представлении операнда x или вес Хэмминга x.
