Разработка эффективных алгоритмов вычисления НОД натуральных чисел для криптографии и теории чисел

Таблица 1 —Вычисления НОД с помощью аппроксимирующего алгоритма для 33-битовых чисел А и В и к = 64._______ ______ А В А / В Я а ш X= п У С 1 1736704041 1210259647 1,43 23 0,587 41 62 -82 2430861 2 1210259647 2430861 498 59 0,857 6 7 -3485 4174 3 2430861 4174 583 7 0,997 62 63 -36665 419 4 4174 419 10,0 57 0,265 9 34 -338 3 Ответ: GCD= 3. Из примера видно, что даже при небольших значениях к аппроксими­ рующий алгоритм обеспечивает быструю сходимость вычисления, значительно обгоняя предыдущие алгоритмы по значению коэффици­ ента редукции р — А /В . В этой главе нами были получены следующие результаты: 1. Была разработана процедура генерации пар чисел, взаимно пр стых с параметров к, имеющих различную длину от 100 до 1000 десятич­ ных разрядов. 2. Реализована базовая процедура вычисления НОД с использ е м алгоритма Евклида с выводом в ответ общего и среднего числа итераций _'+sd суммарного времени по серии из N испытаний для произвольного N . ) J '-Подобрано значение N = 50, достаточное для того, чтобы сгладить флук- ) туации средних значений параметров относительно средних значений и "*5^члюлучать реальные оценки сходимости алгоритма в зависимости от длин исходных пар. 3. Разработана базовая модель реализации аппроксимирующего алг ритма на языке C++ в системе MS Visual Studio 2012 с использованием библиотеки длинных чисел MPIR. Выполнены реализации на компьютере основных процедур, входящих в базовую схему аппроксимирующего алго­ ритма. Такими процедурами являются: 3.1. Процедура вычисления параметров г = A / В и q = А В ~1 mo путем прямых вычислений и с использованием предвычисленных таблиц. 3.2. Процедура ускоренного вычисления параметра г = A / В с использованием особенностей представления длинных чисел в библиотеке MPIR с обращением к отдельным частям (лимбам) длинных чисел. 3.3. Процедура аппроксимации действительного параметра а дро­ бью с ограниченным значением знаменателя. 4. Разработана и реализована эффективная модель, аппроксимаци действительного параметра а праЬильн{Т^ |ДрфИо;'с,'(^йрани чйнным знаме­ нателем с использованием рядов Ш |^ я .д Н . Т у п о Л < ; ^ а ! 17 ьиЬлиотека