Введение 3
Постановка задачи 4
Ход работы 5
Тест Миллера- Рабина 6
р - метод Полларда 8
Алгоритм Ленстры 12
Метод квадратичного решета 16
Сравнительный анализ алгоритмов 21
Заключение 29
Список литературы 30
Приложение 31
Купить

В данной работе будут рассмотрены следующие алгоритмы факторизации: алгоритм Ленстры, алгоритм Полларда, квадратичное решето Померанца. Под факторизацией будем понимать декомпозицию объекта, а именно разложение натурального числа в произведение простых чисел. Единственность и существование следует из основной теоремы арифметики.
Факторизация целых чисел является задачей довольно-таки большой сложности, в особенности для больших чисел. До сих пор неизвестен алгоритм, который позволяет быстро факторизовать довольно большое число (порядка 32 знаков и больше). Факторизация лежит в основе многих алгоритмов шифрования, таких как RSA и алгоритм электронно - цифровой подписи. Отсюда вытекает актуальность данной работы.
В данной работе будет поставлено множество экспериментов по факторизации целых чисел, а также будет проведено тестирование параллельных алгоритмов факторизации и их сравнение по эффективности с обычными алгоритмами.
Целью дипломной работы является изучение параллельных методов решения задач факторизации. Данные методы должны допускать эффективное распараллеливание на многопроцессорных вычислительных системах с массовым параллелизмом, демонстрируя масштабируемость, близкую к линейной. Исследуемые алгоритмы теоретически должны работать быстрее в зависимости от входных данных.
Актуальность работы обоснована тем, что в настоящее время программные продукты, использующие параллельные технологии, не так широко развиты в мире.

Купить