Тема: РЕАЛИЗАЦИЯ АППРОКСИМИРУЮЩЕГО К-АРНОГО АЛГОРИТМА С ИЗМЕНЯЮЩИМСЯ К

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

Купить

В ходе выпускной квалификационный работы были рассмотрены различные алгоритмы нахождения наибольшего общего делителя и реализован аппроксимирующий Парный алгоритм. Главная цель работы состояла в подтверждении поставленной гипотезы о том, что скорость работы алгоритма будет выше, если применять на малых числах меньшее значение к и наоборот.
Для подтверждения гипотезы были проведены множественные тесты алгоритма на числах разной длины с разным значением к. Были построены соответствующие графики, на которых можно пронаблюдать существование зависимости скорости работы алгоритма от длины входных чисел и к. Действительно, на длинных числах целесообразно применять большее значение числа к. При уменьшении чисел, когда их средняя длина переходит из одного интервала в другой и перед началом новой итерации аппроксимирующего алгоритма, следует уменьшить значение к.
На основе полученных данных были определены интервалы длин входных чисел. Каждому из интервалов соответствует число к, при котором алгоритм показывает наименьшее время выполнения. После чего полученные пары «интервал - к» были добавлены в словарь, к которому происходит обращение при выборе к.
При реализации поиска коэффициентов Безу в аппроксимирующем алгоритме было принято решение использовать цепные дроби вместо рядов Фарея. Для этого были проведены тесты, в ходе которых было установлено, что при использовании цепных дробей скорость алгоритма становится выше.
Также были добавлены функции, оптимизирующие работу аппроксимирующего алгоритма. Эти функции позволяют быстрее найти бинарную длину числа и вычислить обратный элемент по модулю.
Проведенная работа позволяет улучшить работу аппроксимирующего к- арного алгоритма, что предоставляет возможность быстрее находить НОД
больших чисел, широко применяемых в криптографии.

Купить