• Главная
• Новости
• Статьи
• Карта сайта
• Поиск
• Контакт
• Рекомендации

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

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

Обозначения и определения для функции дискретного возведения в степень вида g^xmoduloM. Пусть I_n=Z_q представляет собой множество {1,...,q}, где q= φ(M) значение функции Эйлера для модуля M, а Z*_M множество вычетов по модулю M, где n= |log₂M|. Пусть распределение D^p есть равномерное распределение вероятностей. Тогда равновероятный случайный выбор элемента a из множества Ω будет обозначаться как a_RΩ. Оракульной программой, в данном случае, является программа вычисления функции g^xmoduloM, по отношению к исследуемым самотестирующейся и самокорректирующейся программам.

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

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