ВВЕДЕНИЕ 3
1. Анализ предметной области 5
1.1 Делимость чисел 5
1.2 Наибольший общий делитель 5
2. Обзор различных алгоритмов нахождения НОД 8
2.1 Классический алгоритм Евклида 8
2.2 Расширенный алгоритм Евклида 9
2.3 Бинарный алгоритм 10
2.4 k-арный алгоритм нахождения НОД 11
2.5 Аппроксимирующий Парный алгоритм 13
2.6 Теоретические оценки сложности алгоритмов 18
3. Реализация аппроксимирующего Парного алгоритма 19
3.1 Ряды Фарея 19
3.2 Цепные дроби 21
3.3 Сравнение скорости работы рядов Фарея и цепных дробей 22
3.4 Оптимизация алгоритма 23
3.5 Проверка гипотезы 24
3.6 Реализация алгоритма с изменяющимся к 27
3.7 Программный интерфейс 28
ЗАКЛЮЧЕНИЕ 30
СПИСОК ЛИТЕРАТУРЫ 31
ПРИЛОЖЕНИЯ 33

Купить

На сегодняшний день в мире происходит глобальный процесс информатизации. В каждый элемент повседневной жизни человека внедряются компьютерные технологии, которые затрагивают каждый сегмент общества. Если раньше подобные технические достижения применялись в основном в военных целях, то сейчас работа органов государственной власти, компаний крупного и малого бизнеса, различных некоммерческих организации, медицинских учреждений и всех остальных институтов общества теперь напрямую связана с информационными технологиями. Хранимые и передаваемые данные должны оставаться в сохранности и быть защищенными от несанкционированного доступа. Именно поэтому крайне важно обеспечить безопасность и конфиденциальность при работе с информационными системами. Решением этой задачи занимается криптография.
Основной задачей криптографии является обеспечение высокого уровня секретности для защищаемой информации, чтобы не допустить ее утечки или искажения во время атак злоумышленников. В процессе обеспечения безопасности криптография использует множество математических алгоритмов, одним из которых является алгоритм нахождения наибольшего общего делителя (НОД) двух чисел. Нахождение НОД используется во многих криптографических алгоритмах шифрования, например, в RSA, или является частью других математических функций, таких как нахождение наименьшего общего кратного.
Также в криптографии очень большое значение имеют большие числа. На их основе построены все современные алгоритмы шифрования. Причиной этого является то, что работа с большими числами занимает много времени и ресурсов, и взлом таких систем шифрования является очень трудной задачей.
Алгоритм нахождения НОД был известен еще до нашей эры. На данный момент существует несколько способов нахождения наибольшего общего делителя, одним из которых является аппроксимирующий Парный алгоритм.
Он основывается на Парном алгоритме Соренсона, с тем отличием, что при вычислении числа C используется другой метод нахождения коэффициентов х и у. Для того, чтобы их найти, применяется аппроксимация вещественного числа r несократимой дробью. Данное приближение позволяет уменьшить время работы всего алгоритма.
Научным руководителем, Еникеевым Р.Р., была выдвинута гипотеза о том, что при малых значениях чисел A, B наиболее эффективным выбором коэффициента k являются малые числа. На основе данной гипотезы был предложен алгоритм с изменяющимся значением k, который при вычислении НОД больших чисел использует большое значение к, а для малых - уменьшает его значение. Подтверждение гипотезы может способствовать повышению скорости работы алгоритма.
Целью выпускной квалификационной работы является проверка выдвинутой гипотезы и реализация аппроксимирующего алгоритма с изменяющимся k.
Для достижения поставленных целей были выдвинуты следующие задачи:
- изучение литературы по алгоритмам нахождения НОД;
- реализация аппроксимирующего k-арного алгоритма;
- исследование аппроксимирующего алгоритма для различных k;
- реализация аппроксимирующего алгоритма с изменяющимся k.

Купить