Разработка эффективных алгоритмов вычисления НОД натуральных чисел для криптографии и теории чисел тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Амер Исмаил Ф. О.

• Амер Исмаил Ф. О.
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Амер Исмаил Ф. О.

Введение

Глава 1. Обзор алгоритмов вычисления наибольшего общего делителя (НОД) натуральных чисел и оценки их

сложности

1.1 Классический алгоритм Евклида

1.1.1 Расширенный алгоритм Евклида

1.1.2 Оценка производительности алгоритма Евклида

1.2 Бинарный алгоритм вычисления НОД

1.3 fc-арный алгоритм Евклида

1.4 Аппроксимирующий к-арный алгоритм

Глава 2. Программирование к-арного метода вычисления НОД

натуральных чисел

2.1 Методика экспериментальных вычислений

2.2 Исследование значений коэффициента редукции в зависимости

от к

2.3 Поиск подходящей пары (х,у) в fc-арном алгоритме

2.4 Методы ускорение процедуры поиска пары (х,у) в fc-арном алгоритме

2.5 Время вычисления НОД при использовании предтаблиц обратных элементов

2.6 Анализ значений х и у и выбор способа перебopa пар (х,у)

2.7 Использование предтаблиц значений х и у для заданных

значений а и b

2.8 Сдвиг интервала значений у

2.9 Экспериментальные результаты времени при сдвиге области значений у

2.10 Вычисления с большим сдвигом области значений у

2.11 Смешанный алгоритм на основе к-арного алгоритма и схемы Евклида

Стр.

2.12 Выводы по главе

Глава 3. Исследование аппроксимирующего к-арного

алгоритма вычисления НОД

3.1 Базовая схема аппроксимирующего алгоритма

3.2 Программирование аппроксимирующего ^-арного алгоритма в МРП1

3.3 Расчет времени и среднего числа итераций АКА

3.3.1 Оценка производительности вычисления НОД для

Ь = 330 бит

3.3.2 Оценка производительности вычисления НОД для

Ь = 825 бит

3.3.3 Оценка производительности вычисления НОД для

Ь = 1650 бит

3.4 Ускорение аппроксимирующего алгоритма

3.4.1 Ускоренное вычисление параметра г = А/В

3.4.2 Оценка времени вычисления НОД по новой схеме

3.4.3 Оптимизация вычисления параметра а и аппроксимирующей дроби Фарея

3.4.4 Построение аппроксимирующей дроби методом Фарея

3.4.5 Оценка трудоемкости процедуры Фарея

3.4.6 Вычисление параметра С = (Ах + Ву)/к

3.5 Приложения аппроксимирующего алгоритма

3.5.1 Тест простоты Миллера-Рабина

3.5.2 Поиск строго псевдопростых чисел

3.5.3 Экспериментальные результаты

3.6 Выводы по Главе

Заключение

Список сокращений и условных обозначений

Список литературы

Список рисунков

Стр.

Список таблиц

Приложение А. Коды программного комплекса

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

Введение

Диссертационная работа посвящена решению задачи построения эффективного программного обеспечения для реализации алгоритмов вычисления НОД (наибольшего общего делителя) натуральных чисел с точки зрения их приложений к вычислениям с длинными числами, используемых в криптографии и теории чисел. Задача вычисления наибольшего общего делителя (НОД) натуральных чисел представляет собой одну из наиболее распространённые задач, имеющих различные приложения в современной вычислительной математике. Процедура вычисления НОД присутствует во многих криптосистемах и алгоритмах факторизации. Именно поэтому, исследование алгоритмов вычисления НОД является важной темой.

С развитием мощных компьютеров, глобальных компьютерных сетей и информационных технологий становится более важной и задача защиты информации [1 4]. Криптография работает с длинными числами, выполняя задачи генерации криптографических ключей, операции шифрования и дешифрования данных. Современные криптографические алгоритмы работают с конечными полями большой размерности, выполняя многочисленные модулярные вычисления [5 9]. Обратные вычисления в конечных полях необходимо используют расширенный алгоритм Евклида и процедуру вычисления НОД в рассматриваемых алгебраических структурах [10].

Существует обширная литература по криптографии [11 15], первые работы по математической криптографии появились значительно раньше, например, классические работы Клода Шеннона1 [16].

Вычисление НОД является важной фундаментальной задачей теории чисел, успешное решение которой позволяет усовершенствовать алгоритмы широкого класса прикладных задач, связанных с использованием современной асимметричной криптографии [17 21] (алгоритмы RSA [22;23], Рабина [24], Эль-Гамаля [25], электронной цифровой подписи ЭЦП [17; 26], исследование порядка эллиптической кривой [27 29]) как правило, современные криптографические алгоритмы работают с длинными числами и предусматривают процедуру вычисления их НОД [30 32].

1 ht t ps: / / г u. wikip cdia.org/ wiki/ Шеннон, _ Клод

Наиболее распространенным из таких алгоритмов является классический алгоритм Евклида. Однако известны и другие алгоритмы, общей целью создания которых было стремление уменьшить сложность вычисления НОД, сократить время его поиска.

Одним из самых перспективных таких алгоритмов является fc-арный алгоритм поиска GCD, опубликованный в 1990-х годах Джонатаном Соренсоном [33 35]. По сравнению с классическим алгоритмом Евклида данный алгоритм позволяет заметно снизить время вычислений при аккуратном выборе параметра к. В дальнейшем самим Соренсоном и другими учёными было предложено несколько вариантов улучшения и модификации к-арного алгоритма [36-38]. Одним из них является аппроксимирующий к-арный алгоритм, предложенный проф. Ш.Т. Ишмухаметовым [39].

Цель работы. Целью данной работы является сравнительное исследование трех алгоритмов вычисления НОД длинных натуральных чисел: классического алгоритма Евклида, fc-арного алгоритма Дж. Соренсона, аппроксимирующего к-арного алгоритма Ш.Т. Ишмухаметова и разработки эффективного программного обеспечения для реализации этих алгоритмов и ускорения операций вычисления наибольшего общего делителя с длинными целыми числами.

Задача сравнительного изучения трех алгоритмов вычисления НОД и построения эффективного программного обеспечения для их выполнения выполнена в полном объеме. Разработан пакет программ, реализующий базовые версии рассматриваемых алгоритмов, система тестирования, генерирующая пары чисел заданной длины и выполняющая контроль значений различных параметров вычисления таких, как время выполнения всей процедуры, среднее и максимальное число итераций для каждого из рассмотренных алгоритмов и наборов пар чисел заданной длины от 100 до 3000 бит, влияние различных методов ускорения на сходимость процедуры вычисления НОД.

С помощью этих программ были получены численные оценки сходимости трех рассматриваемых алгоритмов для различных входных наборов данных, выведены точные оценки времени выполнения процедуры вычисления НОД и числа итераций, доказана эффективность использования fc-арного алгоритма Соренсона КАРИ и аппроксимирующего алгоритма АКА для решения практических задач теории чисел и криптографии. Также определен новый комбинированный алгоритм КОМБИ, соединяющий простоту классического ал-

горитма Евклида и достоинства fc-арного алгоритма и выполняющийся быстрее обоих алгоритмов.

Для достижения поставленной цели были решены следующие задачи:

1. Выполнен анализ современных алгоритмов вычисления НОД натуральных чисел классического алгоритма Евклида КАЕ, бинарного алгоритма Стейна, fc-арного алгоритма и аппроксимирующего fc-арного алгоритма;

2. Разработан программный комплекс для выполнения полноценного тестирования всех трех рассматриваемых в диссертации алгоритмов, оценки влияния входных и промежуточных параметров на скорость выполнения процедуры, число итераций и время, затрачиваемое на каждой итерации и всей процедуры в целом.

3. Разработаны эффективные реализации алгоритмов вычисления НОД с использованием библиотеки длинных чисел MPIR2 в среде Visual Studio, на основе современных принципов программирования;

4. Выполнены экспериментальные вычисления и сбор статистического материала по скорости выполнения этих алгоритмов и числу итераций в зависимости от выбора параметров;

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

6. Разработаны практические приложения алгоритмов для решения сложных вычислительных задач (поиска строго псевдопростых чисел для ускорения теста простоты Миллера-Рабина.

Научная новизна: Аппроксимирующий fc-арный алгоритм является современным эффективным алгоритмом вычисления НОД, разработанный Ш.Т. Ишмухаметовым. До настоящих) времени не было ни одной полной реализации этого алгоритма для работы с длинными числами. Также никем не выполнялось сравнительное тестирование этого алгоритма в сравнении с другими известными алгоритмами вычисления НОД. Эта работа была выполнена впервые в нашей диссертации. Нами доказано абсолютное превосходство данного алгоритма над классическим алгоритмом Евклида и fc-арным алгоритмом Соренсона путем выполнения экспериментальных вычислений с числами различной дли-

2Torbjorn Granlund and the GMP Development Team. The Multiple Precision Integers and Rationals Library Edition 2. 2015. URL: http://mpir.Org/mpir-2.7.2.pdf

Также нами были разработаны методы, ускоряющие выполнение этого алгоритма с использованием особенностей представления длинных чисел в библиотеке MPIR и использования рядов Фарея для аппроксимации параметра а, играющего основную роль в этом алгоритме.

Основные достижения диссертации содержатся в следующем перечне:

1. Разработан программный комплекс, реализующий рассмотренные алгоритмы и выполняющий оценки их эффективности на языке программирования язык С • • в среде Visual Studio с использованием библиотеки длинных чисел MPIR);

2. Найдены оптимальные значения параметров, обеспечивающих быстрое выполнение fc-арного и аппроксимирующего алгоритмов для пар чисел различной длины;

3. Доказано практическое ускорение процедуры вычисления НОД с использованием fc-ариого и аппроксимирующего fc-арного алгоритмов по отношению к классическому алгоритму Евклида и бинарному алгоритму;

4. Выполнено исследование скорости сходимости fc-арного алгоритма Соренсона при сдвиге области значений параметров ж, у7 найдены оптимальные параметры и доказано практическое ускорение fc-арного алгоритма до 20

5. Выполнены экспериментальные оценки скорости вычисления НОД для чисел различной разрядности для аппроксимирующего fc-арного алгоритма, получены численные результаты сходимости этих алгоритмов в виде таблиц и графиков по числу итераций и времени вычислений для чисел различной длины до 2000 десятичных разрядов (примерно, 6500 бит).

6. Разработан новый комбинированный алгоритм КОМБИ вычисления НОД, основанный на сочетании на разных итерациях алгоритмов Евклида и fc-арного алгоритма, работающий до двух раз быстрее, чем исходные алгоритмы Евклида и Соренсона.

Теоретическая и практическая значимость работы. В диссертации были исследованы и построены новые эффективные версии алгоритмов вычисления НОД на основе алгоритмов Евклида, Соренсона и Ишмухаметова. Эти алгоритмы могут быть использованы в криптографии, теории чисел и других численных разделах математики при генерации параметров криптосистем с

открытым ключом (RSA), при поиске нетривиальных делителей натуральных чисел (факторизации чисел), при построении электронной цифровой подписи ЭЦП, построении архивов типа блокчейн и решении других задач с числами большой размерности.

Методология и методы исследования. При выполнение работы использовались методы теории чисел, арифметические операции в конечных полях, теории алгоритмов, библиотека длинных чисел MPIR в Visual studio и компьютерного моделирования.

Основные положения, выносимые на защиту:

1. Разработка эффективного программного обеспечения для задачи вычисления наибольшего общего делителя пар длинных натуральных чисел;

2. Разработка компьютерной системы тестирования для различных алгоритмов вычисления наибольшего общего делителя;

3. Разработка эффективных реализаций fc-арного алгоритма Соренсона с ускорением базового алгоритма до двух раз;

4. Разработка эффективных реализаций аппроксимирующего алгоритма Ишмухаметова с ускорением базового алгоритма до пяти раз;

5. Разработка программного комплекса для поиска строго псевдопростых чисел с использование аппроксимирующего алгоритма;

Достоверность. Степень достоверности полученных в работе результатов обеспечивается строгостью постановки задач и математических методов их решения, а также экспериментальный системный подход к построению программного комплекса, экспериментально подтверждающего теоретические оценки.

Соответствие паспорту специальности. Работа выполнена в рамках направления области исследований «Модели, методы и алгоритмы проектирования и анализа программ и программных систем, их эквивалентных преобразований, верификации и тестирования» паспорта специальности 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

Апробация результатов работы. Основные результаты работы докладывались на конференциях:

1. Международная конференция по алгебре, анализу и геометрии КФУ, Казань, июнь-июль 2016;

2. Итоговая научная конференция Казанского федерального университета (КФУ) за 2016 год, Казань, январь 2017;

3. Международная научная конференция, Scientific research of the SCO countries: Synergy and Integration Пекин, Китай, июнь 2018;

4. XXVII Международная научно-практическая конференция «Вопросы современных научных исследований», Научный центр «Орка», Омск, июль 2018;

5. VII Международная конференция "Последние тенденции в области науки и технологий управления" Лондон, Великобритания, июль 2018;

6. XXIX Международная научно-практическая конференция «Вопросы современных научных исследований», Научный центр «Орка», Омск, август 2018;

7. Международная конференция, International Conference on Innovations in Engineering, Technology and Sciences (ICIETS-2018), Karnataka, India, сентябрь 2018;

8. Международная научно-практическая конференция "Математическое моделирование, программирование и прикладная математика", Великий Новгород, июнь 2019;

9. Международная математическая конференция стран БРИКС, The 3rd BRICS Mathematics Conference, Иннополис, июль 2019;

10. XXII Международный научно-исследовательский конкурс «Лучшая научно-исследовательская работа 2019», МЦНС «Наука и Просвещение», Пенза, октябрь 2019;

11. II Международная конференция «Передовые технологии в аэрокосмической отрасли, машиностроении и автоматизации - MIST-2019», Красноярск, ноябрь 2019;

Личный вклад. Автор принимал активное участие в теоретических разработках и анализе предложенных методик, разработал и реализовал программный комплекс, необходимый для получения статистических численных оценок, выполнил цикл экспериментальных вычислений процедуры вычисления НОД с использованием трех алгоритмов, выполнил анализ полученных данных, разработал методику ускорения вычисления НОД для fc-арного алгоритма Соренсона на основе сдвигов области выбора параметров, доказал практическую эффективность применения fc-арного алгоритма Соренсона и ап-

проксимирующего алгоритма в сложных вычислительных задачах теории чисел и криптографии, использующих процедуру вычисления НОД.

Публикации. Основные результаты по теме диссертации изложены в 11 печатных изданиях, 5 из которых изданы в журналах, рекомендованных ВАК, 6 в прочих изданиях.

Объем и структура работы. Диссертация состоит из введения, трёх глав, заключения и приложения. Полный объём диссертации составляет 124 страницы, включая 14 рисунков и 29 таблиц. Список литературы содержит 131 наименование.

Во введении обосновывается актуальность исследований, проводимых в рамках данной диссертационной работы, приводится обзор научной литературы по изучаемой проблеме, формулируется цель, ставятся задачи работы, сформулированы научная новизна и практическая значимость представляемой работы.

Первая глава посвящена обзору основных алгоритмов вычисления наибольшего общего делителя (НОД) натуральных чисел. Самым древним из которых является классический алгоритм Евклида (КАЕ). Этот алгоритм имеет многочисленное применение в теории чисел и криптографии и остается одним из самых эффективных алгоритмов вычисления НОД. Рассматривается его расширенная версия (РАЕ), которая используется во многих криптографических и теоретико-числовых алгоритмах, поэтому оценка его производительности играет важную роль в расчетах эффективности криптографических алгоритмов. В первой главе еще рассматривается бинарный алгоритм вычисления НОД, который вычисляет НОД двух натуральных чисел, используя более простые арифметические операции, чем КАЕ. Он заменяет деление на арифметические сдвиги, сравнения и вычитание. Еще рассмотрены парный алгоритм Евклида, который был разработан Д. Соренсоном в 1990 году и аппроксимирующий ^-арпый алгоритм (новая версия ^-арного алгоритма вычисления НОД натуральных чисел, которая была разработана Ш. Ишмухаметовым в 2016 году).

Во второй главе подробно рассмотрен базовый парный метод вычисления НОД натуральных чисел и методы его ускорения. Был разработан программный комплекс по которому были проведены разные экспериментальные вычисления и сравнительный анализ результатов итерации и времени выполнения. Мы исследовали значения коэффициента редукции в зависимости от к и поиск подходящей пары (х,у) в парном алгоритме. Представлены ме-

тоды ускорения процедуры поиска пары (х,у) и проведены экспериментальные данные по времени вычисления НОД при использовании предтаблиц обратных элементов и значений х и у. Были получены экспериментальные результаты времени при сдвиге области значений у. Еще был рассмотрен смешанный алгоритм на основе fc-арного алгоритма и схемы Евклида. В конце второй главы проведены выводы по полученным результатам.

В третьей главе мы подробно исследовали аппроксимирующий fc-арный алгоритм вычисления НОД и его эффективную реализацию на языке программирования С • • в среде программирования Visual Studio с установленной библиотекой длинных чисел MPIR. Приведены теоретические расчеты. Проведены оценки производительности вычисления НОД для пар чисел различной длины по числу итераций и времени работы. Исследованы методы ускорения аппроксимирующего алгоритма и проведены разные оценки времени вычисления. Были реализованы приложения этого алгоритма такие, как тест простоты Миллера-Рабина и поиск строго псевдопростых чисел по которым были проведены экспериментальные результаты. Также в конце третьей главы проведены выводы по полученным результатам.

В приложении представлены коды нашего программного комплекса (главная часть программы и библиотека функций ) на языке программирования С • • в среде программирования Visual Studio с установленной библиотекой длинных чисел MPIR.

Глава 1. Обзор алгоритмов вычисления наибольшего общего делителя (НОД) натуральных чисел и оценки их сложности

По основной теореме алгебры каждое целое натуральное число предста-вимо в виде произведения простых сомножителей и их степеней, причем такое разложение единственно с точностью до перестановки сомножителей. Если число А делится без остатка на число d, то d- делитель А (обозначается di А).

Пусть даны натуральные числа Д В и d. Если di А и то d назывыается общим делителем чисел А и В. Наибольший среди всех положительных делителей А и В называется наибольшим общим делителем (кратко, d =НОД(А, В)).

Простым называется целое число, больше единицы, единственными множителями которого являются 1 и оно само. Существует бесконечно много простых чисел. Криптография часто использует большие простые числа (длины 512 бит и больше) см. [40; 41]. Подробный справочник по простым числам есть у Паулы Рибенбойм (Paula Ribenboim) [42; 43].

Два числа являются взаимно простыми, если их общий множитель равен 1. Другими словами, если НОД а и п равен 1 (НОД(а,п)=1). Взаимно просты числа 14 и 27. 15 и 21 не являются взаимно простыми, а 11 и 400 - являются. Простое число взаимно просто со всеми другими числами, кроме чисел кратных данному простому числу [44]. Для подробного математического изложения теории чисел см. [45 48]

1.1 Классический алгоритм Евклида

Задача вычисления наибольшего общего делителя натуральных чисел является одной из наиболее важных и используемых в математике и криптографии. Алгоритмы для вычисления НОД насчитывают не одно тысячелетие. Одним из первых способов вычисления НОД двух натуральных чисел описан древнегреческим математиком Евклидом в его книге "Началанаписанной в 300-м году до нашей эры. Евклид не был изобретателем этого алгоритма. Историки считают, что этот алгоритм старше на 200 лет, этот самый древный алгоритм, который дошел до нашего времени, и он по-прежнему остается одним

из самых эффективных алгоритмов вычисления НОД. Дональд Кнут описал этот алгоритм и его современные модификации в своем монументальной монографии [49]. Этот алгоритм можно обобщить для нахождения НОД массива из п натуральных чисел [50] и для вычисления НОД полиномов над различными полями.

Алгоритм Евклида имеет многочисленное применение в теории чисел и криптографии [51]. Приведем некоторые примеры. В теории чисел:

— Его расширенная версия используется для нахождения обратных элементов в конечных полях [52; 53].

— Алгоритм используется при решении линейных диофантовых уравнений. Частный случай линейного диофантового уравнения это соотношение Везу (см. [54;55]).

НОД(ДВ ) = хА + уВ,

которое легко решается при помощи расширенной версии алгоритма [56].

— При помощи алгоритма можно представить любое вещественное число в виде непрерывной(цепной) дроби, если это число рационально [57].

А 1

~в = + —;—~ = № ; ^ь ... ; qn\ в qi + ^

Чп

где Qi - значение A div В па ¿-ой итерации алгоритма Евклида, при i = 0 .. .п.

— Также при помощи алгоритма можно определить являются ли два числа взаимно простыми, то есть не имеют никаких общих делителей, кроме 1.

В криптографии:

— Алгоритм используется для генерации открытого и секретного ключей в методе шифрования RSA.

— Используется для генерации параметров точек на эллиптических кривых и вычисления их кратного [58; 59].

— Одним из наиболее перспективных направлений, в которых быстрые алгоритмы НОД играют важную роль, является поиск сильных псевдопростых целых чисел, что улучшает эффективность тестов простоты для криптографии [60; 61].

Классический алгоритм Евклида, обозначаемый через КАЕ, вычисляет наибольший общий делитель НОД (the greatest common divisor GCD) для пар натуральных чисел (А, В). Будем предполагать, что всегда выполнено неравенство А ^ В > 0.

Схема вычисления НОД основана на рекуррентном соотношении

GCD(A, В) = GCD(B, A mod В),

которое используется многократно до тех пор, пока второе число не окажется равным 0, тогда первый аргумент пары равен искомому НОД. Приведем пример работы алгоритма.

пример. Пусть даны А = 1793, В = 753.

Результат работы алгоритма представим ниже в таблице (1.1):

Таблица 1.1 Вычисление НОД с помощью КАЕ._

i A В A mod В [А/В ]

1 1793 753 287 2

2 753 287 179 2

3 287 179 108 1

4 179 108 71 1

5 108 71 37 1

6 71 37 34 1

7 37 34 3 1

8 34 3 1 И

9 3 1 0 3

Ответ: НОД(1793,753) = 1.

В последнем столбце находятся значения целой части от деление А на В, они понадобятся нам в следующем примере.

Реализация классической версии алгоритма Евклида на языке программирования С • • выглядит следующим образом:

int ClassicalEuclid(intA, intB) { int С; if(В == 0) return A; while(B > 0) {

С = А °/„ В; А = В; В = С; }

return А;

}

Среднее чиело итераций алгоритма Евклида для двух случайных равномерно распределенных чисел (А,В) длины n-бит, равно примерно 2log2 п (см. [62]). Другие модификации алгоритма Евклида, такие как бинарный алгоритм и к-арный алгоритм, превосходят по скорости КАЕ в несколько раз. Рассмотрим эти алгоритмы в следующих разделах.

Алгоритм Евклида для п чисел. Для вычисления НОД берем наименьшее ненулевое число из списка п данных чисел. Потом заменяем все остальные числа остатками от деления на это наименьшее ненулевое число. Повторяем эту процедуру до тех пор, пока останется только одно ненулевое число. Это и будет наш искомый НОД.

Пример. НОД(850,1310, 2525,1630) = НОД(850,460,825, 780) = НОД(390,460, 365,320) = Н0Д(70,140,45, 320) = НОД(25,5,45, 5) = Н0Д(0,5,0,0) = 5,

Ответ: Н0Д(850,1310, 2525,1630) = 5.

1.1.1 Расширенный алгоритм Евклида

Расширенный алгоритм Евклида (РАЕ) используется во многих криптографических и теоретико числовых алгоритмах. Он состоит из двух частей. В первой части алгоритма для заданных целых чисел А и В вычисляется их наибольший общий делитель d. Вычисление НОД натуральных чисел А и В выполняется по рекуррентной формуле:

ПОД(А,В) = НОД(В,А mod В).

Во второй части работы алгоритма выполняется решение уравнений вида Ах + By = d, оде А, В - заданные числа, a, d их наибольший общий делитель, найденный в первой части РАЕ.

Для этого к таблице вычисления НОД (ем. Table 1) добавляются два новых столбца, озаглавленных х и у. Поместим в последнюю строчку столбцов х и у значения 0 и 1. Затем, считая значения Xi+1,yi+1 известными, последовательно вычисляем значения ^ и yi, i ^ 0, по формулам:

хг = уг+1, уг = хг+1 - уг+1 • (A div В)г

Пример 1. Решить уравнение 76х+27у = 1. Как показано в таблице (1.2), помещаем в первую строчку значения А = 76, В = 27. Вычисляем A mod В - остаток от деления А па В, и A div В - целую часть от деления А и& В. Потом переносим значения В и A mod В па строчку вниз и па одну клетку влево. Повторяем вычисления во второй строке. Продолжаем вычисления, пока значение в столбце A mod В не станет равным 0. Тогда заносим в последнюю строчку столбцов х ж у значения 0 и 1, и ведем вычисление снизу вверх по формулам, описанным выше.

Таблица 1.2 Решение уравнения с помощью расширенного алгоритма Евклида.

i А В A mod В [А/В ] X У

1 76 27 22 2 -11 31

2 27 22 5 1 9 -11

3 22 5 2 4 -2 9

4 5 2 1 2 1 -2

5 2 1 0 2 0 1

Ответ: НОД(76, 27) = 1 - последнее значение в столбце В. Пар а (х,у) = (-11,31), дающая решение уравнению 76х + 27у = 1, берется из первой строки таблицы.

Расширенный алгоритм Евклида также используется для нахождения обратных элементов в конечных полях, приведем следующий пример.

Пример 2. Найти обратный элемент для е = 7 по составному модулю п = 32.

Запускаем расширенный алгоритм Евклида, возьмем А = 32 и В = 7. получим в таблице (1.3):

Таблица 1.3 Вычисление обратного элемента с помощью расширенного алгоритма Евклида.

i А В A mod В [А/В ] X У

1 32 7 4 4 2 -9

2 7 4 3 1 -1 2

3 4 3 1 1 1 -1

4 3 1 0 3 0 1

Значение у = —9, находящееся в верхней строке, и есть искомое значение обратного элемента = у mod 32 = —9 mod 32 = 23.

Реализация расширенного алгоритма Евклида на языке программирования С • • выглядит следующим образом:

void ExtEuclid (long A, long В, long &х , long &у) { int i=l; long AB [100], C=A, t; while (C>0) { C=A°/„B;

AB [i]= A/B; i++; A=B; B=C;

}

i--;i--; x=0 ; y=l; while (i>0) {

t=y; y= x-y* AB[i]; x=t; i~;

}

return;

1.1.2 Оценка производительности алгоритма Евклида

Расширенный алгоритм Евклида используется во многих криптографических методах, поэтому оценка его производительности играет важную роль в расчетах эффективности криптографических алгоритмов.

Основным фактором в оценке РАЕ является число итераций в главном цикле вычисления новой пары (А; В), или, другими словами, число строчек в таблице вычисления. Пусть Ь - бинарная длина аргуметов пары (А; В). Для оценки числа итераций заметим, что на шаге к произвольной итерации возможны два случая:

Случай 1. В < А/2. На шаге к+1 новое значение А, равное предыдущему В , будет меньше, чем А/2.

Случай 2. В ^ А/2. Остаток г = А той В = А — В будет меньше А/2, и на шаге к + 2 новое значе ние А станет равным остатку г < А/2.

В любом случае, после каждой пары итераций первый аргумент А уменьшается более, чем в 2 раза, значит, общее число итераций не может быть больше, чем 2Ь. Число операций па каждой итерации постоянно (как при прямом ходе, так и при подъеме при вычислении коэффициентов уравнения Ах + Ву = и состоит из одной операции деления с остатком при прямом ходе алгоритма, и одной операции умножения при обратном ходе алгоритма (операции переприсваивания, сложения и вычитания не учитываем). Эти операции в наилучшем алгоритме занимают время 0(Ь Ь), поэтому общая оценка КАЕ и РАЕ составляет значение 0(Ь2 V).

Эта оценка не является завышенной, т.к. существует последовательность чисел Фибоначчи, на парах соседних элементов которых и достигается эта

Список литературы диссертационного исследования кандидат наук Амер Исмаил Ф. О., 2020 год

- - - - - -

В 793 396 198

Подставим наши значения в выражение для С:

1,873

С -

Ах + By - В

к

(г — q)x ~к~

+ s

- В

(1,873 — 5)х 16

+ s

- В| — 0,195х + s\.

Следующая задача - найти правильную дробь т/п, аппроксимирующую а = 0,195.

а

дробей Фарея аппроксимируем интервал (0; 1). Начальная последовательность строится следующим образом (рассмотрим для к = 16):

11 0 < 15 < 14 <

Перебором определим, что

112 3

< 3 < 2 < 2 < 3 <

а =0,195 G (i;1) 65

14

< 15 < 1

Построим медиану дробей 1/6 и 1/5, складывая числитель и знаменатель:

™ = 1+1 = 1. * 0,182. п 6 + 5 11 '

Медиана делит интервал [1/6; 1/5] на две половины. Проверим, в какой половине находится значение а = 0,195. Число а = 0,195 попадает в интервал [2/11; 1/5]

имеет знаменатель равный сумме знаменателей 5 + 11 = 16 > к — 1. а

жение

т 1

а « — = -п 5

с точностью £ = 1/5 — 0,182 = 0,018.

тогда определим х равным знаменателю этой дроби х = 5. Получим,

1С | « В 1 — ах + s | = В

1

—- • 5 + е + s 5

= В | —1 + е + s |

Определим значение в равным 1. Тогда, С ~ В • 0,082. Для точного вычисления С найдем у = —дх + вк = —5 • 5 + 16 = —9. Тогда

С =

Ах + Ву 1485 • 5 + 793 • (—9) 288

к 16 16

= 18.

Поскольку С - четно, сократим его па 2, после чего получим финальное значение С = 9. Коэффицепт редукции р = В/С = 793/9 превысил значение 88, что значительно превышает соответствующую редукцию в стандартном парном алгоритме.

Реализация аппроксимирующего ^-арного алгоритма па языке программирования С • • выглядит следующим образом:

long ApproxKaryQong A,long B,long k,long m, longfe C){ // m=sqrt(k) long u,v,a=A,b=B,d,q,k2=k*k,mm,nn,s1=0,x,у ; q=(A*inv(B7„k,k))7„k; // q=AB"{-l> mod к while(b>k2){

b»=l;a»=l;

}

fprintf (Ans,"A/B=7„d/7„d <=> a/b=e/,d/e/.d\nM, A,B,a,b);

if(a-b*q<0)q-=k;

u=a-b*q; v=b*k;

if(u>v){sl=u/v; u-=sl*v;>

Findmn(u, v, k,mm, nn);

fprintf (Ans , "u/v=7od/7od <=> m/n=7od/7od\n" , u,v,mm,nn); x=nn;y=-q*x-sl*x-mm*k; C=(x*A+y*B)/k; if(C<0)C=-C;

fprintf (Ans," C= I (xA+yB) /к I = I (e/,d*e/,d e/,d*e/,d)/e/,d|=e/,d\n", x,A,y,B,k,C); return C;

void FindmnQong b, long a, long k,long& m, longfe n){ // Поиск дроби Фарея m/n для заданной правильной дроби Ь/а long i=2,tl,t2,ml,nl,m2,n2,mm,nn; if (2*b==a){m=l;n=2;return;} if (2*b<a){

while(a>i*b&&i<k)i++; ml=l;nl=i;m2=l;n2=i-l;} else{while(b*i>a*(i-l)&&i<k)i++; ml=i-2;nl=i-l;m2=nl;n2=i;} while(nl+n2+l-k<=0){ // деление возможно mm=ml+m2;nn=nl+n2; if(b*nn<=a*mm){ m2=mm;n2=nn;} else { ml=mm;nl=nn;}

}

tI=ml*n2+m2*nl; t2=nl*n2;

if(tl<t2) // Случай b/a ближе к левому краю {m=ml;n=nl;return;}

else

{m=m2;n=n2;return;}// Случай m/n ближе к правому краю

}

В статье [96], Еникееьом была исследована задача нахождения наилучшего приближения вещественного числа несократимой дробью, знаменатель которой не превосходит заданного значения п для нахождения самого быстрого метода аппроксимации, что позволит ускорить сходимость аппроксимирующего fc-арного алгоритма. Рассмотрена также аппроксимация цепными дробями и разработан метод, который использует их и предвычисленные начальные шаги, полученные с помощью рядов Фарея. В результате Еникеева показано, что приближение с помощью рядов Фарея и предвычислением показывает лучшее время, а среди алгоритмов, не использующих дополнительную память, метод, основанный на цепных дробях.

Глава 2. Программирование к-арного метода вычисления НОД

натуральных чисел

В этой главе мы обсудим проблему эффективного программирования fc-арного алгоритма вычисления НОД двух или более целых чисел и предложим ряд модификаций, ускоряющих выполнение алгоритма [97 100].

k-арный алгоритм Евклида был разработан в 1990 году Дж.Соренсоном ( [33; 34]) и улучшен независимо друг от друга Вебером [36] и Джебелеаном [37] в 1993 и 1995 годах. Этот алгоритм является естественным обобщением бинарного алгоритма. Основная идея алгоритма состоит в том, чтобы искать па шаге вычисления искать линейную комбинацию Ах + By заданных чисел А и В такую, что выполняется соотношение

Ах + By = 0 mod к, (2.1)

где к - заранее выбранный и фиксированный параметр алгоритма.

В простейшем случае значение к равно 2, и тогда алгоритм совпадает с бинарным. Значение к может быть выбрано любым положительным целым числом. Первые исследователи этого метода (Дж. Соренсон, Т. Джебелеан, К. Вебер) рассматривали разные значения этого параметра (например, Соренсон предложил выбрать к равным степени большого простого числа), однако, никаких преимуществ выбор к простым, составным или степенью простого числа не давал, поэтому наилучшим вариантом стали считать значение к равным степени двойки (Вебер [36]). Это позволило ускорить выполнение рутинных операциях на шагах алгоритма, поскольку деление на степень двойки означало просто сдвиг числа вправо.

Итак, пусть к - четная степень двойки, например, к = 2Ш, и А ^ В > 0 - нечетные целые числа. В главе 1 была сформулирована и доказана основная теорема Соренсона, служащая базисом fc-арпого алгоритма:

Теорема 2.1. (Дснс. Соренсон [1990]). Пусть т > 1 - фиксированное натуральное число, к = т2. Для любых целых чисел А и В, А ^ В > 07 взаимно простых с т, существуют ненулевые х, у, \х\, \у\ ^ т такие, что выполняется, соотношение (2.1).

Следуя теореме Соренсона, на шаге алгоритма для фиксированного к и заданных нечетных А и В вычисляются коэффициенты х,у7 удовлетворяющие теореме, и вычисляется С = (Ах + Ву)/к. Далее вычисляется ё, =НОД(С, т), и если он не равен 1, то выполняется сокращение С на пока С не станет взаимно простым с т. В завершении итерации пара (А,В) заменяется парой (В,С), которая имеет меньший размер по сравнению с исходной парой.

Назовем отношение большего числа к меньшему в паре (А; В) на шаге алгоритма коэффициентом редукции и обозначим символом р = А/В. Чем больше среднее значение этого коэффициента, тем быстрее сходится алгоритм.

Согласно теореме Соренсона:

А _ Ак Ак _ л/к С = Ах + Ву ^ 2А/к = "2"'

откуда

р = ^/А/С ^ 0,707к1/4.

2

Таким образом, что при увеличении к в 16 раза, нижняя граница для р увеличивается в два раза.

Значение к можно брать большим, оставаясь в размере одного машинного слова (до 264), однако экспериментальные вычисления, которые мы приведем в этой главе, показывают, что скорость алгоритма оптимальна при значениях к от к = 1024 до к = 4096. При дальнейшем увеличении к поиск подходящей пары (х,у) и выполнение промежуточных вычислений выполняется дольше, что замедляет выполнение алгоритма в целом.

Кроме того, поскольку НОД вычисленный в парном алгоритме не обязательно равен исходному НОД(А, В) = ^о, а является его кратным. Поэтому после завершения процедуры вычисления НОД с помощью ^-арного алгоритма и получения его ответа необходимо выполнить дополнительное вычисление, используя алгоритм Евклида

¿о = ССО(А; ССО(В4)),

получая правильное значение НОД.

Дополнительные множители, входящие в ответ к-арного алгоритма, называются посторонними множителями. Их размер также растет с увеличение к. Это также замедляет общую процедуру ^-арного алгоритма.

2.1 Методика экспериментальных вычислений

Для исследования сходимости fc-арного алгоритма Соренсона и разработки методов его ускорения нами была разработана система вычислений, реализованная на языке С • • в среде Microsoft Visual Studio 2012. Поскольку эта среда не поддерживает формат длинных чисел, была подключена библиотека длинных чисел для С • • MPIR. Для реализации различных вариаций fc-арного алгоритма весь алгоритм был разбит на отдельные составляющие и было разработано несколько различных процедур, реализующих каждую составляющую часть общего алгоритма. Эти процедуры будут описаны ниже в соответствующих разделах. Запуск процедур выполнялся с различными значениями исходных параметров, главным из которых являлся параметр к.

Контрольными параметрами, которые имеют значения для сходимости fc-арного алгоритма, являются время и количество итераций. В разработанном экспериментальном комплексе фиксировались эти параметры и выполнялось сравнение различных реализаций и вычислений с различными значениями исходных параметров по этим итоговым значениям.

Одним из важных параметров вычисления является длина исходных чисел. Мы брали пары исходных чисел различной длины от 100 до 1000 десятиричных разрядов (примерно, от 320 до 3200 бит). Эти значения укладываются в рамки длин параметров криптографических алгоритмов и протоколов, в которых наши исследования могут найти приложения. Например, алгоритмы типа RSA, ElGamal, DSS и другие работают с числами порядка 150-380 бит для эллиптической криптографии [101 105] и 1024-2048 бит для алгоритмов, основанных на проблеме факторизации длинных чисел и вычислении дискретного логарифма [106 108].

Вычисление НОД для пар такой длины выполняется слишком быстро для единичного вычисления по любого из рассмотренных алгоритмов, поэтому мы вычисляли НОД для серии из 50 и 100 пар натуральных чисел, заранее скомпонованных и занесенных в массивы. Поэтому в приводимых ниже графиках и таблицах приводится суммарное время вычисления для выбранного числа пар. Число итераций мы также суммировали и усредняли по числу вычислений, приводя среднее значение.

Для большей точности финальные вычисления по каждой группе вычислений мы повторяли подряд по 10 серий и вычисляли более точный усредненный результат по набору из 10 серий по 50 или 100 пар. Это позволило добиться достаточного точного измерения среднего времени испытаний и числа итераций независимо от конкретной работы компьютера.

Мы не ставили целью исследовать ускорения путем параллельных вычислений на нескольких потоках, используя мультипроцессорные системы, хотя в одной из наших статей мы обсуждаем возможности распараллеливания алгоритмов вычисления НОД. В этом плане распараллеливание более перспективно для аппроксимирующего к-арного алгоритма [109-112], описанного в следующей главе.

2.2 Исследование значений коэффициента редукции в зависимости

от к

Выполним анализ средних значений коэффициента редукции р = А/В в парном алгоритме в зависимости от значений параметра к.

Согласно теореме Соренсона значение А/С ограничено снизу величиной к1/2/2. Поэтому усредненного то двум итерациям значение А/В ограничено снизу квадратным корнем из этого значения

к1/4

А/В ^

/2 ,

который при изменении к от 16 до 216 = 65536 изменяется от \[2 до 8\/2 « 11,32. Выполним контрольные измерения числа итераций ^-арного алгоритма для различных значений к, усредняя значения среди 50 пар длины 100 десятичных разрядов (примерно 3200 бит). Поместим в таблицу также среднее число итераций для тех же пар по алгоритму Евклида.

По результатам экспериментов вычислим среднее значение коэффициента редукции р = А/В. Последний столбец таблицы показывает минимальное значение коэффициента редукции согласно теореме Соренсона.

Таблица 2.1 — Число итераций алгоритма Евклида и к-алгоритма для различных к.

Параметр к Число итераций Коэффициент редукции Р

Euclidean 1942 3,27

16 1358 5,43 1,4

64 1061 8,74 2

256 888 13,3 2,8

1024 760 20,6 4

4096 672 30,6 5,6

16384 600 46,0 8

65536 573 55,2 11,2

Из этой таблицы видно, что среднее значение коэффициента редукции превышает минимальное значение, обеспечиваемое теоремой Соренсона, примерно в 5 раз для всех рассмотренных значений к.

2.3 Поиск подходящей пары (х,у) в fc-арном алгоритме.

Теорема Соренсона гарантирует существование небольших по модулю значений параметров (х,у)7 но не дает способа их нахождения. Рассмотрим в этом разделе различные методы их поиска.

Обозначим через q - положительное (от 1 до к — 1) значение параметра AB—1 mod к. Из уравнения Ах + By = 0 mod к непосредственно следует соотношение

у = —qx mod к.

Простейшим методом поиска пары (х,у) является перебор значений параметра х от 1 до т и вычисления значения у = —qx mod к до тех пор, пока не будет найдено подходящее у из иптервала — т ^ у ^ т. Для проверки последнего условия следует брать два значения у7 равные —(qx mod к) як — (qx mod к). Программа на языке С для вычисления пары (х,у) может выглядеть следующим образом:

void SearchXY(int А, int В, int m, int q, int &x, int &y) {

int k=m*m;

for(x=l; x<=m; x++){ y=- (q*x °/„ k) ;

if(y+m>=0)return;// Case 0>y>=-m y+=k;

if(y<=m) return;// Case 0<y<=m

}

return;

Пример. A = 1219, В = 583, к = 16 Рассмотрим процедуру вычисления пары (х,у):

1. Сначала найдем а = A mod к = 1219 mod 16 = 3 b = В mod к = 583 mod 16 = 7, Ь-1 mod к = 7, q = ab-1 mod к = 5. Далее в цикле по ж будем искать подходящее Y.

2. х = 1,у = -5, у + к = 11. х = 2,у = -10, у + к = 6. х = 3, у = -15, у + к = 1.

Найдена подходящая пара (х,у) = (3; 1).

3. Вычислим теперь С = (Ах + By)/к = (1219 • 3 + 583 • 1)/16 = 265.

Отметим на будущее, что выбранный вариант не является наилучшим. Например, первый вариант дает меньшее значение С:

С = КАх + Ву)/к\ = (1219 • 1 + 583 • (-5))/16 = 106.

После сокращения на 2 получим окончательное значение С = 53, что гораздо лучше вычисленного ранее С = 265. Дело в том, что если х и у имеют противоположный знак, то слагаемые суммы Ах + By взаимно сокращаются, и линейная комбинация приобретает меньшее по модулю значение. Такое наблюдение не рассматривалось ранее основателем алгоритма Соренсоном или другими исследователями, кроме Ш.Т. Ишмухаметова, который использовал идею выбора наилучшего соотношения между значения слагаемыми Ах и By в основу аппроксимирующего fc-арного алгоритма.

Отметим также, что сама процедура поиска пары (х,у) перебором неэффективна, и имеет оценку 0(1од2к). Ее ускорение способно дать значительный

выигрыш при программной реализации ^-арного алгоритма. Рассмотрим методы ускорения этой процедуры в следующем разделе.

2.4 Методы ускорение процедуры поиска пары (х,у) в парном

алгоритме.

В этом параграфе рассмотрим методы ускорения процедуры поиска пары (х,у). Часть таких способов была предложена самим Соренсоном и его последователями, часть будем предложена в этой работе.Выделим несколько аспектов этой проблемы.

1. Использование предвычислений. Под предвычислениями будем понимать заранее вычисленные значения различных параметров общего алгоритма, которые используются непосредственным обращением к их значениям и не вычисляются повторно.

2. Анализ пар (х,у)7 соответствующих выделенным значения q. Например, для q ^ т = у/к подходящая пара (х,у) всегда имеет значение (х,у) = (1,q).

3. Третье изменение касается изменения области значений параметров х и у в самой базовой теоремы Соренсона. Легко видеть, что набор значений переменных х я у 1 ^ х ^ т, —т ^ у ^ т обеспечивает мощность множества значений пары (х,у), равным 2т2 = 2к. Однако, пример предыдущего параграфа показывает, что данная область значений не всегда обеспечивает наилучшую сходимость.

Нами предложен метод сдвига области значений для переменной у7 обеспечивающий до 25% ускорения алгоритма без увеличения сложности самого алгоритма или отдельных его частей.

Рассмотрим перечисленные варианты ускорение процедуры поиска пары (х,у) по очереди. Сначала рассмотрим ускорение путем использования пред-таблиц.

Первым шагом в процедуре нахождения пары (х,у) является вычислении параметра q = АВ—1 mod к. Как известно, вычисление обратных элементов в конечном поле требует использования расширенного алгоритма Евклида

или соответствующего обратного хода fc-арного алгоритма. Это - затратная процедура, которая может быть сокращена, если заранее составлена таблица обратных элементов по модулю к. Ее полное вычисление выполнится заО(к log2 к) шагов. Для своей работы и хранения результатов алгоритм требует к/2 ячеек памяти, что также критично при больших значениях к. При больших значениях к, сравнимых с размером машинного слова (264) хранение такой большой таблицы в памяти компьютера становится невозможным.

Можно составить таблицы обратных элементов до какого-то приемлимо-го размера, например до к = 216, и вычислять обратные элементы по большим к, используя так называемый «Подъем Гензеля» (Hensel's Lifting [113]). Описание этого алгоритма можно найти в статье Ишмухаметова [54]. Также можно посмотреть [114] и [115].

Другое полезное изменение алгоритма состоит в непосредственном прямом предвычислении пары (х,у). Действительно, значения параметров (х,у) полностью определяются значением q = АВ-1 mod к, которое в свою очередь зависит от значения остатков а = A mod к и b = В mod к. Сопоставляя каждой возможной паре (а,Ь) соответствующее значение (х,у)7 получим таблицу, позволяющую прямо находить подходящие значения (х,у) по последи им т разрядам чисел А и В. Объем такой таблицы составит к2/4 строк, поскольку надо рассмотреть всевозможные пары нечетных значений пар (а,Ь) при 1 ^ а,Ь < к. Одной из важных задач является разработка алгоритма сжатия таблицы пар до приемлимого размера. Возможным решением является первичное (грубое) вычисление подходящей пары (х,у) с использованием таблиц с последующим уточнением обычной процедурой.

2.5 Время вычисления НОД при использовании предтаблиц

обратных элементов

В этом разделе мы рассмотрим экспериментальные данные по времени вычисления НОД без использования предтаблиц обратных элементов и с использованием таких таблиц для разных значений параметра к от к = 16 до к = 216 = 65536 для серии из 50 пар чисел длины 500 десятичных разрядов.

Будет указано общее время вычисления в миллисекундах, поскольку время вычисления НОД для одной пары изменяется долями секунды. Также поместим в эти таблицы значение выигрыша времени в процентах от общего времени.

Таблица 2.2 Ускорение времени с предтаблицами чисел длины 500 разрядов

Параметр к Время(без предтабл.) Время с предтабл. Выигр.в%

16 186 179 3,8

64 143 137 4Д

256 127 118 8,6

1024 112 101 9,8

4096 104 94 9,6

16384 101 91 9,9

65536 109 99 9,2

Экспериментальные вычисления, проведенные в этой серии, позволяют сделать полезные выводы о скорости сходимости ^-арного алгоритма:

1. Процедура вычисления обратных элементов отнимает существенную часть общего времени вычисления НОД (от 3,8 до 9,9 процентов в зависимости от значения параметра к).

2. Выигрыш от использования предтаблиц обратных элементов растет в абсолютном и относительном размере при увеличении к от 16 до 16384. При дальнейшем увеличении к начинается общее ухудшение времени работы алгоритма.

3. Оптимальным значением для выполнения ^-арного алгоритма является значение к = 16384.

Также из таблицы следует, что дальнейшее увеличение значения к приводит к ухудшению общей процедуры, поэтому дальнейшее увеличение значений этого параметра не имеет смысла. Отметим также, что время вычисления НОД по классической схеме Евклида составляет в нашем примере 112 мс. Поэтому только при значениях к от к = 1024 до к = 65536 алгоритм Кагу опережает схему Евклида.

Далее выполним те же расчеты при длине исходных пар А и В, увеличенных до 1000 десятичных разрядов (примерно 3200 бит). Общее время вычисления для 50 пар по схеме Евклида составляет 264 мс.

Таблица 2.3 Оценка времени с предтаблицами чисел длины 1000 разрядов.

Параметр к Время(без предтабл.) Время с предтабл. Выигр.в%

16 610 585 4Д

64 490 460 6,1

256 414 387 6,5

1024 358 334 6,7

4096 332 306 8,0

16384 312 288 7,7

65536 327 297 9,1

Сравнительные характеристики ^-арного алгоритма в этом случае остаются примерно такими же. Относительный выигрыш от применения предтаблиц обратных элементов остается практически неизменным. Однако, общее время работы ^-арного алгоритма не позволяет получить выигрыш по отношению к схеме Евклида.

Данный эксперимент показывает, что в целом, при увеличении длины рассматриваемых чисел парный алгоритм начинает проигрывать алгоритму Евклида. Для прояснения этого вопроса выполним те же вычисления при длине исходных пар Ь =200 десятичных разрядов. Среднее время вычисления по схеме Евклида для 50 пар чисел такой длины составило 34 мс.

Таблица 2.4 Оценка времени с предтаблицами чисел длины 200 разрядов.

Параметр к Время(без предтабл.) Время с предтабл. Выигр.в%

16 50 45 10

64 40 35 12,5

256 35 30 14,3

1024 32 26 18,8

4096 31 25 19,3

16384 31 25 19,3

65536 34 29 14,7

Это вычисление подтверждает вывод о том, что для чисел меньшей длины время вычисления по схеме Евклида проигрывает схеме ^-арного алгоритма.

Лучшее время достигается при к = 4096 и выигрыш к-ариого алгоритма составляет 26,5 процентов относительно алгоритма Евклида. Такая длина составляет 460 бит и относится к младшим значениям параметров простых чисел, используемых в RSA (в этом алгоритме стандартная длина открытого ключа составляет 1024 или 2048 бит, а открытый ключ п = pq - это произведение двух простых чисел размерности около 512 бит).

Рассмотрим далее возможность ускорения поиска пары (х,у) для специальных случаев значений переменной q = ab-1 mod к.

2.6 Анализ значений выбор способа перебора пар (х,у)

Как мы видим ранее, значения х и у в стандартном к-арпом алгоритме зависят от значений q G [1; к) и наоборот. Для каждого х есть список воз-

можных q и у, соответствующих х. Списки, соответствующие разным х, могут пересекаться. На самом деле, если (х, у) = (1,1) является решением уравнения Ах + By = 0 mod к, т0 паРа (х, у) = (2, 2) также является решением, поэто-

( х, ) ( х, )

следующую процедуру:

1. Заставим принимать последовательно значения

1, 2,...,у/к,

2. Для каждого х вычисляем у\ = —qх mod к и у2 = у\ + к. Обратите внимание на то, что у\ • у2 < 0.

3. Проверим, выполняется ли |у^

для г G {1,2}. Если это так. возьмите найденную пару (х, в качестве решения уравнения Ах + By = 0 mod к и завершим вычисление.

х. Мы предполагаем, что к = 2L для четно го L, ^^этому m = \[к = 2L/2 является целым числом.

1. х = 1. Тогда у = —qх = — q ил и у = — q + к. От ^ m получаем 1 ^ q ^ m, или к — m ^ q < к.

2. х = 2. Тогда у = — 2q или у = — 2q + к, и (к — m)/2 < q < (к + m)/2.

3. х = 3. Тогда (к—m)/3 < q < (к+m)/3 или 2(к—m)/3 < q < 2(к+m)/3.

Проиллюстрируем эту процедуру при к = 16. Все возможные значения д принадлежат множеству Уа1(д) = {1,3,5,7,9,11,13,15}. При х = 1, д должен удовлетворять неравенству 1 ^ д ^ 4 или 12 ^ д < 16. Если х = 2, Я ^ [6; 10]. При х = 3, Я = 5 или д = 9. Это завершает процедуру, поскольку все возможные значения д уже найдены. Поэтому при к = 16 и выбранном способе перечисления х от 1 до т последнее возможное значение х = 4 не достигается. Однако такой способ перебора в некоторых случаях дает большее (худшее) значение параметра С = (Ах + Ву)/к, чем значение, полученное для х = 4. Например, при д = 5 и к = 16 возможным решением будут пары (х,у) = (3,1) и (х,у) = (4, — 4) Но во втором случае, решение С имеет меньшее по абсолютной величине значение. Более глубокий анализ позволяет из набора возможных решения выбирать те, для которых соотношение х/у меньше нуля и близко к отношению — В/А^ что обеспечивает лучшее значение параметра С.

Таким образом, получаем важное следствие - результирующая пара(х,у) выбирается неоднозначно. Ее значение зависит от способа перебора области значений переменных х и у. Более того, можно составить рекомендации выбора решения (х,у)7 позволяющие получить меньшие по абсолютной величине значения параметра С.

Предположим теперь, что мы сдвинули множество возможных значений И = [—т; т] перемени ой у влево на 1. Тогда значение у = т невозможно. При к = 16 этот случай соответствует т = 4 и д = 12. В сдвинутом случае пара (х, у) принимает значение (3, —4), и выбор значения С = (ЗА — 4В)/16 лучше, чем исходный С = (А + 4В)/16.

Это замечание показывает выгоды операции сдвига. Последняя проблема состоит в том, чтобы найти оптимальное на которое должно быть сдвинуто множество И. Ясно, что это £ зависит от длины чисел А, В и значения к. Наилучший случай для пары (х, у) достигается в паре (х,у\ когда Ах ~ —Ву. Поэтому отношение х/\у| обратно пропорционально А/В.

Однако, экспериментальные вычисления, выполненные с анализом значений д, хотя и не ухудшают общего времени вычисления, но и не дают существенного выигрыша. Мы смогли уменьшить время вычисления для пар, длины равной 500 десятичных разрядов на 1-2 миллисекунды при оптимальных значениях к = 16384 и к = 65536, что не дает существенного выигрыша, поэтому в дальней рассматриваться не будет.

( х, )

х/ — B/ А

дальнейшем более подробно. На текущем этапе ограничимся таким способом

( х, )

знаков, дающие меньшие значения линейной комбинации |А х + By появлялись раньше в процедуре перебора. Поскольку на каждом шаге выполнять деление А/ B

( х, )

Ах ~ —By. Как уже было отмечено выше в разделе 2.2 среднее значение коэффициента редукции р = А/B зависит от значений параметра к и изменяется

к

В следующем разделе рассмотрим ускорение, полученное при использовании предтаблицы готовых пар х и у для заданных значений а = А mod к = B mod

х

а

Отметим, что множество всевозможных нечетных пар (а,6), ограниченных значением к, равно к2/4, что является достаточно большим числом даже для к = 1024. Поэтому выполним вычисление таких пар только для значений к от 16 до 1024.

Для этого определим два целочисленных массива Хк и Ук размером 5122 = 262144, куда занесем значения пар (х,у), вычисленных для каждой ( а, )

г = (а - 1)/2, ] = (Ь - 1)/2, т = г*к/2 + Хк[т] = х, Ук[т] = у.

Обратное преобразование будет выполняться по формулам

г = (а - 1)/2, ] = (Ь - 1)/2, т = г* к/2 + х = Хк[т], у = Ук[т].

Выполним экспериментальные вычисления времени вычисления без пред-( х, )

Соберем данные в следующую таблицу

Таблица 2.5 — Время вычисления НОД с предтаблицей пар (х,у).

Параметр к Время(без предтабл.) Время с предтабл. Выигр.в%

16 186 170 8,6

64 143 131 8,3

256 127 112 11,8

1024 112 94 16,7

4096 109 85 22,0

Таким образом, при к = 4096 удалось достигнуть наилучшего времени сходимости 85 миллисекунд, получив 24-х процентное ускорение по отношению к классическому алгоритму Евклида. Однако, в целом такое ускорение не слишком эффективно для ^-арного алгоритма, поэтому попробуем также использовать метод сдвига.

2.8 Сдвиг интервала значений у

Как было замечено ранее, значение линейной комбинации 1Ах + Ву1 становится меньше, если коэффициенты х и у имеют противоположный знак. Это позволило выполнить ускорение ^-арного алгоритма Соренсона простым изменением области значения параметра у в отрицательную область. Проанализируем условие теоремы Соренсона. Мы видим, что значение С = 1(Ах + Ву)Цк будет меньше, когда у < 0, поскольку добавки Ах и Ву имеют противоположные знаки и уменьшают друг друга. Параметры (х,у) распределяются равномерно в выбранной области, поэтому случай у < 0 встречается в среднем в половине всех вычислений. Наша идея состоит в том, чтобы увеличить порцию случаев у < 0 в вычислении пары (х,у).

Отметим, что по теореме 1 значения переменной х ограничены множеством а у изменяется в интервале И = [—у/к;у/к\. Фактически, мы можем заменить множество И на множество ^ = [—у/к — Ь;\/к — {] при Ь > 0, сохраняя верным заключение теоремы. Слишком большое значение сдвига £ может привести к ухудшению скорости общей работы алгоритма, так как слагаемое | Ву | станет чаще превалировать над слагаемым |Аж|. Вычислим оптимальное значение экспериментальным путем.

заставляем t принимать последующие значения 0,1, 2, • • •. Обратите внимание, что случай t = 0 соответствует обычной реализации к-арного алгоритма.

к а =

А mod , = B mod к к к

р = А/ B

с экспериментальными результатами таблицы 2.1. Однако, разброс значений р

( х, )

р

точный расчет становится или неточным или слишком громоздким. Поэтому в этом параграфе мы будем использовать простой сдвиг области значение [—m,m] влево на t единиц при увеличивающихся значениях t с целью нахож-

к

параметра t. Начнем вычисление с к = 16. 2.9 Экспериментальные результаты времени при сдвиге области

( х, )

к-арного алгоритма была спроектирована и реализована модель тестовых испы-

а) Первая серия опытов состоит из вычисления общего времени вычисления НОД для 50 пар нечетных чисел длины 500 десятичных разрядов со сдвигом области значений переменной у на £ единиц влево, то есть - в - £ ^ у ^ 5 - t,

= л/к. ( х, )

использование предтаблиц обратных элементов по модулю к.

Таблица 2.6 Время вычисления НОД с предтаблицей пар (х,у).

Параметр 1 = гв Время Выигр.в%

0 176 0%

1 167 5,1%

2 158 10,2%

3 154 12,5%

4 163 7,4%

5 165 6,25%

6 168 4,5%

7 174 1.1%

8 175 0,6%

Таким образом, при к = 16 оптимальным сдвигом исходного интервала для у [-4; 4] явилось значение £ = 3, переводящее этот интервал в новый интервал [-7; 1], почти полностью сдвинутый в отрицательную область. Дальнейшее увеличение £ приводит к ухудшению общего времени вычисления и является нецелесообразным. Отметим еще, что единственное положительное значение у = 1 при £ = 3 при увеличении х почти не оказывает влияния на значение линейной комбинации 1Ах + Ву |, поскольку при к = 16 в среди ем А > 5В7 и слагаемое Ах значительно превосходит 1ВуУ

б) Вторая серия повторяет предыдущую серию, но при к = 64: Будем измерять время вычисления НОД при £ = 2г,г = 0,1,2,....

Таблица 2.7 Время вычисления НОД с предтаблицей пар (х,у).

Параметр 1 = гв Время Выигр.в%

0 134 0%

2 132 1,5%

3 131 2,2%

4 130 3,0%

5 128 4,5%

6 131 2,2%

8 134 0%

Мы видим, что сдвиг интервала, используемый при к = 64, позволяет сократить время вычислений с 134 миллисекунды до 128 миллисекунд, экономя около 4,5 процентов полного времени. Оптимальное значение наблюдается при £ = 5 в области для у € [—13; 3].

Таким образом, метод сдвига интервалов является более эффективным при меньших значениях к. При дальнейшем увеличении к эффект от сдвига уменьшается до 0, поэтому выполнение дальнейших экспериментов при& ^ 256 - нецелесообразно. Этот феномен - легко объясним. При больших значениях к среднее значение коэффициента редукции р растет и достигает значений 30 и более. При таком растет и достигает значений 30 и более. При таком р сдвиг на сравнительно небольшие значения мало влияет на скорость вычисления. Далее выполним вычисления при больших сдвигах области вычисления.

2.10 Вычисления с большим сдвигом области значений у

В этом параграфе мы приведем экспериментальные данные по изменению общего времени вычисления НОД для пар различной длины при разных к в зависимости от сдвига £ области значений на величину к/2. Как было отмечено в предыдущем разделе такое изменение процедуры вычисления не влияет на ее сложности, но позволяет уменьшить общее время и среднее количество итераций, требуемое для полного вычисления НОД заданных пар чисел. Наблюдение состояло в том, что случай у < 0 более предпочтительно, чем случай у > 0, так как при у < 0 сумм а 1Ах + Ву1 становится меньше, потому чт о добавки Ах и Ву имеют противоположные значения и взаимно уменьшают друг друга. Это вызывает более существенное сокращение пары (В, С), где С = 1(Ах + Ву)/к\ на следующей итерации алгоритма.

Мы реализовали несколько вычислительных экспериментов, меняя параметр Ь = 0 до 2л/к с разными к (см. [116]). Ниже представлены наши новые экспериментальные данные в таблицах (табл. 2.8 и 2.9) и в виде графиков (Рисунки 2.1, 2.2 и 2.3) для серии вычислений из 50 пар чисел длины 1500 десятичных разрядов для оценки числа итераций и времени выполнения ^-арного алгоритма вычисления НОД.

Таблица (2.8) содержит итерации до использования сдвигав и минимальные итерации с использованием разных значений параметра £ сдвига интервала коэффициента у для 50 пар длины 1500 десятичных разрядов при разных к.

Таблица 2.8 Оценка итерации вычисления НОД по парам длины 1500 десятичных разрядов в зависимости от к.

Параметр к Итерация до сдвига £ Минимальная итерация с сдвигом £

16 1351.9 1255.7

256 1012.1 946.8

4096 794 760

65536 657.7 631.7

262144 601.1 583

Мы видим что, число итерации уменьшается с ростом параметра к, и минимальная итерация (оптимум) получается при к = 262144. В следующей таблице (2.9) показано общее время работы к-арного алгоритма для 50 пар длины 1500 десятичных разрядов до и после использования сдвигав.

Таблица 2.9 Оценка скорости вычисления НОД по парам длины 1500 десятичных разрядов в зависимости от к.

Параметр к Время до сдвига £ (те) Минимальное время с сдвигом £ (те)

16 258 229

256 192 174

4096 173 153

65536 145 140

262144 143 135

Мы видим что, время работы парного алгоритма тоже уменьшается с ростом параметра к, и минимальное время (оптимум) достигается при к = 262144.

Теперь приведем наши графики в виде гистограмм (Рисунки 2.1 и 2.2) для оценки итерации и времени вычисления НОД в к-арном алгоритме до и после сдвига интервала коэффициента у.

Рисунок 2.1 Сравнение числа итераций вычисления НОД по парам длины 1500 десятичных разрядов в зависимости от к до и после £ сдвига интервала коэффициента у.

Из рисунка (2.1) видно что, при к = 262144 получается оптимум итерации (583). А на следующем рисунке приведено время вычисления НОД.

Рисунок 2.2 Сравнение времени вычисления НОД по парам длины 1500 десятичных разрядов в зависимости от к до и после £ сдвига интервала коэффициента у.

Из рисунка (2.2) видно что, при к = 262144 с использованием £ получается оптимум времени (135 те) работы к-арного алгоритма в нашей реализации.

На следующем рисунке как пример нашей реализации приведем полный график, изображающий время вычисления НОД в к-арном алгоритме, для 50 пар длины 1500 десятичных разрядов, при к = 256 с использованием разных значений ¿(от 0 до 32).

Рисунок 2.3 Время вычисления НОД для 50 пар длины 1500 десятичных разрядов при к = 256, в зависимости от £ сдвига интервала коэффициента у.

Из рисунка (2.3) видно что, при к = 256 с разными значениями £ оптимум времени будет равен (174 те), и это получается при £ = 21.

Мы видим что при сдвиге интервала изменения коэффициента у и хорошем выборе значений параметра к значительно можно сократить число итерации и уменьшить время вычисления НОД натуральных чисел в к-арном алгоритме.

2.11 Смешанный алгоритм на основе к-арного алгоритма и схемы

Евклида

Одним из недостатков к-арного алгоритма, снижающих его эффективность, является его плохая работы при большом значении коэффициента А/В входной пары чисел. В этом случае, значение С = (Ах + Ву)/к может оказаться

близким к В или даже больше В, и на такой итерации алгоритм проигрывает ехеме Евклида, которая выполняется быстрее и всегда обеспечивает выполнение неравенства С < В.

Можно комбинировать выполнение ^-арного алгоритма со схемой Евклида следующим образом:

1. Если значение коэффициента А/В - невелико, то выполняем парный алгоритм, который обеспечивает на выходе новые значения ^Вс большим значением А/В.

2. На следующей итерации выполняет итерацию Евклида, который опять дает на выходе пару с небольшим значением А/В.

3. Повторяем вычисление.

Дополнительно потребуется выполнять проверку, является ли С, полученное по схеме Евклида, четным, и если да, сокращать его на 2, пока оно не станет нечетным. Выполним экспериментальные вычисления по этой схеме и вычислим время вычисления и количество итераций в сравнении с вычисление по схеме Соренсона. В обоих случаях будем использовать предварительно вычисленные таблицы обратных элементов. Зададим длину входных пар — 500 десятичных разрядов и их количество равным 50.

Поместим в первую таблицу количество итераций обычного алгоритма Соренсона с предтаблицами обратных элементов и комбинированного метода:

Таблица 2.10 Оценка числа итераций для обычного и комбинированного

алгоритмов.

Параметр к Число итераций алгоритма 1 Число итераций алгоритма 2

16 755 685

64 590 578

256 493 500

1024 421 429

4096 373 383

16384 335 341

65536 334 337

Таким образом, число итераций комбинированного алгоритма немного меньше при значениях к ^ 64, но при уже к ^ 256 комбинированный алгоритм

начинает проигрывать, хотя и очень мало обычному алгоритму. Выполним теперь сравнения этих алгоритмов по времени работы.

Таблица 2.11 Оценка времени для обычного и комбинированного алгоритмов.

Параметр к Время работы алгоритма 1 Время работы алгоритма 2

16 179 151

64 137 125

256 118 108

1024 101 95

4096 94 86

16384 91 81

65536 108 89

Эксперименты показали, что для всех значений к комбинированный алгоритм опережает обычный. Более того, почти для всех значений к, кроме самых маленьких, комбинированный алгоритм опережает и алгоритм Евклида, время работы которого составляет 112 мс. Наилучшее время к-арный комбинированный алгоритм показывает при к = 214 = 16384, опережая алгоритм Евклида почти на 28 процентов.

Если сравнивать комбинированный алгоритм с предтаблицами с базовым вариантом алгоритма Соренсона без предтаблиц (табл. 2.2), то здесь также достигается большое ускорение. Например, при к = 16384 время вычисления уменьшилось со 101 мс до 81 мс, что дает нам выигрыш времени около 20 процентов.

2.12 Выводы по главе 2

В этой главе мы рассмотрели базовый к-арный алгоритм Соренсона и методы его ускорения. Нами были получены следующие результаты:

1. Среднее количество итераций к-арного алгоритма для чисел длины 500 десятичных разрядов уменьшается от 1358 до 573 при увеличении к от 16 до 216. Это число значительно меньше среднего числа итераций для таких пар

по схеме Евклида, которое составляет 1942 итерации. Точные данные приведены в таблице 2.1.

2. Среднее значение коэффициента редукции р = А/В в процессе вычисления превышает примерно в 5 раз наименьшее значение этого коэффициента, обеспечиваемое теоремой Соренсона для всех к от 16 до 216.

3. Базовый к-арный алгоритм по схеме Соренсона выполняется медленнее классического алгоритма Евклида для пар чисел длины 1600 бит почти для всех значений к. Наилучшим значением является к = 16384, при котором этот алгоритм работает немного быстрее алгоритма Евклида (101 мс на 50 парах против 112 мс у алгоритма Евклида). Точные результаты в табл. 2.2.

4. При использовании предтаблиц обратных элементов по модулю к алгоритм ускоряется от 3,8% до 9,9% в зависимости от значения к. Наилучший результат (91 мс и 9,9% выигрыша) на парах длины 1600 бит достигается при к = 16384. Немного проигрывает время вычисления при к = 4096 - 94 мс. При увеличении к время опять начинает увеличиваться.

5. Те же расчеты, выполненные для чисел 3200 бит, показывают ухудшение времени работы fc-арного алгоритма относительно схемы Евклида. Наилучшим средним временем на числах такой длины является время 288 мс, достигнутое при к = 16384, но даже это время проигрывает времени работы алгоритма Евклида (264 мс). Отсюда следует, что базовая версия алгоритма Соренсона даже с использованием предтаблиц работает хуже алгоритма Евклида при длине входных аргументов больше примерно 3000 бит.

6. Однако для чисел длины меньше 3000 бит (напомним, что стандартные длины ключей RSA составляют 1024 и 2048 бит) алгоритм Соренсона обгоняет алгоритм Евклида. Время выполнения этих алгоритмов на числах 640 бит доказывает (табл. 2.4) преимущество fc-арного алгоритма по отношению к алгоритму Евклида почти для всех к, а при к = 4096 выполняется за 25 мс против 34 мс у алгоритма Евклида (выигрыш составляет 26,5%).

7. Исследован метод непосредственного анализа значений параметра q = АВ-1 mod к для ускорения вычисления коэффициентов (х,у). Однако, данный алгоритм не дал значительного ускорения вычисления и в дальнейшем не рассматривался.

8. Также был исследован метод использования предтаблиц для прямого нахождения коэффициентов (х,у) по значению параметра д = АВ-1 mod к. Этот подход требует значительного объема машинной памяти, так как необходимо хранить таблицы, содержащие примерно к/4 строк, что при болыпих к становится не эффективным. Однако как показано в табл. 2.5 при к = 4096 мы смогли достичь более быстрого вычисления НОД 50 пар чисел длины 1600 бит, равной 85 мс.

9. Далее нами был исследован метод сдвига параметра у7 заключающийся в том, что вместо интервала [-у/к; л/к] подходящее значение у мы искали в сдвинутом влево интервале [—л/к — Ь;л/к — Ь]. При подходящем значении Ь параметры х и у имеют противоположные знаки, что обеспечивает уменьшение значения линейной комбинации 1Ах + Ву Этот метод хорошо тем, что не требует никаких значительных изменений в алгоритме, а просто изменения границ в процедуре поиска значений коэффициентов (х,у).

Сначала мы рассмотрели небольшие значения к и сдвиги Ь < 2л/к па числах длины 1600 бит. При таких ограничениях получено небольшое ускорение (до 12,8%) при к = 16 и £ = 5 (то ееть у искался та интервале [—9; —1] вместо [—4; 4]).

При следующем значении к = 64 удалось достичь только 3-х процентного выигрыша при £ = 3 (табл. 2.6 и 2.7). Поэтому при к ^ 256 сдвиг па небольшие значения £ является неэффективным.

10. Следующими был рассмотрен метод сдвига на большой интервал, сравнимый по величине с параметром к. В этом случае рассматривались различные значения к и пары чисел различной длины. Результаты вычислений собраны в графики и таблицы, представленные в разделе 2.10.

Общий выигрыш, полученный от таких сдвигов, зависит как от величины сдвига, так и от длины исходных чисел. Наилучший результат для пар длины 4800 бит был достигнут при сдвиге па величину половинв1 к и составит примерно 25 процентов (см. Рис. 2.3).

11. Последним был предложен комбинированный метод вычисления НОД, основанный на исполвзовании па чередовании к-арного алгоритма и алгоритма Евклида. Теоретическая выгода такого сочетания обоснована в секции 2.11, а экспериментальные подсчеты, приведенные в таблице, показывают выигрыш такого алгоритма по отношению к схеме Соренсона с предвычислениями об-

ратных элементов по к от 10 до 18 процентов. По этой схеме было получено наилучшее значение для среднего времени вычисления НОД 50 пар чисел длины 1600 бит, равное 81 мс (28 процентов выигрыша у алгоритма Евклида вычисляющего НОД за 112 мс).

Глава 3. Исследование аппроксимирующего к-арного алгоритма

вычисления ИОД

В этой главе мы рассмотрим проблему эффективной реализации на компьютере аппроксимирующего к-арный алгоритм, являющегося естественным обощением fc-арного алгоритма Соренсона. Этот алгоритм был разработан в 2016 году Ш.Т. Ишмухаметовым [39]. Главное отличие аппроксимирующего fc-арного алгоритма от алгоритма Соренсона заключается в выборе на шаге алгоритма пары параметров (х,у), обеспечивающих тождество

Ах + By = 0 (modк). (3.1)

Идея Ишмухаметова состояла в том, чтобы выбирать эти значения не перебором, а таким способом, чтобы линейная комбинация |Аж+Ву1 принимала минимальное значение. Напомним, что тождество (3.1) эквивалентно равенству

у = —qx + ks, где q = АВ—1 mod к, s £ N.

Варьируя значения двух параметров х и s, можно добиться высокой скорости сходимости fc-арного алгоритма, во много раз превосходящего базовую версию Соренсона. Дальнейшее развитие этого алгоритма было выполнено в статьях [96; 117].

В следующих параграфах мы обсудим базовую схему и детали реализации на языке С++ аппроксимирующего fc-арного алгоритма.

3.1 Базовая схема аппроксимирующего алгоритма

Пусть задан параметр к и пара взаимно-простых с к чисел А и В. По-прежнему будем выбирать значение к, равным степени двойки к = 2t для некоторого целого t ^ 2, из соображений эффективности модульных операций по такому модулю. Числа А и В должны быть нечетными, а если они не являются таковыми, то перед вычислением НОД поделим А и В на общий делитель, равный степени двойки, и если какое-то из чисел А или В останется четным, то сократим его на максимальную степень двойки. В дальнейшем считаем, что числа А и В - нечетные.

Для удобства описания дальнейших операций введем следующее определение.

Определение. Пусть х - произволвное действителвное число. Обозначим через ]х\ наимепвшее целое число, болвшее х, а через [х] наиболвшее целое число, менвшее х.

Для заданного х назовем ближней дробной частвю и определим следующим образом:

Непосредственно из определения следует, что а(х) может бв1тв как положительным так и отрицательным и удовлетворяет неравенству |а(ж)| < 0,5.

Опишем кратко основные этапв1 процедурв1 вычисления пары (х,у) на шаге алгоритма:

1. Получаем на входе два входных нечетных числа А и В.

2. Вычисляем отношение г = А/В.

3. Вычисляем д = АВ-1 (шо^).

4. Вычисляем в = (г — д)/к и выделяем дробную и целую части:

5. Вычисляем дробь Фарея т/п, аппроксимирующую параметр а с наилучшей точностью. Знаменатель п - положителен и ограничен сверху параметром к.

6. Определяем

х = п, у = —дх + кв = —дп — (т + й0 • п) • пк.

7. Определим С = (Ах + Ву)/к. Если С - четно, то будем сокращать его на два, пока оно не станет нечетным.

Для оценки коэффициента редукции р = В/С распишем значение С более подробно:

х — [х], если х — [х] ^ 0,5 х—]х\, иначе.

(3.2)

Ах + Ву (А/В )х + у ~~ = В -к-

В

гх + (—дх + кв)

к

= В

(г - д) к

х + s

= В \ßx + s| = В |(а + s0)^ + s\ =

= В

,т

п

(--Ъ £ + s0)^ + s = В \т + £ • п + s0 • п + s\

(здесь, е - точность аппроксимации а дробью m/v). Зададим значение параметра s равным s = —(т + s0 • п). Тогда получим

С = В|е • п\, и у = — дж + sk = — qn — (т + s0 • п) • к.

Таким образом, значение коэффициента редукции р = В/С =1/пев этой итерации определяется точностью аппроксимации параметра а рациональной дробью. В статье [39] доказано, что при ограничении п < к можно добиться точности

£ <

3

2F'

Отсюда выводим, что