Тема: Реализация и исследование алгоритма быстрого умножения полиномов на основе методов Карацубы и Тоома-Кука

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

В ходе выполнения выпускной квалификационной работы были сделаны теоретические выкладки на тему исследуемых методов умножения полиномов, таких как алгоритм их работы, сложность вычислений, возможности оптимизации и прочее. Проведя анализ полученных в ходе исследования данных можно сделать вывод, что применение наивного алгоритма ограничено «строго бытовыми» задачами - время умножения в несколько часов для чисел порядка ~105 знаков говорит о его неприменимости для решения сложных вычислительных задач. Что касается методов Карацубы и Тоома-Кука, то они показывают отличные результаты даже при умножении полиномов длиной миллион знаков, подтверждая теоретические выкладки, сделанные ранее. Алгоритм Тоома- Кука немного выигрывает по времени у алгоритма Карацубы, так как по сути является модификацией последнего. Так же разница в скорости работы реализованных методов подкрепляет их теоретическую сложность вычислений. Данные быстрые алгоритмы умножения полиномов рекомендуются к внедрению в сложные информационные системы и приложения, в которых задействована длинная арифметика.
Подводя итог, можно сказать, что поставленные цели были достигнуты: глубоко изучена теоретическая часть первых быстрых алгоритмов умножения, реализовано клиентское приложение, готовое к интеграции в сложные вычислительные системы, проведено комплексное сравнение эффективности исследуемых алгоритмов умножения полиномов на основе методов Карацубы и Тоома-Кука.

Купить