ВВЕДЕНИЕ 3
1. ПОСТАНОВКА ЗАДАЧИ 6
2. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 8
3. АЛГОРИТМЫ УМНОЖЕНИЯ 10
3.1. НАИВНЫЙ АЛГОРИТМ УМНОЖЕНИЯ 11
3.2. БЫСТРЫЕ АЛГОРИТМЫ УМНОЖЕНИЯ 13
3.2.1. Возникновение области быстрых алгоритмов 13
3.2.2. Метод Карацубы 15
3.2.3. Метод Тоома-Кука 18
4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ 22
4.1. ВЫБОР СРЕДСТВ РАЗРАБОТКИ 22
4.2. ОПИСАНИЕ ФУНКЦИОНАЛА ПРИЛОЖЕНИЯ 23
4.3. ТЕСТИРОВАНИЕ 28
5. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ 32
5.1. ВЫБОР ДИАПАЗОНА ДАННЫХ ДЛЯ ИССЛЕДОВАНИЯ 32
5.2. АНАЛИЗ ПОЛУЧЕННОЙ ИНФОРМАЦИИ 33
ЗАКЛЮЧЕНИЕ 35
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 36
ПРИЛОЖЕНИЕ 37
В наш век стремительного появления все новых и новых информационных систем, и их непрекращающегося развития, все сводится к тому, что каждая уважающая себя организация, использующая и хранящая ценную информацию, задумывается о защите этих данных. К тому же существует ряд информационных технологий, при создании и функционировании которых фактор безопасности имеет первоочередное значение. Сегодня среди средств защиты информации от неправомерного использования выделяют несколько групп:
• технические (или аппаратные) средства;
• программные средства;
• смешанные аппаратно-программные средства;
• организационные средства.
К техническим средствам относятся инженерные устройства различного типа, которые аппаратным способом препятствуют утечке важной информации. Сюда относят: замки на дверях, сигнализация, сканирующие устройства, генераторы шумов и различные сетевые фильтры. К достоинствам средств защиты этого типа можно отнести их независимость от внешних факторов и надежность, а к недостаткам - высокую стоимость, малую гибкость и большие габариты.
Программные средства включают в себя программы и алгоритмы контроля доступа к системе, установления личности пользователя, шифрования данных, а также антивирусное ПО, средства архивации данных, межсетевые экраны и др. Преимущество программных средств состоит в их универсальности, надежности, гибкости и способности к развитию, а недостаток в чувствительности к изменениям и зачастую большому количеству потребляемых ресурсов, а следовательно зависимости от мощности вычислительной системы, в которой функционируют.
Смешанные аппаратно-программные средства обеспечивают информационную безопасность путём эффективного сочетания комплекса технических и программных средств.
Организационные средства являются результатом взаимодействия организационно-правовых (нормативно-правовые акты, установленные предприятием) и организационно-технических (планирование помещений, установка аппаратуры, разграничения прав доступа) мероприятий. Организационные средства помогают решать большое количество различных проблем, легко реализуемы и неограниченны в модифицировании. К недостаткам можно отнести высокую зависимость от внешних факторов.
На сегодняшний день, по степени популярности и доступности выделяют именно программные средства - к примеру, не каждая организация озабочивается проверкой на наличие внешних прослушивающих устройств на своей территории, а вот комплект антивирусных программ для рабочих компьютеров зачастую занимает первую строчку в списке расходов на обеспечение информационной безопасности системы. И в свою очередь едва ли не самым надежным механизмом программной защиты являются криптографические методы, которые все чаще применяется как при сборе и обработке информации, так и при ее хранении и передаче.
Криптография - одна из старейших наук, ее суть заключается в методах обеспечения конфиденциальности и аутентификации, создания симметричных и асимметричных криптосистем, систем цифровой подписи, хэш-функций и т.д. Криптография тесно связана с математикой, ведь именно в правильном и эффективном использовании простейших математических операций лежит суть этой непростой, но интересной науки. И такова тенденция развития современного уровня кибербезопасности, что требования к производительности алгоритмов, основанных на этих операциях, постоянно растут.
В данной работе мы подробнее остановимся на одной математической операций - на умножении, которое, как оказалось в ходе исследования, можно использовать намного эффективнее, чем это осуществляют многие информационные системы обработки информации.
В ходе выполнения выпускной квалификационной работы были сделаны теоретические выкладки на тему исследуемых методов умножения полиномов, таких как алгоритм их работы, сложность вычислений, возможности оптимизации и прочее. Проведя анализ полученных в ходе исследования данных можно сделать вывод, что применение наивного алгоритма ограничено «строго бытовыми» задачами - время умножения в несколько часов для чисел порядка ~105 знаков говорит о его неприменимости для решения сложных вычислительных задач. Что касается методов Карацубы и Тоома-Кука, то они показывают отличные результаты даже при умножении полиномов длиной миллион знаков, подтверждая теоретические выкладки, сделанные ранее. Алгоритм Тоома- Кука немного выигрывает по времени у алгоритма Карацубы, так как по сути является модификацией последнего. Так же разница в скорости работы реализованных методов подкрепляет их теоретическую сложность вычислений. Данные быстрые алгоритмы умножения полиномов рекомендуются к внедрению в сложные информационные системы и приложения, в которых задействована длинная арифметика.
Подводя итог, можно сказать, что поставленные цели были достигнуты: глубоко изучена теоретическая часть первых быстрых алгоритмов умножения, реализовано клиентское приложение, готовое к интеграции в сложные вычислительные системы, проведено комплексное сравнение эффективности исследуемых алгоритмов умножения полиномов на основе методов Карацубы и Тоома-Кука.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
