ВВЕДЕНИЕ 3
1. Анализ основных алгоритмов умножения длинных чисел 6
2. Особенности реализации алгоритмов умножения длинных чисел и
экспериментальные вычисления 24
3. Анализ алгоритмов, использующих операции умножения длинных
чисел 29
4. Особенности реализации алгоритмов, использующих операции
умножения длинных чисел и экспериментальные вычисления 37
ЗАКЛЮЧЕНИЕ 44
СПИСОК ЛИТЕРАТУРЫ 45
ПРИЛОЖЕНИЕ
Актуальность. Активное развитие информационных технологий и средств связи повышает актуальность проблемы информационной безопасности. По этой причине требуется совершенствовать старые методы защиты информации и средства, а также разрабатывать новые методы и средства, направленные на повышение уровня информационной безопасности общества. Следовательно, необходим комплексный подход для повышения уровня информационной безопасности. Таким образом, возникает потребность перейти к эффективному использованию правовых, организационных и технических мер обеспечения защиты информации [1].
Одну из главных ролей в обеспечении информационной безопасности играют криптографические методы. На сегодняшний день, увеличивается актуальность использования криптографических систем защиты информации, например, таких криптографических алгоритмов как Эль-Г амаля и RSA. Эти алгоритмы основаны на вычислительной сложности задач факторизации и вычисления дискретного логарифма в конечном поле.
Стоит отметить, что при работе с криптографическими системами часто возникает необходимость вычисления операций умножения, при этом зачастую данные операции требуется производить десятки и более раз. В связи с этим возникает актуальность исследования алгоритмов умножения длинных чисел, повышение эффективности которых может значительно увеличить эффективность работы действующих криптосистем и дать новые инструменты в обеспечении защиты информации.
Целью научно-исследовательской работы является анализ эффективности работы алгоритмов умножения длинных чисел и оценка практического быстродействия, включая анализ их эффективности в рамках применения в конкретных практических задачах, алгоритмах факторизации чисел и нахождения НОД.
Для достижения поставленной цели были сформулированы следующие задачи:
1. Изучить (проанализировать текущие результаты) следующие алгоритмы умножения длинных чисел:
- Наивный алгоритм;
- Алгоритм Карацубы;
- Алгоритм Тоома-Кука;
- Алгоритм Шенхаге;
- Алгоритм Нюссбаумера.
2. Реализовать (в виде программы) алгоритмы умножения длинных чисел, которые являются предметом исследования в данной работе.
3. Провести практические эксперименты, сформировать выводы на основании полученных результатов об эффективности исследуемых алгоритмов на числах разного порядка.
4. Провести исследование и реализовать (в виде программы) алгоритмы, в которых на практике требуется проводить операции умножения длинных чисел: K-арный алгоритм нахождение НОД, Алгоритм факторизации Ленстры (включая использование проективных координат).
5. Провести практические эксперименты путем использования различных алгоритмов умножения длинных чисел в работе алгоритмов, которые используют операции умножения K-арный алгоритм нахождение НОД, Алгоритм факторизации Ленстры. Сформировать выводы об эффективности использования того или иного алгоритма умножения длинных чисел в рамках алгоритмов, которые используют их как вспомогательные на числах разного порядка.
Результатом научно-исследовательской работы стали полученные в ходе исследования выводы о практической эффективности использования алгоритмов умножения длинных чисел, как составных частей других алгоритмов, используемых в криптографии, а также программный комплекс, который использует различные наиболее эффективные алгоритмы умножения длинных чисел в зависимости от размерности входных чисел, что значительно увеличивает быстродействие вычисления операции умножения длинных чисел.
Выпускная квалификационная работа состоит из 4 основных глав:
- В первой главе приводится описание исследуемой предметной области, значимость исследуемых задач для криптографии, а также описание алгоритмов умножения длинных чисел, которые являются предметом исследования в настоящей работе.
- Во второй главе приводится описание разработанного программного комплекса, предназначенного для тестирования алгоритмов и методика проведения экспериментов, а также сформированные выводы по итогам проведения экспериментальных вычислений.
- В третьей главе приводится описание алгоритмов нахождения НОД и факторизации чисел, которые используют операции умножения.
- В четвертой главе приводится описание программного комплекса, который был разработан для проведения вычислительных экспериментов работы алгоритмов умножения длинных чисел в алгоритмах нахождения НОД и факторизации чисел.
По результатам проведенных работ можно утверждать, что все поставленные цели и задачи были выполнены, а именно были реализованы и проведены эксперименты со следующими алгоритмами умножения длинных чисел:
- «Наивный» алгоритм;
- Алгоритм Карацубы;
- Алгоритм Тоома-Кука;
- Алгоритм Шенхаге;
- Алгоритм Нюссбаумера.
Данные алгоритмы были протестированы в ходе применения в следующих практических задачах (математических алгоритмах):
- k-арный алгоритм нахождения НОД
- Алгоритм факторизации Ленстры
По результатам проведенных экспериментов можно сделать следующие выводы:
- Практическим путем подтвердилась гипотеза о том, что нет наиболее эффективного алгоритма умножения длинных чисел, разные алгоритмы умножения длинных чисел на числах разного порядка имеют разную эффективность.
- Для проведения операций умножения в рамках К-арного алгоритма нахождения НОД наиболее эффективным является «наивный» алгоритм умножения.
- Для проведения операций умножения в рамках алгоритма факторизации Ленстры при размерности входного числа менее 56 знаков наиболее эффективным является «наивный» алгоритм умножения, а в случае если размерность входного числа составляет 56 и более знаков наиболее эффективным является алгоритм умножения Карацубы.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
