🔍 Поиск готовых работ

🔍 Поиск работ

АНАЛИЗ И ИССЛЕДОВАНИЕ СХОДИМОСТИ АЛГОРИТМА ПОИСКА КОЭФФИЦИЕНТОВ БЕЗУ

Работа №47948

Тип работы

Магистерская диссертация

Предмет

информатика

Объем работы72
Год сдачи2018
Стоимость5700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
365
Не подходит работа?

Узнай цену на написание


ВВЕДЕНИЕ 3
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ СХЕМ
ОПТИМИЗАЦИИ ОБЫЧНОГО АЛГОРИТМА ЕВКЛИДА 7
1.1. Алгоритм Евклида 7
1.2. Расширенный алгоритм Евклида 9
1.3. Бинарный алгоритм Евклида 11
1.4. K-арный алгоритм Евклида 13
1.5. Аппроксимирующий алгоритм Евклида 15
1.6. Дроби Фарея 18
1.7. Выводы по главе 1 20
ГЛАВА 2. МЕТОДЫ РЕАЛИЗАЦИИ СХЕМ ОПТИМИЗАЦИИ АЛГОРИТМА ПОИСКА КОЭФФИЦИЕНТОВ БЕЗУ 21
2.1. Бинарный расширенный алгоритм Евклида 21
2.2. K-арный расширенный алгоритм Евклида 23
2.3. Обратный элемент заданного числа 26
2.4. Аппроксимирующий расширенный алгоритм Евклида 28
2.5. Параллельный аппроксимирующий расширенный алгоритм Евклида 29
2.6. Выводы по главе 2 31
ГЛАВА 3. ПРОГРАМНАЯ РЕАЛИЗАЦИЯ СХЕМ ОПТИМИЗАЦИИ АЛГОРИТМА ПОИСКА КОЭФФИЦИЕНТОВ БЕЗУ 32
3.1. Принцип работы программы 32
3.2. Простое число 33
3.3. Степень числа 2 39
3.4. Выводы по главе 3 44
ЗАКЛЮЧЕНИЕ 46
СПИСОК ИСПОЛЬЗУЕМЫХ СОКРАЩЕНИЙ 49
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 50
ПРИЛОЖЕНИЯ

Актуальность проблемы: Криптография — наука, занимающаяся разработкой криптосистем, то есть исследованием математических методов преобразования информации с целью защиты систем от несанкционированного доступа.
В век современных технологий время является очень ценным ресурсом. Поэтому важным показателем работы программы является его скорость вычислений. Процесс увеличения скорости идет в следующих направлениях:
1. Увеличение производительности оборудования. Достигается за счёт использования более мощных процессоров. Главной трудностью в данном подходе является большая трудность изготовления таких процессоров. Ещё одной трудностью является обновление оборудования на всех машинах, что влечёт за собой дополнительные расходы.
2. Распараллеливание программы. Распределение общей работы между разными потоками позволяет уменьшить общее время работы программы. Однако алгоритм поиска коэффициентов Безу является итеративным, и соответственно не подлежит распараллеливании.
3. Уменьшение асимптотической сложности используемого алгоритма. Именно этот подход и будет использован в данной работе. Заключается он в уменьшении числа элементарных операций, используемых алгоритмом. Соотношение Безу — представление наибольшего общего делителя целых
чисел в виде их линейной комбинации с целыми коэффициентами [20, с. 29]. Для случая двух целых чисел А и В и их GCD(A,B) = d — наибольший общий делитель, данное соотношение записывается в следующем виде [25, с. 7]:
Аи + Bv = d (1)
При этом коэффициенты и и v называются коэффициентами Безу. Нахождение коэффициентов Безу может использоваться при решении следующих задач:
1. Решение диофантовых уравнений первой степени вида [9, с. 49]:
2. Решение сравнений первой степени вида [2, с. 68] [36]:
Ах = В (mod т) (3)
3. Поиск обратного элемента в поле — частный случай уравнения (3):
Ах = 1 (mod т) (4)
4. Является основой для некоторых криптографических алгоритмов с
открытым ключом, таких как RSA. [6, с. 438] [27, с. 286]
Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел [7, с. 11] [19, с. 180]. Этот алгоритм итеративный и определяется соотношением [23, с. 26]:
GCD (А, В) = GCD (В, A mod В) (5)
Расширенный алгоритм Евклида — модификация алгоритма Евклида, позволяющая находить коэффициенты Безу. Основной идеей является представление полученного остатка на каждой итерации в виде линейной комбинации исходных чисел А и В.
Основной идеей оптимизации алгоритма поиска коэффициентов Безу будет изменение выбора нового числа, что должно привести к более быстрой сходимости алгоритма и соответственно уменьшению числа итераций.
Главным недостатком подхода, описанного выше, является увеличение нагрузки на одну итерацию, что может привести уменьшению скорости полного алгоритма. Поэтому мы должны также оптимально находить новые значения для следующей итерации.
Объект исследования: сфера криптографии и алгоритмов теории чисел.
Предмет исследования: алгоритм нахождения коэффициентов Безу, его алгоритмическая сложность и схемы для его оптимизации.
Цель магистерской диссертации: исследование схем оптимизации алгоритма поиска коэффициентов Безу, их алгоритмическая сложность и их реализация.
Для достижения поставленной цели в работе сформулированы и решены следующие задачи:
1. Анализ алгоритма поиска коэффициентов Безу.
2. Анализ существующих схем оптимизации для обычного алгоритма Евклида.
3. Построение нового алгоритма поиска коэффициентов Безу на основе изученных схем.
Научная новизна исследования: В данной работе можно выделить 4 пункта новизны:
1. Вывод теоретической оценки сходимости для всех рассмотренных схем оптимизации алгоритма поиска коэффициентов Безу.
2. Математическое описание параллельного аппроксимирующего расширенного алгоритма Евклида, идея которого высказана в работе [21].
3. Программная реализация всех рассмотренных схем оптимизации алгоритма поиска коэффициентов Безу на языке Python 3.
4. Проверка на практике теоретически выведенных схем оптимизации алгоритма поиска коэффициентов Безу.
Объем и структура работы: Магистерская диссертация состоит из введения, трёх глав, заключения, списка использованной литературы и приложения в виде листинга. Объем основного текста составляет 45 страниц машинописного текста.
В первой главе проведен краткий анализ предметной области — исходные обычный и расширенный алгоритмы Евклида. Рассмотрены следующие схемы оптимизации обычного алгоритма Евклида — бинарный, k-арный и аппроксимирующий. Также для всех алгоритмов подсчитано примерное число итераций.
Во второй главе рассматриваются модифицированные расширенные алгоритмы Евклида. Для модификации использовались следующие схемы — k-арный, аппроксимирующий и аппроксимирующий с параллелизацией. Все перечисленные схемы были использованы для анализа.
В третьей главе дано описание программы, использованных библиотек и результаты экспериментов.
Каждая глава заканчивается краткими выводами, а вся работа — заключением.

Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

В работе рассмотрены теоретические и практические вопросы поиска коэффициентов Безу. Разработаны: программа, содержащая реализацию всех рассмотренных схем оптимизации расширенного алгоритма Евклида. Также, в диссертации, для оценивания эффективности оптимизации расширенного алгоритма Евклида проведены эксперименты и показаны результаты.
В результате проведенной работы получены следующие результаты:
• Проведён анализ обычного и расширенного алгоритмов Евклида. Разобраны схемы алгоритмов и проведена оценка их сходимости. Также показаны возможные практические применения алгоритмов.
• Проведён анализ существующих методов оптимизации алгоритма
Евклида. Выбранными оказались: бинарный, k-арный,
аппроксимирующий алгоритмы. Разобраны схемы алгоритмов и проведена оценка их сходимости.
• Проведён анализ бинарного расширенного алгоритма Евклида. Разобрана схема алгоритма и проведена оценка его сходимости. Также были приведены аргументы, почему данный алгоритм не рассматривается в этой работе.
• Проведён анализ методов оптимизации алгоритма Евклида. Выбранными оказались: k-арный, аппроксимирующий алгоритмы. Представлены их модификации для расширенного алгоритма Евклида. Рассмотрены возможные исключительные ситуации и разобраны способы их решения. Разобраны схемы алгоритмов и проведена оценка их сходимости.
• Проведён анализ параллельного расширенного алгоритма Евклида. Разобрана схема алгоритма и проведена оценка его сходимости.
• Реализованы все разобранные схемы оптимизации алгоритма Евклида. Протестированы на практике корректность работы полученных реализаций.
• Реализованы все разобранные схемы оптимизации расширенного алгоритма Евклида. Протестированы на практике корректность работы полученных реализаций.
• Реализована программа для проведения экспериментов. Временные характеристики алгоритмов, полученные в ходе программы, сохраняются в файлах.
• Проведён анализ полученных характеристик. Получено графическое отображение результатов.
В ходе работы были сделаны следующие выводы по рассмотренным схемам:
• K-арный — показал наихудший результат среди всех рассмотренных схем. При маленьких значениях модуля количество шагов оказалось больше, чем у оригинального, при больших появился значительный выигрыш. Количество работы на одной итерации при небольшом модуле меньше, чем у других схем, но больше, чем у оригинального алгоритма. Это приводит к суммарному проигрышу во времени для всего алгоритма по сравнению с оригинальным.
• Аппроксимирующий — показал наилучший результат среди всех рассмотренных схем. Количество шагов в разы уменьшилось по сравнению с оригинальным алгоритмом. При больших значениях модуля совпадает по количеству шагов с параллельным. Количество работы на одной итерации при небольшом модуле меньше, чем у параллельного, но больше, чем у оригинального алгоритма. Однако при больших значениях дисперсия становится слишком большой, что усложняет анализ. Одной из причин может быть неоднородная сходимость алгоритма на дробях Фарея.
• Параллельный — количество шагов в разы уменьшилось по сравнению с оригинальным алгоритмом. При больших значениях модуля совпадает по количеству шагов с аппроксимирующим. Количество работы на одной итерации при небольшом модуле самое большое по сравнению с другими алгоритмами. Однако при больших значениях дисперсия становится слишком большой, что усложняет анализ. Одной из причин может быть неоднородная сходимость алгоритма на дробях Фарея.
Дальнейшим направлением исследования возможно уменьшение времени работы, затраченной на одной итерации. Среди возможных подходов: раскрытие внутренних вызовов функций, использование более низкоуровневого языка, использование более быстрого алгоритма подбора коэффициентов.


1. Акритас А. Основы компьютерной алгебры с приложениями: пер. с англ.,
М., Мир, 1994, 544 с.
2. Егоров Д. Ф. Элементы теории чисел., М., Петроград: Госиздат, 1923, 202 с.
3. Ишмухаметов Ш.Т. Вычисление коэффициентов Безу для k-арного алгоритма нахождения НОД., КФУ, Казань, Россия, 2016, 6 с.
4. Ишмухаметов Ш.Т. Рубцова Р.Г. Об аппроксимирующем k-арном алгоритме вычисления НОД., КФУ, Казань, Россия, 2016, 4 с.
5. Ишмухаметов Ш.Т. Аппроксимирующий k-арный алгоритм нахождения НОД // Журнал математики им. Лобачевского № 2., Казань, Россия, 2016, с. 722-728.
6. Крэнделл Р., Померанс П. Простые числа: криптографические и вычислительные аспекты., М., УРРС, 2011, 664 с
7. Начала Евклида Т. 2.: пер. с греч. и комм. Мордухая-Болтовского Д. Д. под ред. Выгодского М. Я. и Веселовского И. Н., М., ГИТТЛ, 1949, 511 с.
8. Савин А. Число Фидия - золотое сечение (рус.) // "Квант": Научнопопулярный физико-математический журнал № 6., М., 1997, 32-33 с.
9. Сушкевич А. К. Теория чисел. Элементарный курс., Харьков, Изд-во Харьковского университета, 1954, 204 с.
10. Akhavi, A., Vallee, B. Average Bit-Complexity of Euclidean Algorithms, In: Proceedings ICALP’00, Lecture Notes Computer Science 1853, 2000, pp. 373387.
11. Brent, R. Twenty years’ analysis of the Binary Euclidean Algorithm, Millenial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in honour of A. Hoare, Palgrave, NY, 4153, 2000, pp. 41-53.
12. Brocot, A.: Calcul des rouages par approximation, nouvelle methode. Revue Chronometrique 6 (1860), pp. 186-194.
13. Chor, B., Goldreich, O. An improved Parallel Algorithm for integer GCD, Algorithmica, 5, 1990, pp. 1-10.
14. Dixon, J. The Number of Steps of the Euclidian Algorithm, Journal of Number Theory, 1, 1970, pp. 414-422.
15. Dolgov D. A. Comparative Analysis of Module Reduction Calculation Algorithms. Research Journal of Applied Sciences, 10, 2015, pp. 442-446.
16. Dolgov D. A. GCD calculation in the search task of pseudoprime and strong pseudoprime numbers, Lobachevskii Journal of Mathematics, Volume 37, Issue 6, 2016, pp. 733—738.
17. Farey, J.: On a Curious Property of Vulgar Fractions. London, Edinburgh and Dublin Phil. Mag. 47, 1816, p. 385,
18. Forisek M. “Approximating Rational Numbers by Fractions”. Bratislava,
Slovakia, 2007, p. 10.
19. Hardy, G.H., Wright, E.M. An Introduction to the Theory of Numbers, Oxford, Calrendon Press, 4-th ed, 1959, p. 433.
20. Hasse H. «Vorlesungen Uber Zahlentheorie», Berlin, 1950, p. 59. 21.Ishmuhametov S.T. A parallel computation of the GCD of natural numbers, Kazan
Federal University, Kazan, Russia, 2016, p. 9.
22.Ishmukhametov S. T., Rubtsova R. G. A fast algorithm for counting GCD of natural numbers, Proc. of intern.conf. Algebra, Analyses and Geometry, Kazan, Kazan Federal University, 2016, pp. 52-53
23.Ishmukhametov S., Mubarakov B., Mochalov A. Euclidian Algorithm for Recurrent Sequences, Applied Discrete Mathematics and Heuristic Algorithms, International Scientific Journal, Samara, 1, №2, 2015, pp. 57-62.
24. Jebelean T. A. Generalization of the Binary GCD Algorithm, Proc. Of Intern.Symp.on Symb.and Algebr. Comp.(ISSAC’93), 1993, pp. 111-116.
25. Jones, G. A., Jones, J. M. §1.2. Bezout's Identity // Elementary Number Theory. — Berlin: Springer-Verlag, 1998, p. 302.
26. Knuth D. E. The Art of Computer Programming. — 3. — Addison-Wesley. — Т. 2: Seminumerical Algorithms. — ISBN 0-201-89684-2, 1997, p. 704.
27. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. CRC Press, 1996, p. 816.
28.Ore O. Number Theory and Its History. — McGraw-Hill, 1948, p. 400.
29.Schohage, A. Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients. In: European Computer Algebra Conference, 144, 1982, p. 315.
30.Sorenson J. The k-ary GCD Algorithm, Universitet of Wisconsin-Madison, Tecn.Report, 1990, pp. 1-20.
31.Sorenson J. Two fast GCD Algorithms, J.Alg. 16, №1, 1994, pp. 110-144
32.Sorenson. J. An analysis of the generalized binary GCD algorithm, in: A. van der Poorten, A. Stein (Eds.), High Primes and Misdemeanors, Lectures in Honour of Hugh Cowie Williams, Banff, Alberta, Canada, AMS Math. Review, 41 (2005h: 11279), 2005, pp. 254-258.
33.Stein, J. "Computational problems associated with Racah algebra", Journal of Computational Physics, 1 (3): doi:10.1016/0021-9991(67)90047-2, ISSN 00219991, 1967, pp. 397-405.
34. Tonkov T. On the average length of finite continued fractions // Acta Arithmetica. — Т. 26, 1974, pp. 47-57.
35. Weber K. The accelerated integer GCD algorithm, ACM Trans.Math.Software,
21, №1, 1995, pp. 1-12.
36. https://brilliant.org/wiki/bezouts-identity/ [Дата обращения 15 Октября 2016, открытый доступ]
37. http ://cmcstuff.esyr.org/vmkbotva-
r15/3 %20%D0%BA%D 1 %83 %D 1 %80%D 1%81/6%20%D0%A1%D0%B5%D0 %BC%D0%B5%D 1%81%D 1%82%D1%80/%D0%92%D 1 %8B%D 1%87%D0% B8%D1%81%D0%BB%D0%B8%D 1 %82%D0%B5%D0%BB%D 1%8C%D0%B D%D0%B0%D 1%8F%20%D 1 %81 %D0%BB%D0%BE%D0%B6%D0%BD%D 0%BE%D 1 %81 %D 1 %82%D 1%8C%20%D0%B0%D0%BB%D0%B3%D0%BE %D 1%80%D0%B8%D 1 %82%D0%BC%D0%BE%D0%B2/abramov10_2005.pdf [Дата обращения 21 Января 2018, открытый доступ]
38. http://e-maxx.ru/algo/fibonacci_numbers [Дата обращения 10 Октября 2016, открытый доступ]
39. http://e-maxx.ru/algo/stern_brocot_farey [Дата обращения 15 Ноября 2017, открытый доступ]
40. http://www.itlab.unn.ru/Uploads/coaChapter09.pdf [Дата обращения 17 Ноября 2016, открытый доступ]
41. http://mathworld.wolfram.com/PortersConstant.html [Дата обращения 13 Ноября 2016, открытый доступ]

Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2025 Cервис помощи студентам в выполнении работ
.