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

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

Обозначения и определения для функции дискретного возведения в степень вида gxmoduloM. Пусть In=Zq представляет собой множество {1,...,q}, где q= φ(M) значение функции Эйлера для модуля M, а Z*M множество вычетов по модулю M, где n= |log2M|. Пусть распределение Dp есть равномерное распределение вероятностей. Тогда равновероятный случайный выбор элемента a из множества Ω будет обозначаться как aRΩ. Оракульной программой, в данном случае, является программа вычисления функции gxmoduloM, по отношению к исследуемым самотестирующейся и самокорректирующейся программам.

Алгоритм Axmodulo N можно вычислить многими способами [34,64], один из наиболее общеизвестных и применяемых, это алгоритм, основанный на считывании индекса (значения степени) слева направо. Этот метод достаточно прост и нагляден, история его восходит еще к 200 г. до н.э. Пусть x[1,...,n] двоичное представление положительного числа x и A, B и N положительные целые числа в rичной системе счисления, тогда псевдокод алгоритма Axmodulo N, реализованного программой Exp(') имеет следующий вид.


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

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


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

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